淺談Python中字典和散列表以及散列衝突的解決

本篇文章帶給大家的內容是關於淺談Python中字典和散列表以及散列衝突的解決，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

Python 用散列表來實作 dict。

散列表其實是一個稀疏數組（總是有空白元素的陣列稱為稀疏數組）。在一般書中，散列表裡的單元通常叫做表元（bucket）。在 dict 的散列表當中，每個鍵值對都佔用一個表元，每個表元都有兩個部分，一個是對鍵的引用，一個是對值的引用。因為每個表元的大小一致，所以可以透過偏移量來讀取某個表元。

Python會設法保證大概還有三分之一的表元是空的，當快要達到這個閥值的時候，會進行擴容，將原散列表複製到一個更大的散列表裡。

如果要把一個物件放入到散列表裡，就先要計算這個元素鍵的雜湊值。這就要求鍵（key）必須是可散列的。

一個可散列的物件必須滿足以下條件：

支援 hash() 函數，並且透過 __hash__() 方法得到的雜湊值是不變的。

支援透過 __eq__() 方法來偵測相等性。

若 a == b 為真，則 hash(a) == hash(b) 也為真。

下面主要來說明一下散列表的演算法。

為了取得鍵 search_key 所對應的值 search_value，python 會先呼叫 hash(search_key) 計算 search_key 的雜湊值，把這個值最低的幾位數字當作偏移量，在散列表裡查找表元（具體取幾位，得看當前散列表的大小）。若找到的表元是空的，則拋出 KeyError 異常；若不為空，則表元裡會有一對 found_key:found_value，檢定 search_key 和 found_key 是否相等，若相等，則傳回 found_value。若不相等，這種情況稱為雜湊衝突。

為了解決雜湊衝突，演算法會在雜湊值中另外再取幾位，然後用特殊的方法處理一下，把得到的新數值作為偏移量在散列表中查找表元，若找到的表元是空的，則同樣拋出KeyError 異常；若非空，則比較鍵是否一致，一致則返回對應的值；若又發現散列衝突，則重複以上步驟。

新增元素跟上面的過程幾乎一樣，只不過在發現空表元的時候會放入這個新元素，不為空則為散列重複，繼續查找。

當往 dict 裡加入新元素並且發生了散列衝突的時候，新元素可能會被安排存放到另一個位置。於是就會發生下面的情況：dict([key1, value1], [key2, 值2]) 和 dict([key2, value2], [key1, 值1]) 兩個字典，在進行比較的時候是相等的，但如果 key1 和 key2 散列衝突，則這兩個鍵在字典裡的順序是不一樣的。

無論何時，往 dict 裡加入新的鍵，python 解析器都可能做出字典擴容的決定。擴容導致的結果就是要新建一個更大的散列表，並把字典裡已有的元素加到新的散列表裡。這個過程中可能發生新的雜湊衝突，導致新散列表中鍵的次序變化。如果在迭代一個字典的同時往裡面加入新的鍵，會發生什麼事？不湊巧擴容了，不湊巧鍵的次序變了，然後就 orz 了。

由於散列表必須是稀疏的，這導致它在空間上的消耗必然要大很多，這是典型的空間換時間。

以上是淺談Python中字典和散列表以及散列衝突的解決的詳細內容。更多資訊請關注PHP中文網其他相關文章！