楔子

本篇文章來(lái)剖析一下字典的底層結(jié)構(gòu)，看看它是怎么設(shè)計(jì)的，以及在設(shè)計(jì)的過(guò)程中都需要做哪些考量。另外字典是基于哈希表實(shí)現(xiàn)的，而傳統(tǒng)的哈希表存在內(nèi)存浪費(fèi)的問(wèn)題，那么字典又是如何優(yōu)化的呢？帶著這些問(wèn)題，開(kāi)始今天的內(nèi)容。

字典的底層結(jié)構(gòu)

Python 一切皆對(duì)象，字典也不例外，它在底層也由某個(gè)結(jié)構(gòu)體表示。

// Include/cpython/dictobject.h
typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    PyDictValues *ma_values;
} PyDictObject;

解釋一下里面的字段的含義：

• PyObject_HEAD：對(duì)象的頭部信息，里面包含了對(duì)象的引用計(jì)數(shù)和類(lèi)型。
• ma_used：字典的長(zhǎng)度，它充當(dāng)了 ob_size。
• ma_version_tag：字典的版本號(hào)，對(duì)字典的每一次修改都會(huì)導(dǎo)致其改變。
• ma_keys：從定義上來(lái)看它是一個(gè)指針，指向了 PyDictKeysObject。而 Python 里面的哈希表分為兩種，分別是 combined table 和 split table，即結(jié)合表和分離表。如果是結(jié)合表，那么鍵值對(duì)全部由 ma_keys 維護(hù)，此時(shí) ma_values 為 NULL。
• ma_values：如果是分離表，那么鍵由 ma_keys 維護(hù)，值由 ma_values 維護(hù)。而 ma_values 是一個(gè)二級(jí)指針，指向 PyObject * 類(lèi)型的指針數(shù)組的首元素；

這里先解釋一下結(jié)合表和分離表的由來(lái)。結(jié)合表的話，鍵和值會(huì)存在一起；分離表的話，鍵和值會(huì)存在不同的地方。那么問(wèn)題來(lái)了，為什么要將哈希表分為兩種呢？事實(shí)上，早期的哈希表只有結(jié)合表這一種，并且現(xiàn)在創(chuàng)建一個(gè)字典使用的也是結(jié)合表。

from ctypes import *

class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]

class PyDictObject(PyObject):
    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]


d = {"a": 1, "b": 2}
print(
    PyDictObject.from_address(id(d)).ma_values
)  # None

我們看到 ma_values 打印的結(jié)果是一個(gè) None，證明是結(jié)合表，值不是由 ma_values 維護(hù)，而是和鍵一起，都由 ma_keys 負(fù)責(zé)維護(hù)。

而分離表是在 PEP-0412 中被引入的，主要是為了提高內(nèi)存使用率，也就是讓不同的字典共享相同的一組 key。比如自定義類(lèi)的實(shí)例對(duì)象，它們默認(rèn)都有自己的屬性字典，如果對(duì)某個(gè)類(lèi)多次實(shí)例化，那么改成分離表會(huì)更有效率。因?yàn)樗鼈兊膶傩悦Q(chēng)是相同的，完全可以共享同一組 key；如果是結(jié)合表，那么每個(gè)實(shí)例的屬性字典都要將相同的 key 單獨(dú)保存一次，這顯然是一種浪費(fèi)。

from ctypes import *

class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]

class PyDictObject(PyObject):

    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]

class A:
    pass

a1 = A()
a2 = A()

# 因?yàn)轭?lèi)型指定的是 void *，所以打印的結(jié)果是一串地址
# 但我們看到輸出不為 None，說(shuō)明采用的確實(shí)是分離表
print(
    PyDictObject.from_address(id(a1.__dict__)).ma_values,
    PyDictObject.from_address(id(a2.__dict__)).ma_values
)  # 140291010752544 140291010877520

# 然后再查看 ma_keys，既然是共享同一組 key
# 那么打印的地址應(yīng)該是一樣的
print(
    PyDictObject.from_address(id(a1.__dict__)).ma_keys,
    PyDictObject.from_address(id(a2.__dict__)).ma_keys
)  # 94312886214288 94312886214288

# 結(jié)果確實(shí)是一樣的，不同實(shí)例對(duì)象的屬性字典里面的 key 是共享的
# 因?yàn)槭峭粋€(gè)類(lèi)的實(shí)例對(duì)象，屬性字典的 key 是相同的，所以沒(méi)必要將同一組 key 保存多次

