我們?cè)谏弦黄恼轮蟹治隽?CPython 中是如何實(shí)現(xiàn) dict 的。由于涉及內(nèi)容較多，我可能并沒(méi)有描述清楚 dict 所用的哈希表的具體結(jié)構(gòu)。

如果你也對(duì)此有疑問(wèn)，不妨來(lái)看一下本文對(duì)哈希表結(jié)構(gòu)的進(jìn)一步分析。

【dict 哈希表】

先看一張重新制作的圖。

這張圖描述的就是 CPython 中 PyDictKeysObject 結(jié)構(gòu)中的成員變量 dk_indices。它的數(shù)據(jù)類型是 char[]，表明它是一塊連續(xù)分配的內(nèi)存。

dk_indices 在使用中被分割為兩部分。

第一部分是圖中的 Slots 數(shù)組，也就是我們之前文章中提到的哈希表索引內(nèi)存塊；第二部分是 KeyValues 數(shù)組，我們之前稱之為哈希表鍵值對(duì)內(nèi)存塊。這兩部分都是連續(xù)的內(nèi)存，都可以當(dāng)做數(shù)組來(lái)處理，從而能充分利用數(shù)組隨機(jī)訪問(wèn)的特性，提高 dict 的訪問(wèn)效率。

Slots 數(shù)組有兩個(gè)作用：

1. 根據(jù)字典中元素 key 的哈希值為元素提供一個(gè)槽位（slot）。這是哈希表最一般的用途。

2. Slots 中存儲(chǔ)的并非元素本身，而是元素在 KeyValues 數(shù)組中的索引。由于 Slots 本身就是一個(gè)數(shù)組，通過(guò) Slots[KeySlot] 就可以直接獲取元素在 KeyValues 數(shù)組中的位置，效率很高。

圖中的 slot 有 3 種取值：-1、-2 和自然數(shù)。分別代表著 slot 的三種狀態(tài)：

1. 未曾使用（UnUsed）

   這是每個(gè) slot 的初始狀態(tài)，表示 slot 從未被 key 命中過(guò)，從未存儲(chǔ)過(guò)任何元素的索引。
   

2. 回收備用（Dummy）

   這類 slot 已存儲(chǔ)過(guò)元素的索引，但元素已被刪除，被標(biāo)記為可再次使用。從這里也可以看到，執(zhí)行刪除操作時(shí)，哈希表并不會(huì)真正刪除元素。這既能提高內(nèi)存的使用效率，又可以避免物理刪除導(dǎo)致的其他元素訪問(wèn)失效。

3. 活動(dòng)的（Active）

   slot 中存儲(chǔ)的是一個(gè)有效的元素的索引。

哈希表的 hash 算法和沖突算法都是運(yùn)行在這個(gè) Slots 數(shù)組上的。

計(jì)算 slot 的基本方法為：

當(dāng)發(fā)生 key 沖突時(shí)，會(huì)采用如下算法在 Slots 中查找下一個(gè)合適的 slot：

KeyValues 數(shù)組用來(lái)存儲(chǔ)鍵值對(duì)。鍵值對(duì)是以追加的方式添加到數(shù)組的尾部的，添加完成之后，將其位置索引保存在 key 對(duì)應(yīng)的 slot 中。

dict.items()、dict.keys() 和 dict.values() 這三個(gè)方法就是直接訪問(wèn) KeyValues 數(shù)組的，因而元素的輸出順序和插入順序是一致的。

【使用這種結(jié)構(gòu)的好處】

首先，使用連續(xù)的內(nèi)存可充分利用數(shù)組隨機(jī)訪問(wèn)的特性，保證了 dict 的訪問(wèn)效率。

其次，Slots 數(shù)組只保存元素的索引，每個(gè) slot 只占用少量固定長(zhǎng)度的內(nèi)存，可大大節(jié)省內(nèi)存空間。

我們可以想象，當(dāng) dict 比較大時(shí)，如果其中只包含少量有效的（Active） slot，此時(shí)的 Slots 就是一個(gè)稀疏的數(shù)組。如果 Slots 中存儲(chǔ)的是元素對(duì)象，每個(gè)元素對(duì)象的 size 要遠(yuǎn)大于一個(gè) int 索引值占用的空間，這個(gè)稀疏數(shù)組會(huì)造成比較嚴(yán)重的內(nèi)存浪費(fèi)。

因此，CPython 所采用的這種哈希表內(nèi)存結(jié)構(gòu)的確是一種高效緊湊的數(shù)據(jù)存儲(chǔ)方式，具有很高的時(shí)間和空間效率。

【相關(guān)文章】