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
#統計時間需要用到 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) 鍵 (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'] ]通過對比可以發現，空間利用率得到很大的提高。
dic = {"name":1}
print(hash("name"))
setDemo = {1}
print(hash(1))
執行結果為：
8230115042008314683
1
具體遇到雜湊衝突時，各解決方法的具體含義可閱讀《雜湊表詳解》一節做詳細了解。
這裡的找到空位，表示雜湊表中沒有儲存目標元素。
O(1)。