以上就是結(jié)合表和分離表之間的區(qū)別，只需要知道分離表是 Python 為了提高內(nèi)存使用率而專(zhuān)門(mén)引入的即可。我們平時(shí)自己創(chuàng)建的字典，使用的都是結(jié)合表，因此我們的重點(diǎn)也將會(huì)放在結(jié)合表身上。

而結(jié)合表的話，鍵值都由 ma_keys 維護(hù)，它是一個(gè)指向 PyDictKeysObject 的指針，因此玄機(jī)就隱藏在這個(gè)結(jié)構(gòu)體里面。

// Include/cpython/dictobject.h
typedef enum {
    DICT_KEYS_GENERAL = 0,
    DICT_KEYS_UNICODE = 1,
    DICT_KEYS_SPLIT = 2
} DictKeysKind;  // 鍵的種類(lèi)，下面會(huì)用到

typedef struct _dictkeysobject PyDictKeysObject;

// Include/internal/pycore_dict.h
struct _dictkeysobject {
  // key 的引用計(jì)數(shù)，也就是 key 被多少個(gè)字典所使用
  // 如果是結(jié)合表，那么該成員始終是 1，因?yàn)榻Y(jié)合表獨(dú)占一組 key
  // 如果是分離表，那么該成員大于等于 1，因?yàn)榉蛛x表可以共享一組 key
  Py_ssize_t dk_refcnt;
  // 1 << dk_log2_size 便是哈希表的大小、或者說(shuō)長(zhǎng)度
  // 因此可以看出哈希表的大小滿(mǎn)足 2 的 n 次方，這樣可以將取模運(yùn)算優(yōu)化成按位與運(yùn)算
  // 比如 size 滿(mǎn)足 2 的 n 次方，那么整數(shù) num % size 等價(jià)于 num & (size - 1)
  uint8_t dk_log2_size;
  // 通過(guò) 1 << dk_log2_index_bytes 可以計(jì)算出哈希索引數(shù)組總共占多少字節(jié)
  // 關(guān)于什么是哈希索引數(shù)組，稍后解釋
  uint8_t dk_log2_index_bytes;
  // 鍵的種類(lèi)，有三個(gè)可選值，分別是 0、1、2
  // 如果字典的鍵可以是任意類(lèi)型，那么 dk_kind 為 0，即 DICT_KEYS_GENERAL
  // 如果字典的所有鍵都是 unicode 字符串，那么 dk_kind 為 1，即 DICT_KEYS_UNICODE
  // 以上兩種取值，不論是哪一種，都表示字典使用的是結(jié)合表
  // 如果是分離表，那么 dk_kind 為 2，即 DICT_KEYS_SPLIT，這里分離表不做過(guò)多討論
  // 那么問(wèn)題來(lái)了，為什么要對(duì)鍵（key）做這種區(qū)分呢？
  // 首先一個(gè)鍵值對(duì)就是一個(gè) entry，它里面包含了鍵和值，而它的類(lèi)型有兩種
  // 如果 dk_kind == 0，那么 entry 由 PyDictKeyEntry 結(jié)構(gòu)體表示
  // 如果 dk_kind == 1，那么 entry 由 PyDictUnicodeEntry 結(jié)構(gòu)體表示
  uint8_t dk_kind;
  // 字典的版本號(hào)，如果字典被修改，那么會(huì)重置為 0
  // 通過(guò)該字段，可以檢測(cè)字典是否在迭代過(guò)程中被修改
  uint32_t dk_version;
  // 鍵值對(duì)數(shù)組的長(zhǎng)度，說(shuō)白了就是鍵值對(duì)數(shù)組可以容納多少個(gè) entry（鍵值對(duì)）
  // 關(guān)于什么是鍵值對(duì)數(shù)組，以及它和哈希索引數(shù)組之間有什么區(qū)別，稍后會(huì)解釋
  Py_ssize_t dk_usable;
  // 鍵值對(duì)數(shù)組里面已經(jīng)存儲(chǔ)了多少個(gè)鍵值對(duì)
  Py_ssize_t dk_nentries;
  // 哈希索引數(shù)組
  char dk_indices[];
  // 注：dk_indices 后面其實(shí)還有一個(gè)字段 dk_entries，只不過(guò)沒(méi)有寫(xiě)在結(jié)構(gòu)體里面
  // 從字段名也可以看出，它表示鍵值對(duì)數(shù)組，因此它的類(lèi)型就是個(gè)數(shù)組
  // 然后數(shù)組里面存儲(chǔ)的是鍵值對(duì)，即 entry，而根據(jù) dk_kind 的不同
  // entry 可以是 PyDictKeyEntry 結(jié)構(gòu)體實(shí)例，也可以是 PyDictUnicodeEntry 結(jié)構(gòu)體實(shí)例
};

