如何理解Python中的集合和字典？

字典和集合是進行過性能高度優化的數據結構，特別是對于查找、添加和刪除操作。本節將結合實例介紹它們在具體場景下的性能表現，以及與列表等其他數據結構的對比。

例如，有一個存儲產品信息（產品 ID、名稱和價格）的列表，現在的需求是，借助某件產品的ID找出其價格。則實現代碼如下：

def find_product_price(products, product_id):

for id, price in products:

if id == product_id:

return price

return None

products = [

(111, 100),

(222, 30),

(333, 150)

]

print('The price of product 222 is {}'.format(find_product_price(products, 222)))

運行結果為：

The price of product 222 is 30

在上面程序的基礎上，如果列表有 n 個元素，因為查找的過程需要遍歷列表，那么最壞情況下的時間復雜度就為 O(n)。即使先對列表進行排序，再使用二分查找算法，也需要 O(logn) 的時間復雜度，更何況列表的排序還需要 O(nlogn) 的時間。

但如果用字典來存儲這些數據，那么查找就會非常便捷高效，只需 O(1) 的時間復雜度就可以完成，因為可以直接通過鍵的哈希值，找到其對應的值，而不需要對字典做遍歷操作，實現代碼如下：

products = {

111: 100,

222: 30,

333: 150

}

print('The price of product 222 is {}'.format(products[222]))

運行結果為：

The price of product 222 is 30

有些讀者可能對時間復雜度并沒有直觀的認識，沒關系，再給大家列舉一個實例。下面的代碼中，初始化了含有 100,000 個元素的產品，并分別計算出了使用列表和集合來統計產品價格數量的運行時間：

#統計時間需要用到 time 模塊中的函數，了解即可

import time

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)

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

price = [x for x in range(200000, 300000)]

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))

#使用集合完成同樣的工作

def find_unique_price_using_set(products):

unique_price_set = set()

for _, price in products:

unique_price_set.add(price)

return len(unique_price_set)

# 計算集合版本的時間

start_using_set = time.perf_counter()

find_unique_price_using_set(products)

end_using_set = time.perf_counter()

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

運行結果為：

time elapse using list: 68.78650900000001

time elapse using set: 0.010747099999989018

可以看到，僅僅十萬的數據量，兩者的速度差異就如此之大。而往往企業的后臺數據都有上億乃至十億數量級，因此如果使用了不合適的數據結構，很容易造成服務器的崩潰，不但影響用戶體驗，并且會給公司帶來巨大的財產損失。

那么，字典和集合為什么能如此高效，特別是查找、插入和刪除操作呢？

字典和集合的工作原理

字典和集合能如此高效，和它們內部的數據結構密不可分。不同于其他數據結構，字典和集合的內部結構都是一張哈希表：

對于字典而言，這張表存儲了哈希值（hash）、鍵和值這 3 個元素。

而對集合來說，哈希表內只存儲單一的元素。

對于之前版本的 Python 來說，它的哈希表結構如下所示：

哈希值 (hash) 鍵 (key) 值 (value)

. | ...

0 | hash0 key0 value0

. | ...

1 | hash1 key1 value1

. | ...

2 | hash2 key2 value2

. | ...

這種結構的弊端是，隨著哈希表的擴張，它會變得越來越稀疏。比如，有這樣一個字典：

{'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']

]

通過對比可以發現，空間利用率得到很大的提高。

清楚了具體的設計結構，接下來再分析一下如何使用哈希表完成對數據的插入、查找和刪除操作。

哈希表插入數據

當向字典中插入數據時，Python 會首先根據鍵（key）計算出對應的哈希值（通過 hash(key) 函數），而向集合中插入數據時，Python會根據該元素本身計算對應的哈希值（通過 hash(valuse) 函數）。

例如：

dic = {"name":1}

print(hash("name"))

setDemo = {1}

print(hash(1))

運行結果為：

8230115042008314683

1

得到哈希值（例如為 hash）之后，再結合字典或集合要存儲數據的個數（例如 n），就可以得到該元素應該插入到哈希表中的位置（比如，可以用 hash%n 的方式）。

如果哈希表中此位置是空的，那么此元素就可以直接插入其中；反之，如果此位置已被其他元素占用，那么 Python 會比較這兩個元素的哈希值和鍵是否相等：

如果相等，則表明該元素已經存在，再比較他們的值，不相等就進行更新；

如果不相等，這種情況稱為哈希沖突（即兩個元素的鍵不同，但求得的哈希值相同）。這種情況下，Python 會使用開放定址法、再哈希法等繼續尋找哈希表中空余的位置，直到找到位置。

具體遇到哈希沖突時，各解決方法的具體含義可閱讀《哈希表詳解》一節做詳細了解。

哈希表查找數據

在哈希表中查找數據，和插入操作類似，Python 會根據哈希值，找到該元素應該存儲到哈希表中的位置，然后和該位置的元素比較其哈希值和鍵（集合直接比較元素值）：

如果相等，則證明找到；

反之，則證明當初存儲該元素時，遇到了哈希沖突，需要繼續使用當初解決哈希沖突的方法進行查找，直到找到該元素或者找到空位為止。

這里的找到空位，表示哈希表中沒有存儲目標元素。

哈希表刪除元素

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

需要注意的是，哈希沖突的發生往往會降低字典和集合操作的速度。因此，為了保證其高效性，字典和集合內的哈希表，通常會保證其至少留有 1/3 的剩余空間。隨著元素的不停插入，當剩余空間小于 1/3 時，Python 會重新獲取更大的內存空間，擴充哈希表，與此同時，表內所有的元素位置都會被重新排放。