字典和集合是進行過性能高度優化的數據結構，特別是對于查找、添加和刪除操作。本節將結合實例介紹它們在具體場景下的性能表現，以及與列表等其他數據結構的對比。
例如，有一個存儲產品信息（產品ID、名稱和價格）的列表，現在的需求是，借助某件產品的ID找出其價格。則實現代碼如下：
deffind_product_price(products,product_id):
forid,priceinproducts:
ifid==product_id:
returnprice
returnNone
products=[
(111,100),
(222,30),
(333,150)
]
print('Thepriceofproduct222is{}'.format(find_product_price(products,222)))
運行結果為：
Thepriceofproduct222is30
在上面程序的基礎上，如果列表有n個元素，因為查找的過程需要遍歷列表，那么最壞情況下的時間復雜度就為O(n)。即使先對列表進行排序，再使用二分查找算法，也需要O(logn)的時間復雜度，更何況列表的排序還需要O(nlogn)的時間。
但如果用字典來存儲這些數據，那么查找就會非常便捷高效，只需O(1)的時間復雜度就可以完成，因為可以直接通過鍵的哈希值，找到其對應的值，而不需要對字典做遍歷操作，實現代碼如下：
products={
111:100,
222:30,
333:150
}
print('Thepriceofproduct222is{}'.format(products[222]))
運行結果為：
Thepriceofproduct222is30
有些讀者可能對時間復雜度并沒有直觀的認識，沒關系，再給大家列舉一個實例。下面的代碼中，初始化了含有100,000個元素的產品，并分別計算出了使用列表和集合來統計產品價格數量的運行時間：
#統計時間需要用到time模塊中的函數，了解即可
importtime
deffind_unique_price_using_list(products):
unique_price_list=[]
for_,priceinproducts:#A
ifpricenotinunique_price_list:#B
unique_price_list.append(price)
returnlen(unique_price_list)
id=[xforxinrange(0,100000)]
price=[xforxinrange(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("timeelapseusinglist:{}".format(end_using_list-start_using_list))
#使用集合完成同樣的工作
deffind_unique_price_using_set(products):
unique_price_set=set()
for_,priceinproducts:
unique_price_set.add(price)
returnlen(unique_price_set)
#計算集合版本的時間
start_using_set=time.perf_counter()
find_unique_price_using_set(products)
end_using_set=time.perf_counter()
print("timeelapseusingset:{}".format(end_using_set-start_using_set))
運行結果為：
timeelapseusinglist:68.78650900000001
timeelapseusingset:0.010747099999989018
可以看到，僅僅十萬的數據量，兩者的速度差異就如此之大。而往往企業的后臺數據都有上億乃至十億數量級，因此如果使用了不合適的數據結構，很容易造成服務器的崩潰，不但影響用戶體驗，并且會給公司帶來巨大的財產損失。
那么，字典和集合為什么能如此高效，特別是查找、插入和刪除操作呢？
字典和集合的工作原理
字典和集合能如此高效，和它們內部的數據結構密不可分。不同于其他數據結構，字典和集合的內部結構都是一張哈希表：
對于字典而言，這張表存儲了哈希值（hash）、鍵和值這3個元素。
而對集合來說，哈希表內只存儲單一的元素。
對于之前版本的Python來說，它的哈希表結構如下所示：
哈希值(hash)鍵(key)值(value)
.|...
0|hash0key0value0
.|...
1|hash3key1value1
.|...
2|hash2key2value2
.|...
這種結構的弊端是，隨著哈希表的擴張，它會變得越來越稀疏。比如，有這樣一個字典：
{'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
--------------------
hash0key0value0
---------------------
hash3key1value1
---------------------
hash2key2value2
---------------------
...
---------------------
在此基礎上，上面的字典在新哈希表結構下的存儲形式為：
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會重新獲取更大的內存空間，擴充哈希表，與此同時，表內所有的元素位置都會被重新排放。