字典的定義還是稍微有點(diǎn)復(fù)雜的，如果目前感到困惑，沒(méi)有關(guān)系，稍后我們會(huì)一點(diǎn)點(diǎn)解釋清楚。這里再來(lái)看看鍵值對(duì)長(zhǎng)什么樣子。

// Include/internal/pycore_dict.h
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; 
} PyDictKeyEntry;

typedef struct {
    PyObject *me_key;   
    PyObject *me_value; 
} PyDictUnicodeEntry;

如果對(duì)象要作為字典的 key，那么它一定是可哈希的，所以 PyDictKeyEntry 里面除了鍵和值（指針）之外，還包含了鍵的哈希值。并且在 3.8 版本的時(shí)候，鍵值對(duì)統(tǒng)一使用 PyDictKeyEntry 結(jié)構(gòu)體表示。

但在 3.12 的時(shí)候，又設(shè)計(jì)出了 PyDictUnicodeEntry，它的使用場(chǎng)景是字典里面的 key 全部都是字符串。相比 PyDictKeyEntry ，它內(nèi)部不再保存 me_hash 字段，因?yàn)樽址畠?nèi)部已經(jīng)維護(hù)了哈希值。所以通過(guò)該設(shè)計(jì)，可以更加節(jié)省內(nèi)存，不得不說(shuō)，Python 底層為了優(yōu)化真的是殫精竭慮。

至此，字典的整個(gè)底層結(jié)構(gòu)就非常清晰了，我們畫(huà)一張圖，然后再來(lái)從頭解釋一下，并解答之前留下的疑問(wèn)。

圖片

字典的真正實(shí)現(xiàn)藏在 PyDictKeysObject 中，它的內(nèi)部包含兩個(gè)關(guān)鍵數(shù)組：一個(gè)是哈希索引數(shù)組 dk_indices，另一個(gè)是鍵值對(duì)數(shù)組 dk_entries。

字典維護(hù)的鍵值對(duì)（entry）會(huì)按照先來(lái)后到的順序保存在鍵值對(duì)數(shù)組中，而哈希索引數(shù)組則保存鍵值對(duì)在鍵值對(duì)數(shù)組中的索引。另外，哈希索引數(shù)組中的一個(gè)位置我們稱(chēng)之為一個(gè)槽，比如圖中的哈希索引數(shù)組便有 8 個(gè)槽，其數(shù)量由 1 << dk_log2_size 維護(hù)。

比如我們創(chuàng)建一個(gè)空字典，注意：雖然字典是空的，但是容量已經(jīng)有了，然后往里面插入鍵值對(duì) "komeiji":99 的時(shí)候，Python 會(huì)執(zhí)行以下步驟：

1. 將鍵值對(duì)保存在 dk_entries 中，由于初始字典是空的，所以會(huì)保存在 dk_entries 數(shù)組中索引為 0 的位置。
2. 通過(guò)哈希函數(shù)計(jì)算出 "komeiji" 的哈希值，然后將哈希值映射成索引，假設(shè)是 6。
3. 將 "鍵值對(duì)" 在 "鍵值對(duì)數(shù)組" 中的索引 0，保存在哈希索引數(shù)組中索引為 6 的槽里面。

然后當(dāng)我們?cè)诓檎益I "komeiji" 對(duì)應(yīng)的值的時(shí)候，便可瞬間定位。過(guò)程如下：

1. 通過(guò)哈希函數(shù)計(jì)算出 "komeiji" 的哈希值，然后映射成索引。因?yàn)樵谠O(shè)置的時(shí)候索引是 6，所以在獲取時(shí)，映射出來(lái)的索引肯定也是 6。
2. 找到哈希索引數(shù)組中索引為 6 的槽，得到其保存的 0，這里的 0 對(duì)應(yīng)鍵值對(duì)數(shù)組的索引。
3. 找到鍵值對(duì)數(shù)組中索引為 0 的位置存儲(chǔ)的 entry，然后判斷 entry->me_key 和查找的 key 是否一致，不一致則重新映射。如果一致，則取出 me_value，然后返回。

