在Python中，字典是通過散列表或說哈希表實(shí)現(xiàn)的。字典也被稱為關(guān)聯(lián)數(shù)組，還稱為哈希數(shù)組等。也就是說，字典也是一個(gè)數(shù)組，但數(shù)組的索引是鍵經(jīng)過哈希函數(shù)處理后得到的散列值。哈希函數(shù)的目的是使鍵均勻地分布在數(shù)組中，并且可以在內(nèi)存中以O(shè)(1)的時(shí)間復(fù)雜度進(jìn)行尋址，從而實(shí)現(xiàn)快速查找和修改。哈希表中哈希函數(shù)的設(shè)計(jì)困難在于將數(shù)據(jù)均勻分布在哈希表中，從而盡量減少哈希碰撞和沖突。由于不同的鍵可能具有相同的哈希值，即可能出現(xiàn)沖突，高級(jí)的哈希函數(shù)能夠使沖突數(shù)目最小化。Python中并不包含這樣高級(jí)的哈希函數(shù)，幾個(gè)重要（用于處理字符串和整數(shù)）的哈希函數(shù)是常見的幾個(gè)類型。

通常情況下建立哈希表的具體過程如下：

數(shù)據(jù)添加：把key通過哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。

數(shù)據(jù)查詢：再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到數(shù)組的位置獲取value。

哈希函數(shù)就是一個(gè)映射，因此哈希函數(shù)的設(shè)定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即可。本質(zhì)上看哈希函數(shù)不可能做成一個(gè)一對(duì)一的映射關(guān)系，其本質(zhì)是一個(gè)多對(duì)一的映射，這也就引出了下面一個(gè)概念–哈希沖突或者說哈希碰撞。哈希碰撞是不可避免的，但是一個(gè)好的哈希函數(shù)的設(shè)計(jì)需要盡量避免哈希碰撞。

Python2中使用使用開放地址法解決沖突。

CPython使用偽隨機(jī)探測(cè)(pseudo-random probing)的散列表(hash table)作為字典的底層數(shù)據(jù)結(jié)構(gòu)。由于這個(gè)實(shí)現(xiàn)細(xì)節(jié)，只有可哈希的對(duì)象才能作為字典的鍵。字典的三個(gè)基本操作（添加元素，獲取元素和刪除元素）的平均事件復(fù)雜度為O(1)。

Python中所有不可變的內(nèi)置類型都是可哈希的。

可變類型（如列表，字典和集合）就是不可哈希的，因此不能作為字典的鍵。

常見的哈希碰撞解決方法：

1 開放尋址法（open addressing）

開放尋址法中，所有的元素都存放在散列表里，當(dāng)產(chǎn)生哈希沖突時(shí)，通過一個(gè)探測(cè)函數(shù)計(jì)算出下一個(gè)候選位置，如果下一個(gè)獲選位置還是有沖突，那么不斷通過探測(cè)函數(shù)往下找，直到找個(gè)一個(gè)空槽來(lái)存放待插入元素。

開放地址的意思是除了哈希函數(shù)得出的地址可用，當(dāng)出現(xiàn)沖突的時(shí)候其他的地址也一樣可用，常見的開放地址思想的方法有線性探測(cè)再散列，二次探測(cè)再散列等，這些方法都是在第一選擇被占用的情況下的解決方法。

2 再哈希法

這個(gè)方法是按順序規(guī)定多個(gè)哈希函數(shù)，每次查詢的時(shí)候按順序調(diào)用哈希函數(shù)，調(diào)用到第一個(gè)為空的時(shí)候返回不存在，調(diào)用到此鍵的時(shí)候返回其值。

3 鏈地址法

將所有關(guān)鍵字哈希值相同的記錄都存在同一線性鏈表中，這樣不需要占用其他的哈希地址，相同的哈希值在一條鏈表上，按順序遍歷就可以找到。

4 公共溢出區(qū)

其基本思想是：所有關(guān)鍵字和基本表中關(guān)鍵字為相同哈希值的記錄，不管他們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。

5 裝填因子α

一般情況下，處理沖突方法相同的哈希表，其平均查找長(zhǎng)度依賴于哈希表的裝填因子。哈希表的裝填因子定義為表中填入的記錄數(shù)和哈希表長(zhǎng)度的比值，也就是標(biāo)志著哈希表的裝滿程度。直觀看來(lái)，α越小，發(fā)生沖突的可能性就越小，反之越大。一般0.75比較合適，涉及數(shù)學(xué)推導(dǎo)。

在python中一個(gè)key-value是一個(gè)entry，

entry有三種狀態(tài)。

Unused： me_key == me_value == NULL

Unused是entry的初始狀態(tài)，key和value都為NULL。插入元素時(shí)，Unused狀態(tài)轉(zhuǎn)換成Active狀態(tài)。這是me_key為NULL的唯一情況。

Active： me_key != NULL and me_key != dummy 且 me_value != NULL

插入元素后，entry就成了Active狀態(tài)，這是me_value唯一不為NULL的情況，刪除元素時(shí)Active狀態(tài)刻轉(zhuǎn)換成Dummy狀態(tài)。

Dummy： me_key == dummy 且 me_value == NULL

此處的dummy對(duì)象實(shí)際上一個(gè)PyStringObject對(duì)象，僅作為指示標(biāo)志。Dummy狀態(tài)的元素可以在插入元素的時(shí)候?qū)⑺兂葾ctive狀態(tài)，但它不可能再變成Unused狀態(tài)。

為什么entry有Dummy狀態(tài)呢？這是因?yàn)椴捎瞄_放尋址法中，遇到哈希沖突時(shí)會(huì)找到下一個(gè)合適的位置，例如某元素經(jīng)過哈希計(jì)算應(yīng)該插入到A處，但是此時(shí)A處有元素的，通過探測(cè)函數(shù)計(jì)算得到下一個(gè)位置B，仍然有元素，直到找到位置C為止，此時(shí)ABC構(gòu)成了探測(cè)鏈，查找元素時(shí)如果hash值相同，那么也是順著這條探測(cè)鏈不斷往后找，當(dāng)刪除探測(cè)鏈中的某個(gè)元素時(shí)，比如B，如果直接把B從哈希表中移除，即變成Unused狀態(tài)，那么C就不可能再找到了，因?yàn)锳C之間出現(xiàn)了斷裂的現(xiàn)象，正是如此才出現(xiàn)了第三種狀態(tài)---Dummy，Dummy是一種類似的偽刪除方式，保證探測(cè)鏈的連續(xù)性。

提示

一般情況下普通的順序表數(shù)組存儲(chǔ)結(jié)構(gòu)也可以認(rèn)為是簡(jiǎn)單的哈希表，雖然沒有采用哈希函數(shù)（取余），但同樣可以在O(1)時(shí)間內(nèi)進(jìn)行查找和修改。但是這種方法存在兩個(gè)問題：擴(kuò)展性不強(qiáng)；浪費(fèi)空間。

set集合和dict一樣也是基于散列表的，只是他的表元只包含鍵的引用，而沒有對(duì)值的引用，其他的和dict基本上是一致的，所以在此就不再多說了。并且dict要求鍵必須是能被哈希的不可變對(duì)象，因此普通的set無(wú)法作為dict的鍵，必須選擇被“凍結(jié)”的不可變集合類：frozenset。顧名思義，一旦初始化，集合內(nèi)數(shù)據(jù)不可修改。

以上這篇Python字典底層實(shí)現(xiàn)原理詳解就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論