你們有沒(méi)有想過(guò) Python/ target=_blank class=infotextkey>Python 字典為何如此快速和可靠？答案是它們建立在另一種技術(shù)之上：哈希表。
了解 Python 哈希表的工作原理將使您更深入地了解字典的工作原理，這對(duì)于您理解 Python 來(lái)說(shuō)是一個(gè)很大的優(yōu)勢(shì)，因?yàn)樽值湓?Python 中幾乎無(wú)處不在。
哈希函數(shù)永久鏈接
在介紹哈希表及其 Python 實(shí)現(xiàn)之前，您必須了解什么是哈希函數(shù)及其工作原理。
哈希函數(shù)是一種可以將任意長(zhǎng)度的數(shù)據(jù)映射為固定長(zhǎng)度值的函數(shù)，稱(chēng)為哈希。
哈希函數(shù)具有三大特點(diǎn)：
- 它們的計(jì)算速度很快：計(jì)算一段數(shù)據(jù)的哈希值必須是一個(gè)快速的操作。
- 它們是確定性的：相同的字符串將始終產(chǎn)生相同的哈希值。
- 它們產(chǎn)生固定長(zhǎng)度的值：無(wú)論您的輸入是一字節(jié)、十字節(jié)還是一萬(wàn)字節(jié)，生成的散列將始終具有固定的預(yù)定長(zhǎng)度。
哈希函數(shù)中很常見(jiàn)的另一個(gè)特征是它們通常是單向函數(shù)：由于函數(shù)中實(shí)現(xiàn)了自愿數(shù)據(jù)丟失，您可以從字符串中獲取哈希，但無(wú)法從哈希中獲取原始字符串。這并不是每個(gè)哈希函數(shù)的強(qiáng)制功能，但當(dāng)它們必須具有加密安全性時(shí)就變得很重要。
一些流行的哈希算法有MD5、SHA-1、SHA-2、NTLM。
哈希的常見(jiàn)用法永久鏈接
有很多東西依賴(lài)于哈希，哈希表只是其中之一。哈希的其他常見(jiàn)用法是出于加密和安全原因。
一個(gè)具體的例子是當(dāng)您嘗試從互聯(lián)網(wǎng)下載開(kāi)源軟件時(shí)。通常，您還會(huì)發(fā)現(xiàn)一個(gè)伴隨文件，它是該文件的簽名。這個(gè)簽名只是原始文件的哈希值，它非常有用，因?yàn)槿绻约河?jì)算原始文件的哈希值并與網(wǎng)站提供的簽名進(jìn)行檢查，您可以確定您下載的文件沒(méi)有已被篡改。
哈希的另一個(gè)常見(jiàn)用途是存儲(chǔ)用戶(hù)密碼。您是否曾經(jīng)問(wèn)過(guò)自己，為什么當(dāng)您忘記某個(gè)網(wǎng)站的密碼并嘗試恢復(fù)該密碼時(shí)，該網(wǎng)站通常會(huì)讓您選擇另一個(gè)密碼，而不是返回您選擇的原始密碼？答案是該網(wǎng)站不會(huì)存儲(chǔ)您選擇的整個(gè)密碼，而僅存儲(chǔ)其哈希值。
這樣做是出于安全原因，因?yàn)槿绻承┖诳瞳@得了網(wǎng)站數(shù)據(jù)庫(kù)的訪問(wèn)權(quán)限，他們將無(wú)法知道您的密碼，而只能知道您密碼的哈希值，并且由于哈希函數(shù)通常是單向函數(shù)，因此您可以確定他們將永遠(yuǎn)無(wú)法從哈希值開(kāi)始獲取您的密碼。
Python hash()函數(shù)永久鏈接
Python有一個(gè)內(nèi)置函數(shù)來(lái)生成對(duì)象的哈希值，即函數(shù)hash()。該函數(shù)接受一個(gè)對(duì)象作為輸入，并將哈希值作為整數(shù)返回。
在內(nèi)部，此函數(shù)調(diào)用.__hash__()輸入對(duì)象的方法，因此如果您想讓自定義類(lèi)可哈希，您所要做的就是實(shí)現(xiàn)該方法以.__hash__()根據(jù)對(duì)象的內(nèi)部狀態(tài)返回整數(shù)。
現(xiàn)在，嘗試啟動(dòng) Python 解釋器并hash()稍微使用一下該函數(shù)。對(duì)于第一個(gè)實(shí)驗(yàn)，嘗試對(duì)一些數(shù)值進(jìn)行哈希處理：
>>> hash(1)
1
>>> hash(10)
10
>>> hash(10.00)
10
>>> hash(10.01)
230584300921368586
>>> hash(-10.01)
-230584300921368586
如果您想知道為什么這些散列似乎具有不同的長(zhǎng)度，請(qǐng)記住 Pythonhash()函數(shù)返回整數(shù)對(duì)象，這些對(duì)象在標(biāo)準(zhǔn) 64 位 Python 3 解釋器上始終用 24 個(gè)字節(jié)表示。
如您所見(jiàn)，默認(rèn)情況下，整數(shù)值的哈希值就是該值本身。請(qǐng)注意，無(wú)論您要散列的值的類(lèi)型如何，這都有效，因此整數(shù)1和浮點(diǎn)數(shù)1.0具有相同的散列：1。
這有什么特別之處？好吧，這顯示了您之前學(xué)到的知識(shí)，即哈希函數(shù)通常是單向函數(shù)：如果兩個(gè)不同的對(duì)象可能具有相同的哈希值，則不可能執(zhí)行從哈希值開(kāi)始并返回到原始對(duì)象的相反過(guò)程。在這種情況下，有關(guān)原始哈希對(duì)象的類(lèi)型的信息已經(jīng)丟失。
通過(guò)哈希數(shù)字您可以注意到的另一件有趣的事情是，十進(jìn)制數(shù)具有與其值不同的哈希值，并且負(fù)值具有負(fù)哈希值。但是，如果您嘗試對(duì)獲得的十進(jìn)制值的相同數(shù)字進(jìn)行哈希處理，會(huì)發(fā)生什么情況？答案是您得到相同的哈希值，如以下示例所示：
>>> hash(0.1)
230584300921369408
>>> hash(230584300921369408)
230584300921369408
>>> hash(0.1) == hash(230584300921369408)
True
如您所見(jiàn)，整數(shù) number 的哈希值230584300921369408與 number 的哈希值相同0.1。如果您想到之前學(xué)到的關(guān)于哈希函數(shù)的知識(shí)，這是完全正常的，因?yàn)槿绻梢詫?duì)任何數(shù)字或任何字符串進(jìn)行哈希處理以獲得固定長(zhǎng)度值，因?yàn)槟荒軗碛杏晒潭ㄩL(zhǎng)度值表示的無(wú)限值，這意味著必須有重復(fù)的值。它們實(shí)際上是存在的，稱(chēng)為碰撞。當(dāng)兩個(gè)對(duì)象具有相同的哈希值時(shí)，就說(shuō)它們發(fā)生了碰撞。
對(duì)字符串進(jìn)行哈希處理與對(duì)數(shù)值進(jìn)行哈希處理沒(méi)有太大區(qū)別。啟動(dòng) Python 解釋器并嘗試對(duì)字符串進(jìn)行哈希處理：
>>> hash("Bad Behaviour")
7164800052134507161
正如您所看到的，字符串是可散列的并且也會(huì)生成數(shù)值，但是如果您嘗試運(yùn)行此命令，您可能會(huì)發(fā)現(xiàn)您的 Python 解釋器沒(méi)有返回與上面示例相同的結(jié)果。這是因?yàn)閺?Python 3.3 開(kāi)始，字符串和字節(jié)對(duì)象的值在哈希過(guò)程之前會(huì)使用隨機(jī)值進(jìn)行加鹽。這意味著在進(jìn)行哈希處理之前，字符串的值會(huì)在每次解釋器啟動(dòng)時(shí)使用隨機(jī)值進(jìn)行修改。如果要覆蓋此行為，可以PYTHONHASHSEED在啟動(dòng)解釋器之前將環(huán)境變量設(shè)置為大于零的整數(shù)值。
正如您所料，這是一項(xiàng)安全功能。之前您了解到，網(wǎng)站通常存儲(chǔ)密碼的哈希值而不是密碼本身，以防止對(duì)網(wǎng)站數(shù)據(jù)庫(kù)的攻擊竊取所有網(wǎng)站密碼。如果網(wǎng)站僅存儲(chǔ)計(jì)算出的哈希值，則攻擊者可能很容易知道原始密碼是什么。他們只需要獲取大量常用密碼（網(wǎng)絡(luò)上充滿了這些列表）并計(jì)算其相應(yīng)的哈希值即可獲得通常稱(chēng)為彩虹表的內(nèi)容。
通過(guò)使用彩虹表，攻擊者可能無(wú)法獲取數(shù)據(jù)庫(kù)中的每個(gè)密碼，但仍然能夠竊取其中的絕大多數(shù)。為了防止這種攻擊，一個(gè)好主意是在對(duì)密碼進(jìn)行哈希處理之前對(duì)密碼進(jìn)行加鹽，即在計(jì)算哈希值之前使用隨機(jī)值修改密碼。
從 Python 3.3 開(kāi)始，解釋器默認(rèn)在散列之前對(duì)每個(gè)字符串和字節(jié)對(duì)象加鹽，以防止可能的 DOS 攻擊，正如 Scott Crosby 和 Dan Wallach 在2003 年論文中所演示的那樣。
DOS 攻擊（DOS 代表拒絕服務(wù)）是一種攻擊者故意耗盡計(jì)算機(jī)系統(tǒng)資源，使系統(tǒng)無(wú)法再向客戶(hù)端提供服務(wù)的攻擊。在 Scott Crosby 演示的這個(gè)特定攻擊案例中，攻擊可能會(huì)向目標(biāo)系統(tǒng)注入大量散列沖突的數(shù)據(jù)，從而使目標(biāo)系統(tǒng)使用更多的計(jì)算能力來(lái)解決沖突。
Python 可哈希類(lèi)型永久鏈接
所以此時(shí)，您可能想知道是否有任何 Python 類(lèi)型是可哈希的。這個(gè)問(wèn)題的答案是否定的，默認(rèn)情況下，Python 中只有不可變類(lèi)型是可哈希的。如果您使用不可變的容器（如元組），內(nèi)容也應(yīng)該是不可變的，以便可散列。
嘗試在 Python 中獲取不可哈希類(lèi)型的哈希值，您將從TypeError解釋器中獲取 a ，如以下示例所示：
>>> hash(["R","e","a","l","P","y","t","h","o","n"])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
但是，每個(gè)自定義定義的對(duì)象在 Python 中都是可哈希的，并且默認(rèn)情況下其哈希值源自其 id。這意味著同一類(lèi)的兩個(gè)不同實(shí)例默認(rèn)情況下具有不同的哈希值，如下例所示：
>>> class Car():
... velocity = 0
... direction = 0
... damage = 0
...
>>> first_car = Car()
>>> second_car = Car()
>>> hash(first_car)
274643597
>>> hash(second_car)
274643604
正如您所看到的，默認(rèn)情況下同一自定義對(duì)象的兩個(gè)不同實(shí)例具有不同的哈希值。但是，可以通過(guò).__hash__()在自定義類(lèi)中實(shí)現(xiàn)方法來(lái)修改此行為。
哈希表永久鏈接
現(xiàn)在您知道什么是哈希函數(shù)，您可以開(kāi)始檢查哈希表了。哈希表是一種數(shù)據(jù)結(jié)構(gòu)，允許您存儲(chǔ)鍵值對(duì)的集合。
在哈希表中，每個(gè)鍵值對(duì)的鍵必須是可哈希的，因?yàn)榇鎯?chǔ)的鍵值對(duì)是通過(guò)使用其鍵的哈希來(lái)索引的。哈希表非常有用，因?yàn)椴檎冶碇性厮璧钠骄噶顢?shù)與表本身中存儲(chǔ)的元素?cái)?shù)無(wú)關(guān)。這意味著即使您的表增長(zhǎng)十倍或一萬(wàn)倍，查找特定元素的整體速度也不會(huì)受到影響。
哈希表通常是通過(guò)創(chuàng)建可變數(shù)量的存儲(chǔ)桶來(lái)實(shí)現(xiàn)的，這些存儲(chǔ)桶將包含您的數(shù)據(jù)，并通過(guò)散列它們的鍵來(lái)索引這些數(shù)據(jù)。鍵的哈希值將確定用于該特定數(shù)據(jù)塊的正確存儲(chǔ)桶。
在下面的示例中，您可以找到 Python 中基本哈希表的實(shí)現(xiàn)。這只是一個(gè)實(shí)現(xiàn)，讓您了解哈希表如何工作，因?yàn)槟院髸?huì)知道，在 Python 中，無(wú)需創(chuàng)建哈希表的自定義實(shí)現(xiàn)，因?yàn)樗鼈兪亲鳛樽值鋵?shí)現(xiàn)的。讓我們看看這個(gè)實(shí)現(xiàn)是如何工作的：
import pprint
class Hashtable:
def __init__(self, elements):
self.bucket_size = len(elements)
self.buckets = [[] for i in range(self.bucket_size)]
self._assign_buckets(elements)
def _assign_buckets(self, elements):
for key, value in elements:
hashed_value = hash(key)
index = hashed_value % self.bucket_size
self.buckets[index].Append((key, value))
def get_value(self, input_key):
hashed_value = hash(input_key)
index = hashed_value % self.bucket_size
bucket = self.buckets[index]
for key, value in bucket:
if key == input_key:
return(value)
return None
def __str__(self):
return pprint.pformat(self.buckets) # here pformat is used to return a printable representation of the object
if __name__ == "__mAIn__":
capitals = [
('France', 'Paris'),
('United States', 'Washington D.C.'),
('Italy', 'Rome'),
('Canada', 'Ottawa')
]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")
查看for從第 9 行開(kāi)始的循環(huán)。對(duì)于哈希表的每個(gè)元素，此代碼計(jì)算鍵的哈希值（第 10 行），根據(jù)哈希值計(jì)算元素在存儲(chǔ)桶中的位置（第 11 行）并添加一個(gè)元組在桶中（第 12 行）。
PYTHONHASHSEED將環(huán)境變量設(shè)置為值后嘗試運(yùn)行上面的示例46，您將得到以下輸出，其中兩個(gè)存儲(chǔ)桶為空，另外兩個(gè)存儲(chǔ)桶各包含兩個(gè)鍵值對(duì)：
[[('United States', 'Washington D.C.'), ('Canada', 'Ottawa')],
[],
[],
[('France', 'Paris'), ('Italy', 'Rome')]]
The capital of Italy is Rome
請(qǐng)注意，如果您嘗試在未設(shè)置PYTHONHASHSEED變量的情況下運(yùn)行程序，您可能會(huì)得到不同的結(jié)果，因?yàn)槟呀?jīng)知道 Python 中的哈希函數(shù)，從 Python 3.3 開(kāi)始，在哈希過(guò)程之前使用隨機(jī)種子對(duì)每個(gè)字符串加鹽。
在上面的示例中，您實(shí)現(xiàn)了一個(gè) Python 哈希表，該哈希表采用元組列表作為輸入，并將它們組織在多個(gè)等于輸入列表長(zhǎng)度的存儲(chǔ)桶中，并使用模運(yùn)算符來(lái)分配表中的哈希值。
但是，正如您在輸出中看到的，您有兩個(gè)空桶，而另外兩個(gè)桶各有兩個(gè)不同的值。當(dāng)發(fā)生這種情況時(shí)，就說(shuō)Python 哈希表中存在沖突。
使用標(biāo)準(zhǔn)庫(kù)的hash()函數(shù)，哈希表中的沖突是不可避免的。您可以決定使用更多數(shù)量的桶并降低發(fā)生碰撞的風(fēng)險(xiǎn)，但您永遠(yuǎn)無(wú)法將風(fēng)險(xiǎn)降低到零。
此外，您要處理的存儲(chǔ)桶數(shù)量越多，浪費(fèi)的空間就越多。要測(cè)試這一點(diǎn)，您可以簡(jiǎn)單地使用兩倍于輸入列表長(zhǎng)度的存儲(chǔ)桶數(shù)量來(lái)更改前一個(gè)示例的存儲(chǔ)桶大?。?/p>
```python hl_lines=”3” class Hashtable: def init (self, elements): self.bucket_size = len(elements) * 2 self.buckets = [[] for i in range(self.bucket_size)] self._assign_buckets （元素）
Running this example, I ended up with a better distribution of the input data, but I had however a collision and five unused buckets:
```console
[[],
[],
[],
[('Canada', 'Ottawa')],
[],
[],
[('United States', 'Washington D.C.'), ('Italy', 'Rome')],
[('France', 'Paris')]]
The capital of Italy is Rome
正如您所看到的，兩個(gè)哈希發(fā)生沖突并已被插入到同一個(gè)存儲(chǔ)桶中。
由于沖突通常是不可避免的，因此要實(shí)現(xiàn)哈希表，還需要實(shí)現(xiàn)沖突解決方法。解決哈希表中沖突的常見(jiàn)策略是：
- 開(kāi)放尋址
- 單獨(dú)鏈接
單獨(dú)的鏈接是您在上面的示例中已經(jīng)實(shí)現(xiàn)的鏈接，它包括使用另一個(gè)數(shù)據(jù)結(jié)構(gòu)在同一存儲(chǔ)桶中創(chuàng)建值鏈。在該示例中，您使用了一個(gè)嵌套列表，在過(guò)度占用的存儲(chǔ)桶中查找特定值時(shí)必須完全掃描該列表。
在開(kāi)放尋址策略中，如果您應(yīng)該使用的存儲(chǔ)桶繁忙，您只需不斷尋找要使用的新存儲(chǔ)桶即可。要實(shí)現(xiàn)此解決方案，您需要對(duì)如何將存儲(chǔ)桶分配給新元素以及如何檢索鍵的值進(jìn)行一些更改。從該_assign_buckets()函數(shù)開(kāi)始，您必須使用默認(rèn)值初始化存儲(chǔ)桶，并繼續(xù)尋找空存儲(chǔ)桶（如果您應(yīng)該使用的存儲(chǔ)桶已被占用）：
def _assign_buckets(self, elements):
self.buckets = [None] * self.bucket_size
for key, value in elements:
hashed_value = hash(key)
index = hashed_value % self.bucket_size
while self.buckets[index] is not None:
print(f"The key {key} collided with {self.buckets[index]}")
index = (index + 1) % self.bucket_size
self.buckets[index] = ((key, value))
None正如你所看到的，所有的桶在賦值之前都被設(shè)置為默認(rèn)值，并且while循環(huán)不斷尋找一個(gè)空的桶來(lái)存儲(chǔ)數(shù)據(jù)。
由于存儲(chǔ)桶的分配發(fā)生了變化，檢索過(guò)程也應(yīng)該發(fā)生變化，因?yàn)樵谠揼et_value()方法中，您現(xiàn)在需要檢查鍵的值，以確保您找到的數(shù)據(jù)是您正在尋找的數(shù)據(jù)：
def get_value(self, input_key):
hashed_value = hash(input_key)
index = hashed_value % self.bucket_size
while self.buckets[index] is not None:
key,value = self.buckets[index]
if key == input_key:
return value
index = (index + 1) % self.bucket_size
在查找過(guò)程中，在該 get_value()方法中，您使用該None值來(lái)檢查何時(shí)需要停止查找鍵，然后檢查數(shù)據(jù)的鍵以確保返回正確的值。
運(yùn)行上面的示例，鍵Italy與先前插入的元素 ( France) 發(fā)生碰撞，因此已被重新定位到第一個(gè)可用的空閑存儲(chǔ)桶。然而，搜索Italy按預(yù)期進(jìn)行：
The key Italy collided with ('France', 'Paris')
[None,
None,
('Canada', 'Ottawa'),
None,
('France', 'Paris'),
('Italy', 'Rome'),
None,
('United States', 'Washington D.C.')]
The capital of Italy is Rome
開(kāi)放尋址策略的主要問(wèn)題是，如果您還必須處理表中元素的刪除，則需要執(zhí)行邏輯刪除而不是物理刪除，因?yàn)槿绻鷦h除了在沖突期間占用存儲(chǔ)桶的值，則另一個(gè)值將被刪除。碰撞的元素永遠(yuǎn)不會(huì)被發(fā)現(xiàn)。
在我們前面的示例中，Italy與先前插入的元素 ( France) 發(fā)生碰撞，因此它已被重新定位到下一個(gè)存儲(chǔ)桶，因此刪除該France元素將導(dǎo)致Italy無(wú)法訪問(wèn)，因?yàn)樗徽加闷渥匀荒繕?biāo)存儲(chǔ)桶，這對(duì)于解釋器來(lái)說(shuō)似乎是空的。
因此，當(dāng)使用開(kāi)放尋址策略時(shí)，要?jiǎng)h除一個(gè)元素，您必須將其存儲(chǔ)桶替換為虛擬值，這向解釋器表明，必須將其視為已刪除以進(jìn)行新插入，但必須將其用于檢索目的。
字典：實(shí)現(xiàn) Python 哈希表永久鏈接
現(xiàn)在您已經(jīng)了解了什么是哈希表，讓我們來(lái)看看它們最重要的 Python 實(shí)現(xiàn)：字典。Python 中的字典是使用哈希表和開(kāi)放尋址沖突解決方法構(gòu)建的。
您已經(jīng)知道字典是鍵值對(duì)的集合，因此要定義字典，您需要提供用大括號(hào)括起來(lái)的以逗號(hào)分隔的鍵值對(duì)列表，如下例所示：
>>> chess_players = {
... "Carlsen": 2863,
... "Caruana": 2835,
... "Ding": 2791,
... "Nepomniachtchi": 2784,
... "Vachier-Lagrave": 2778,
... }
在這里，您創(chuàng)建了一個(gè)名為 的字典chess_players，其中包含世界上排名前五的國(guó)際象棋棋手及其實(shí)際等級(jí)。
要檢索特定值，您只需使用方括號(hào)指定鍵：
>>> chess_players["Nepomniachtchi"]
2784
如果嘗試訪問(wèn)不存在的元素，Python 解釋器會(huì)拋出異常Key Error：
>>> chess_players["Mastromatteo"]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'Mastromatteo'
要迭代整個(gè)字典，您可以使用.items()方法，該方法返回元組中所有鍵值對(duì)的可迭代對(duì)象：
>>> for (k, v) in chess_players.items():
... print(k,v)
...
Carlsen 2863
Caruana 2835
Ding 2791
Nepomniachtchi 2784
Vachier-Lagrave 2778
要迭代 Python 字典的鍵或值，您也可以使用.keys()或方法：.values()
>>> chess_players.keys()
dict_keys(["Carlsen", "Caruana", "Ding", "Nepomniachtchi", "Vachier-Lagrave"])
>>> chess_players.values()
dict_values([2863, 2835, 2791, 2784, 2778])
要將另一個(gè)元素插入字典中，您只需為新鍵分配一個(gè)值：
>>> chess_players["Grischuk"] = 2777
>>> chess_players
{'Carlsen': 2863, 'Caruana': 2835, 'Ding': 2791, 'Nepomniachtchi': 2784, 'Vachier-Lagrave': 2778, 'Grischuk': 2777}
要更新現(xiàn)有鍵的值，只需為先前插入的鍵分配不同的值即可。
請(qǐng)注意，由于字典是建立在哈希表之上的，因此您只能插入鍵為hashable 的元素。如果元素的鍵不可散列（例如列表），解釋器會(huì)拋出異常TypeError：
>>> my_list = ["Giri", "Mamedyarov"]
chess_players[my_list] = 2764
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
要?jiǎng)h除元素，您需要使用以下del語(yǔ)句，指定要?jiǎng)h除的鍵：
>>> del chess_players["Grischuk"]
>>> chess_players
{'Carlsen': 2863, 'Caruana': 2835, 'Ding': 2791, 'Nepomniachtchi': 2784, 'Vachier-Lagrave': 2778}
刪除條目不會(huì)刪除字典中的實(shí)際值，它只是用虛擬值替換鍵，以便開(kāi)放尋址沖突解決方法將繼續(xù)工作，但解釋器會(huì)為您處理所有這些復(fù)雜性，忽略已刪除的元素。
Python 哈希表的 Pythonic 實(shí)現(xiàn)永久鏈接
現(xiàn)在您知道字典是 Python 哈希表，但您可能想知道其實(shí)現(xiàn)原理是如何工作的，因此在本章中，我將嘗試為您提供一些有關(guān) Python 哈希表實(shí)際實(shí)現(xiàn)的信息。
請(qǐng)記住，我在這里提供的信息基于最新版本的 Python，因?yàn)?Python 3.6 字典已經(jīng)發(fā)生了很大變化，現(xiàn)在更小，更快，甚至更強(qiáng)大，因?yàn)樗鼈儸F(xiàn)在是插入有序的（插入有序保證已已在 Python 3.6 中實(shí)現(xiàn)，但在 Python 3.7 中已被 Guido 正式認(rèn)可）。
嘗試創(chuàng)建一個(gè)空的Python字典并檢查它的大小，你會(huì)發(fā)現(xiàn)一個(gè)空的Python字典占用了240字節(jié)的內(nèi)存：
>>> import sys
>>> my_dict = {}
>>> sys.getsizeof(my_dict)
240
通過(guò)運(yùn)行這個(gè)例子可以看到，Python字典的基本占用是240字節(jié)。但如果您決定添加一個(gè)值會(huì)發(fā)生什么？嗯，這可能看起來(lái)很奇怪，但大小并沒(méi)有改變：
>>> my_dict["a"] = 100
>>> sys.getsizeof(my_dict)
240
那么，為什么字典的大小沒(méi)有改變呢？因?yàn)閺?Python 3.6 開(kāi)始，值存儲(chǔ)在不同的數(shù)據(jù)結(jié)構(gòu)中，并且字典僅包含指向?qū)嶋H值存儲(chǔ)位置的指針。此外，當(dāng)您創(chuàng)建一個(gè)空字典時(shí)，它會(huì)開(kāi)始創(chuàng)建一個(gè)包含 8 個(gè)存儲(chǔ)桶、長(zhǎng)度僅為 240 字節(jié)的 Python 哈希表，因此字典中的第一個(gè)元素的大小根本沒(méi)有改變。
現(xiàn)在嘗試添加更多元素并查看字典的行為方式，您將看到字典增長(zhǎng)：
>>> for i in range(20):
... my_dict[i] = 100
... print(f"elements = {i+1} size = {sys.getsizeof(my_dict)}")
...
elements = 1 size = 240
elements = 2 size = 240
elements = 3 size = 240
elements = 4 size = 240
elements = 5 size = 240
elements = 6 size = 368
elements = 7 size = 368
elements = 8 size = 368
elements = 9 size = 368
elements = 10 size = 368
elements = 11 size = 648
elements = 12 size = 648
elements = 13 size = 648
elements = 14 size = 648
elements = 15 size = 648
elements = 16 size = 648
elements = 17 size = 648
elements = 18 size = 648
elements = 19 size = 648
elements = 20 size = 648
正如您所看到的，在插入第六個(gè)和第十一個(gè)元素后，字典變大了，但為什么呢？因?yàn)闉榱耸刮覀兊?Python 哈希表更快并減少?zèng)_突，解釋器在字典已滿三分之二時(shí)會(huì)不斷調(diào)整字典的大小。
現(xiàn)在，嘗試刪除字典中的所有元素，一次一個(gè)，完成后再次檢查大小，你會(huì)發(fā)現(xiàn)即使字典為空，空間也沒(méi)有被釋放：
>>> keys = list(my_dict.keys())
>>> for key in keys:
... del my_dict[key]
...
>>> my_dict
{}
>>> sys.getsizeof(my_dict)
648
發(fā)生這種情況的原因是，由于字典的內(nèi)存占用非常小，并且在使用字典時(shí)刪除并不頻繁，因此解釋器寧愿浪費(fèi)一點(diǎn)空間，也不愿在每次刪除后動(dòng)態(tài)調(diào)整字典的大小。但是，如果通過(guò)調(diào)用該.clear()方法清空字典，由于這是批量刪除，因此會(huì)釋放空間，并且字典大小將達(dá)到最小值 72 字節(jié)：
>>> my_dict.clear()
>>> sys.getsizeof(my_dict)
72
正如你所想象的，在這個(gè)字典上的第一次插入將使解釋器保留8個(gè)桶的空間，回到最初的情況。