由于哈希值計(jì)算以及數(shù)組索引查找均是 O(1) 的時(shí)間復(fù)雜度，所以字典的查詢(xún)速度才會(huì)這么快。

另外前面介紹哈希表的時(shí)候，為了避免牽扯太多，說(shuō)得相對(duì)簡(jiǎn)化了。比如："xxx": 80，假設(shè) "xxx" 映射出來(lái)的索引是 2，那么鍵值對(duì)就直接存在索引為 2 的地方。這實(shí)際上是簡(jiǎn)化了，因?yàn)檫@相當(dāng)于把哈希索引數(shù)組和鍵值對(duì)數(shù)組合在一塊了，而早期的 Python 也確實(shí)是這么做的。

但是從上面字典的結(jié)構(gòu)圖中我們看到，實(shí)際上是先將鍵值對(duì)按照先來(lái)后到的順序存在一個(gè)數(shù)組（鍵值對(duì)數(shù)組）中，然后再將它在鍵值對(duì)數(shù)組中的索引存放在另一個(gè)數(shù)組（哈希索引數(shù)組）的某個(gè)槽里面，因?yàn)?nbsp;"xxx" 映射出來(lái)的是 2，所以就存在索引為 2 的槽里面。

而在查找的時(shí)候，映射出來(lái)的索引 2 其實(shí)是哈希索引數(shù)組的索引。然后索引為 2 的槽又存儲(chǔ)了一個(gè)索引，這個(gè)索引是鍵值對(duì)數(shù)組的索引，會(huì)再根據(jù)該索引從鍵值對(duì)數(shù)組里面獲取指定的 entry。最后比較 key 是否相同、如果相同則返回指定的 value。

所以能看出兩者整體思想是基本類(lèi)似的，理解起來(lái)區(qū)別不大，甚至第一種方式實(shí)現(xiàn)起來(lái)還更簡(jiǎn)單一些。但為什么要采用后者這種實(shí)現(xiàn)方式，以及這兩者之間的區(qū)別，我們下面來(lái)專(zhuān)門(mén)分析，之所以采用后者主要是基于內(nèi)存的考量。

哈希表的內(nèi)存優(yōu)化

在早期，哈希表并沒(méi)有分成兩個(gè)數(shù)組實(shí)現(xiàn)，而是只由一個(gè)鍵值對(duì)數(shù)組實(shí)現(xiàn)，這個(gè)數(shù)組也承擔(dān)哈希索引數(shù)組的角色。

圖片

我們看到這種結(jié)構(gòu)不正是我們?cè)诮榻B哈希表時(shí)說(shuō)的嗎？鍵值對(duì)數(shù)組不僅負(fù)責(zé)存儲(chǔ) entry，同時(shí)也負(fù)責(zé)承載映射后的索引，而無(wú)需分成兩個(gè)數(shù)組，這種方式似乎更簡(jiǎn)單、更直觀。沒(méi)錯(cuò)，Python 在早期確實(shí)是通過(guò)這種方式實(shí)現(xiàn)的哈希表，只是這種實(shí)現(xiàn)方式有一個(gè)弊端，就是太耗費(fèi)內(nèi)存了。

前面說(shuō)了，基于 key 映射出的索引是隨機(jī)的，所以肯定會(huì)存在索引沖突的情況，即不同的 key 映射到了同一個(gè)槽。并且隨著存儲(chǔ)的 entry 增多，沖突也會(huì)越頻繁，性能也就越差。因此哈希表必須要預(yù)留一定的空間，而經(jīng)過(guò)實(shí)踐表明，預(yù)留的空間至少要占總?cè)萘康?1/3。

換句話說(shuō)，哈希表存儲(chǔ)的 entry 的數(shù)量不能超過(guò)總?cè)萘康?2/3。

// Objects/dictobject.c
#define USABLE_FRACTION(n) (((n) << 1)/3)

宏 USABLE_FRACTION 會(huì)根據(jù)哈希表的長(zhǎng)度，或者說(shuō)容量，計(jì)算出哈希表可存儲(chǔ)的元素個(gè)數(shù)。以長(zhǎng)度為 8 的哈希表為例，最多可以保存 5 個(gè)鍵值對(duì)，超出則需要擴(kuò)容，顯然這存在嚴(yán)重的內(nèi)存浪費(fèi)。

