字典和集合基礎字典是一系列無序元素的組合，其長度大小可變，元素可以任意的刪減和改變。不過，這里的元素是一堆鍵（key）和值（value）的配對。

集合沒有鍵和值的配對，是一系列無序的、唯一的元素組合。

字典和集合的創建：

d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}

d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'})

d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')])

d4 = dict(name='jason', age=20, gender='male')

d1 == d2 == d3 ==d4

True

s1 = {1, 2, 3}

s2 = Set([1, 2, 3])

s1 == s2

True

set 并不支持索引操作，因為 set 本質上是一個哈希表，和列表不一樣

s = {1, 2, 3}

s[0]

Traceback (most recent call last):

File "", line 1, in

TypeError: 'set' object does not support indexing

對于字典，我們通常會根據鍵和值，進行升序或降序排序：

d = {'b': 1, 'a': 2, 'c': 10}

d_sorted_by_key = sorted(d.items(), key=lambda x: x[0]) # 根據字典鍵的升序排序

d_sorted_by_value = sorted(d.items(), key=lambda x: x[1]) # 根據字典值的升序排序

d_sorted_by_key

[('a', 2), ('b', 1), ('c', 10)]

d_sorted_by_value

[('b', 1), ('a', 2), ('c', 10)]

字典和集合性能

import time

# list version

def find_unique_price_using_list(products):

unique_price_list = []

for _, price in products: # A

if price not in unique_price_list: #B

unique_price_list.append(price)

return len(unique_price_list)

def find_unique_suing_set(products):

unique_price_set = set()

for _, price in products:

unique_price_set.add(price)

return len(unique_price_set)

id = [x for x in range(0, 100000)]

price = [x for x in range(2000000, 3000000)]

products = list(zip(id, price))

# 計算列表版本時間

start_using_list = time.perf_counter()

find_unique_price_using_list(products)

end_using_list = time.perf_counter()

print("time elapse using list : {}".format(end_using_list-start_using_list))

# 輸出

time elapse using list : 44.804451168

# 計算集合版本的時間

start_using_set = time.perf_counter()

find_unique_suing_set(products)

end_using_set = time.perf_counter()

print("time elapse using set: {}".format(end_using_set-start_using_set))

# 輸出

time elapse using set: 0.010326210999998864

你可以看到，僅僅十萬的數據量，兩者的速度差異就如此之大。更不用說上億乃至十億數據量了。

字典和集合的工作原理

字典和集合內部結構都是一張哈希表 對于字典而言，這張表存儲了哈希值（hash），鍵和值這 3 個元素。 對于集合而言，區別就是哈希表內沒有鍵和值的配對，只有單一的元素。

老版本的 python 的哈希結構如下所示：

entries = [

['--', '--', '--']

[-230273521, 'dob', '1999-01-01'],

['--', '--', '--'],

['--', '--', '--'],

[1231236123, 'name', 'mike'],

['--', '--', '--'],

[9371539127, 'gender', 'male']

]

不難想象，隨著哈希表的擴張，它會變得越來越稀疏。（為什么會越來越稀疏：哈希表為了保證其操作的有效性（查找、添加、刪除等等），都會 overallocate（保證留至少1/3的剩余空間）,但很多空間其實都沒有被利用，因此很稀疏。）

舉個例子，我們有這樣一個字典：

{'name': 'mike', 'dob': '1999-01-01', 'gender': 'male'}

那么它的存儲為類似下面的形式：

entries = [

['--', '--', '--']

[-230273521, 'dob', '1999-01-01'],

['--', '--', '--'],

['--', '--', '--'],

[1231236123, 'name', 'mike'],

['--', '--', '--'],

[9371539127, 'gender', 'male']

]

這樣的設計結構，很顯然非常浪費存儲空間。為了提高存儲空間的利用率，現在的哈希表除了字典本身的結構，會把索引和哈希值、鍵、值單獨分開，也就是下面的新結構：

Indices

----------------------------------------------------

None | index | None | None | index | None | index ...

----------------------------------------------------

Entries

--------------------

hash0 key0 value0

---------------------

hash1 key1 value1

---------------------

hash2 key2 value2

---------------------

...

---------------------

那么剛剛的這個例子，在新的哈希表結構下，就會變成下面這樣：

indices = [None, 1, None, None, 0, None, 2]

entries = [

[1231236123, 'name', 'mike'],

[-230273521, 'dob', '1999-01-01'],

[9371539127, 'gender', 'male']

] # 索引 indices 中的值，對應的是 entries 數組的位置

我們可以看到，空間利用率得到很大的提高。

插入操作

每次向字典或集合插入一個元素時，python 會首先計算鍵的哈希值（hash（key））,在和 mask = PyDicMinSize - 1做與操作，計算這個元素應該插入哈希表的位置 index = hash(key)&mask，如果哈希表此位置是空的，那么這個元素就會被插入其中。

如果此位置已被占用，Python 便會比較兩個元素的哈希值和鍵是否相等。 如果兩者都相等，則表明兩個元素已經存在，如果值不同，則更新值。 若兩者有一個不等，這種情況我們稱之為哈希沖突，意思是兩個元素的鍵不相等，但是哈希值相同。這種情況下，python 便會繼續尋找表中空余的位置，直到找到位置為止。

刪除操作，

python 會暫時對這個位置的元素，賦一個特殊的值，等到重新調整哈希表的大小時，再將其刪除。

不難理解，哈希沖突的發生，往往會降低字典和集合操作的速度。因此，為了保證其高效性，字典和集合內的哈希表，通常會保證其至少留有 1/3 的剩余空間。隨著元素的不停插入，當剩余空間不足 1/3 時，python 會重新獲取更大的內存空間，擴充哈希表。不過在這種情況下，表內的所有元素的位置都會被重新排放。

雖然哈希沖突和哈希表大小的調整，都會導致速度減緩，但是這種情況發生的次數極少，所以平均情況下，這仍能保證插入、查找和刪除的時間復雜度為 O(1)。

思考下面初始化字典的方式，哪一種更高效？

# Option A

d = {'name': 'jason', 'age': 20, 'gender': 'male'}

# Option B

d = dict({'name': 'jason', 'age': 20, 'gender': 'male'})

第一種更快，{} 是一個內置函數，不需要涉及 dict() 函數調用時的 stack 操作。字典的鍵可以是一個列表嗎，下面的代碼是否正確？

d = {'name': 'jason', ['education']: ['Tsinghua University', 'Stanford University']}

用列表作為 key 在 dict 中是不被允許的，因為列表是一個動態變化的數據結構，字典中的key要求是不可變的。如果是可變的 key ，那么隨著 key 的變化，這里就有可能有重復的 key，那么這就和字典的定義相違背。這里換成 tuple 是可行的。

總結

以上是生活随笔為你收集整理的python字典和集合双向索引_Python字典和集合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。