所以 Python 為了節(jié)省內(nèi)存，想出了一個(gè)妙招。既然只能用 2/3，那就將鍵值對(duì)數(shù)組的空間變?yōu)樵瓉?lái)的 2/3，只用來(lái)存儲(chǔ)鍵值對(duì)（entry），而對(duì) key 進(jìn)行映射得到的索引則由另一個(gè)數(shù)組（哈希索引數(shù)組）來(lái)承載。假設(shè)映射出的索引是 4，那么就去找哈希索引數(shù)組中索引為 4 的槽，該槽存儲(chǔ)的便是鍵值對(duì)在鍵值對(duì)數(shù)組中的索引。

之所以這么設(shè)計(jì)，是因?yàn)殒I值對(duì)數(shù)組里面一個(gè)元素要占用 24 或 16 字節(jié)，而哈希索引數(shù)組在容量不超過(guò) 255 的時(shí)候，里面一個(gè)元素只占一個(gè)字節(jié)，容量不超過(guò) 65535 的時(shí)候，里面一個(gè)元素只占兩個(gè)字節(jié)，其它以此類(lèi)推。

所以哈希索引數(shù)組里面的元素大小比鍵值對(duì)數(shù)組要小很多，將哈希表分成兩個(gè)數(shù)組（避免鍵值對(duì)數(shù)組的浪費(fèi)）來(lái)實(shí)現(xiàn)會(huì)更加節(jié)省內(nèi)存。我們可以舉個(gè)例子計(jì)算一下，假設(shè)有一個(gè)容量為 65535 的哈希表。

如果是通過(guò)第一種方式，只用一個(gè)數(shù)組來(lái)存儲(chǔ)的話：

# 總共需要 1572840 字節(jié)
>>> 65535 * 24
1572840  
# 除以 3, 會(huì)浪費(fèi) 524280 字節(jié)
>>> 65535  * 24 // 3
524280
>>>

如果是通過(guò)第二種方式，使用兩個(gè)數(shù)組來(lái)存儲(chǔ)的話：

# 容量雖然是 65535
# 但鍵值對(duì)數(shù)組是容量的 2 / 3
# 然后加上哈希索引數(shù)組的大小
>>> 65535 * 24 * 2 // 3 + 65535 * 2
1179630
>>>

所以一個(gè)數(shù)組存儲(chǔ)比兩個(gè)數(shù)組存儲(chǔ)要多用 393210 字節(jié)的內(nèi)存，因此 Python 選擇使用兩個(gè)數(shù)組來(lái)存儲(chǔ)。

我們?cè)僖蚤L(zhǎng)度為 8 的哈希表為例，畫(huà)一張圖對(duì)比一下，由于哈希表長(zhǎng)度為 8，那么它最多存儲(chǔ) 5 個(gè)鍵值對(duì)。

圖片

如果哈希表只使用一個(gè)鍵值對(duì)數(shù)組，那么基于 key 映射出的索引就是鍵值對(duì)數(shù)組的索引，這種方式簡(jiǎn)單直觀，但內(nèi)存浪費(fèi)嚴(yán)重，因?yàn)橐速M(fèi)掉 1/3 的空間。于是為了解決這個(gè)問(wèn)題，哈希表選擇使用兩個(gè)數(shù)組實(shí)現(xiàn)，分別是哈希索引數(shù)組和鍵值對(duì)數(shù)組。

哈希索引數(shù)組的長(zhǎng)度就是哈希表的長(zhǎng)度，key 映射之后的索引也是哈希索引數(shù)組的索引，只不過(guò)它存儲(chǔ)的不再是鍵值對(duì)，而是鍵值對(duì)在鍵值對(duì)數(shù)組中的索引。那么問(wèn)題來(lái)了，明明多了一個(gè)數(shù)組，為啥內(nèi)存占用反而變少了呢？很明顯，由于引入了哈希索引數(shù)組，鍵值對(duì)數(shù)組的長(zhǎng)度可以減少到原來(lái)的 2/3。

因?yàn)橄啾孺I值對(duì)數(shù)組，哈希索引數(shù)組的內(nèi)存占用非常低，引入它需要的成本遠(yuǎn)小于避免鍵值對(duì)數(shù)組浪費(fèi) 1/3 所帶來(lái)的收益，所以使用兩個(gè)數(shù)組來(lái)實(shí)現(xiàn)哈希表是更加合理的。

然后我們?cè)賮?lái)回顧一下 PyDictKeysObject 結(jié)構(gòu)體，此時(shí)里面的字段就非常清晰了。

圖片

哈希表本質(zhì)上就是個(gè)數(shù)組，只不過(guò) Python 選擇使用兩個(gè)數(shù)組實(shí)現(xiàn)，其中哈希索引數(shù)組的長(zhǎng)度便是哈希表的容量，而該長(zhǎng)度由 1 << dk_log2_size 表示。然后 1 << dk_log2_index_bytes 則表示哈希索引數(shù)組占的內(nèi)存大小，之所以要維護(hù)這個(gè)大小信息，是為了能夠快速定位到位于哈希索引數(shù)組之后的鍵值對(duì)數(shù)組。

由于哈希表最多使用 2/3，那么就只為鍵值對(duì)數(shù)組申請(qǐng) 2/3 容量的空間。對(duì)于容量為 8 的哈希表，那么哈希索引數(shù)組的長(zhǎng)度就是 8，鍵值對(duì)數(shù)組的長(zhǎng)度就是 5。而鍵值對(duì)數(shù)組的長(zhǎng)度由 dk_usable 字段維護(hù)，所以它的值是 5。

假設(shè)哈希表，或者說(shuō)鍵值對(duì)數(shù)組存儲(chǔ)了 3 個(gè)鍵值對(duì)，那么 dk_nentries 就是 3，因?yàn)樵撟侄呜?fù)責(zé)維護(hù)當(dāng)前已存在的鍵值對(duì)的數(shù)量。咦，前面介紹 PyDictObject 的時(shí)候，看到里面有一個(gè) ma_used 字段，表示字典的長(zhǎng)度。那么 dk_nentries 和 ma_used 有啥區(qū)別呢，從字面意思上看，兩者的含義貌似是等價(jià)的，關(guān)于這一點(diǎn)后續(xù)再解釋。

最后就是 dk_indices 和 dk_entries，它們表示哈希索引數(shù)組和鍵值對(duì)數(shù)組。到此我們就把每個(gè)字段的含義又重新回顧了一遍，現(xiàn)在再來(lái)看是不是就清晰多了呢。

字典遍歷的有序性

我們知道 Python 從 3.6 開(kāi)始，字典的遍歷是有序的，那么這是怎么實(shí)現(xiàn)的呢？

其實(shí)很簡(jiǎn)單，在存儲(chǔ)時(shí)，雖然映射之后的索引是隨機(jī)的，但鍵值對(duì)本身始終是按照先來(lái)后到的順序被添加進(jìn)鍵值對(duì)數(shù)組中。而字典在 for 循環(huán)時(shí)，會(huì)直接遍歷鍵值對(duì)數(shù)組，所以遍歷的結(jié)果是有序的。但即便如此，我們也不應(yīng)該依賴(lài)此特性。

還是以之前的圖為例，我們順序?qū)懭肴齻€(gè)鍵值對(duì)，key 分別是 "a"、"b"、"c"：

圖片

早期的哈希表只有一個(gè)鍵值對(duì)數(shù)組，鍵值對(duì)在存儲(chǔ)時(shí)本身就是無(wú)序的，那么遍歷的結(jié)果自然也是無(wú)序的。對(duì)于當(dāng)前來(lái)說(shuō)，遍歷的結(jié)果就是 "b"、"a"、"c"。

但從 3.6 開(kāi)始，鍵值對(duì)數(shù)組中的鍵值對(duì)，和添加順序是一致的。而遍歷時(shí)，會(huì)直接遍歷鍵值對(duì)數(shù)組，因此遍歷的結(jié)果是有序的。對(duì)于當(dāng)前來(lái)說(shuō)，遍歷的結(jié)果就是 "a"、"b"、"c"。

當(dāng)然，如果你是 Python 的設(shè)計(jì)者，希望遍歷依舊不保持有序的話，那么該怎么做呢？很簡(jiǎn)單，可以先遍歷哈希索引數(shù)組，將存儲(chǔ)的有效索引依次取出，對(duì)于當(dāng)前來(lái)說(shuō)就是 1、0、2。然后基于這些索引，從鍵值對(duì)數(shù)組中獲取鍵值對(duì)，那么遍歷的結(jié)果也是 "b"、"a"、"c"。

字典的內(nèi)存大小

下面來(lái)分析一下字典占用的內(nèi)存大小，首先字典和列表一樣都有容量的概念，由于空間已經(jīng)申請(qǐng)了，不管有沒(méi)有使用，大小都必須算進(jìn)去。而字典的容量策略相比列表要簡(jiǎn)單很多，因?yàn)榇笮∫獫M(mǎn)足 2 的 n 次方，所以容量一定按照 8、16、32、64、······ 進(jìn)行變化。

注意：字典的容量（或者說(shuō)哈希表的容量）指的是內(nèi)部哈希索引數(shù)組的長(zhǎng)度，它要滿(mǎn)足 2 的 n 次方，從而將取模運(yùn)算優(yōu)化成按位與運(yùn)算。當(dāng)哈希索引數(shù)組存儲(chǔ)的元素（鍵值對(duì)數(shù)組的索引）個(gè)數(shù)達(dá)到了總長(zhǎng)度的 2/3，同時(shí)也意味著鍵值對(duì)數(shù)組已經(jīng)滿(mǎn)了，那么說(shuō)明字典（哈希表）該擴(kuò)容了。

知道了容量規(guī)則，我們來(lái)看一下字典的內(nèi)存大小怎么計(jì)算。

typedef struct {
    PyObject_HEAD              // 16 字節(jié)
    Py_ssize_t ma_used;        // 8 字節(jié)
    uint64_t ma_version_tag;   // 8 字節(jié)
    PyDictKeysObject *ma_keys; // 8 字節(jié)
    PyDictValues *ma_values;   // 8 字節(jié)
} PyDictObject;
// 所以 PyDictObject 實(shí)例占 48 字節(jié)


struct _dictkeysobject {
    Py_ssize_t dk_refcnt;        // 8 字節(jié)
    uint8_t dk_log2_size;        // 1 字節(jié)
    uint8_t dk_log2_index_bytes; // 1 字節(jié)
    uint8_t dk_kind;             // 1 字節(jié)
    uint32_t dk_version;         // 4 字節(jié)
    Py_ssize_t dk_usable;        // 8 字節(jié)
    Py_ssize_t dk_nentries;      // 8 字節(jié)
    char dk_indices[];  
    // 隱藏字段 dk_entries
};
// 如果不算哈希索引數(shù)組 dk_indices 和鍵值對(duì)數(shù)組 dk_entries
// 那么 PyDictKeysObject 實(shí)例占 31 + 1 = 32 個(gè)字節(jié)
// 注意：結(jié)構(gòu)體會(huì)因內(nèi)存對(duì)齊而多出 1 字節(jié)的空洞，所以是 32 字節(jié)

// 另外事實(shí)上在計(jì)算 PyDictKeysObject 的大小時(shí)，兩個(gè)數(shù)組并沒(méi)有被包含在內(nèi)
// 因?yàn)?dk_indices 是靈活數(shù)組，它在結(jié)構(gòu)體定義中沒(méi)有固定的大小，所以相當(dāng)于是 0
// 至于 dk_entries 更不用說(shuō)了，它壓根就沒(méi)有定義在結(jié)構(gòu)體中
// 因此 sizeof(PyDictKeysObject) 返回的結(jié)果就是 32
// 但在申請(qǐng)內(nèi)存的時(shí)候，是要根據(jù)字典的容量，為兩個(gè)數(shù)組申請(qǐng)內(nèi)存的

所以一個(gè)字典的大小至少是 48 字節(jié)，如果大小等于 48，說(shuō)明字典為空，它的 ma_keys 為 NULL。

圖片

但如果字典里面存在元素，那么還需要計(jì)算 PyDictKeysObject 的大小。

圖片

手動(dòng)創(chuàng)建的字典使用的都是結(jié)合表，因此它的 ma_keys 字段指向的 PyDictKeysObject 實(shí)例負(fù)責(zé)存儲(chǔ)鍵值對(duì)，而如果忽略掉內(nèi)部的兩個(gè)數(shù)組，那么它的大小為 32 字節(jié)。

所以當(dāng)字典不為空時(shí)，其內(nèi)存大小等于 48 + 32 + 哈希索引數(shù)組的內(nèi)存大小 + 鍵值對(duì)數(shù)組的內(nèi)存大小。有了這個(gè)公式，如果再能分析出兩個(gè)數(shù)組的長(zhǎng)度，那么任何一個(gè)字典，我們都可以計(jì)算出它的內(nèi)存大小。

我們以容量為 8 的字典為例，值得一提的是，當(dāng)字典不為空時(shí)，它的容量至少是 8。

// Objects/dictobject.c
#define PyDict_LOG_MINSIZE 3
#define PyDict_MINSIZE 8

從這個(gè)宏定義中我們可以得知，一個(gè)字典的最小容量是 8，即 1 << 3，或者說(shuō)內(nèi)部哈希索引數(shù)組的長(zhǎng)度最小是 8。

那么我們來(lái)算一下容量為 8 的字典的內(nèi)存大小，字典的容量是 8 說(shuō)明哈希索引數(shù)組的長(zhǎng)度是 8，每個(gè)元素占 1 字節(jié)，因此哈希索引數(shù)組的大小是 8 字節(jié)。然后鍵值對(duì)數(shù)組的長(zhǎng)度是 (8 << 1) / 3 = 5，每個(gè)元素可能占 16 或 24 字節(jié)。

• 如果所有 key 都是字符串，那么鍵值對(duì)用 PyDictUnicodeEntry 表示，一個(gè) entry 占 16 字節(jié)，那么字典的內(nèi)存大小為 48 + 32 + 8 + 5 * 16 = 168 字節(jié)。
• 否則鍵值對(duì)使用 PyDictKeyEntry 表示，一個(gè) entry 占 24 字節(jié)，那么字典的內(nèi)存大小為 48 + 32 + 8 + 5 * 24 = 208 字節(jié)。

我們來(lái)測(cè)試一下，看看是不是這個(gè)樣子。

圖片

結(jié)果和我們分析的一樣，那么問(wèn)題來(lái)了，如果一個(gè)字典有 7 個(gè)鍵值對(duì)，那么這個(gè)字典的內(nèi)存大小是多少呢？

長(zhǎng)度為 8 的哈希表，鍵值對(duì)數(shù)組的長(zhǎng)度是 5，最多能容納 5 個(gè)鍵值對(duì)。長(zhǎng)度為 16 的哈希表，鍵值對(duì)數(shù)組的長(zhǎng)度為 10，最多能容納 10 個(gè)鍵值對(duì)。所以對(duì)于鍵值對(duì)個(gè)數(shù)為 7 的字典，它內(nèi)部哈希表的長(zhǎng)度為 16。

字典是翻倍擴(kuò)容的，因?yàn)槿萘恳獫M(mǎn)足 2 的 n 次方。

因此當(dāng)鍵值對(duì)的個(gè)數(shù)為 7 時(shí)，字典的內(nèi)存大小等于 48 + 32 + 16 + 10 * entry_size。如果 entry_size 為 16，那么大小就是 256，如果 entry_size 為 24，那么大小就是 336。

圖片

結(jié)果沒(méi)有問(wèn)題，以上我們就計(jì)算出了字典的內(nèi)存大小，你也可以自己創(chuàng)建個(gè)字典測(cè)試一下。

小結(jié)

通過(guò)研究字典的具體實(shí)現(xiàn)，我們可以得出以下結(jié)論：

• 字典是一種高效的映射型容器，能夠以 O(1) 的時(shí)間復(fù)雜度執(zhí)行查詢(xún)和寫(xiě)入操作；
• 字典之所以這么快，是因?yàn)樗晒１韺?shí)現(xiàn)。但快是要付出代價(jià)的，哈希表必須保證一定的稀疏性，否則會(huì)頻繁出現(xiàn)索引沖突，導(dǎo)致哈希表性能下降，因?yàn)樗饕成涫请S機(jī)的；
• 既然哈希表要保證稀疏性，就意味著內(nèi)存開(kāi)銷(xiāo)大，因?yàn)榇嬖趦?nèi)存浪費(fèi)。
• 但 Python 為優(yōu)化內(nèi)存使用，選擇基于兩個(gè)數(shù)組來(lái)實(shí)現(xiàn)哈希表，通過(guò)避免鍵值對(duì)數(shù)組的浪費(fèi)，來(lái)減少內(nèi)存占用；
• 鍵值對(duì)數(shù)組里的 entry 除了保存 key 和  value 之外，還保存了 key 的哈希值。但如果所有的 key 都是字符串類(lèi)型，那么為優(yōu)化內(nèi)存使用，會(huì)選擇不再保存哈希值，因?yàn)樽址旧硪呀?jīng)維護(hù)了自身的哈希值。