字典是怎么實現(xiàn)的，它的底層結(jié)構(gòu)長什么樣子？
楔子
本篇文章來剖析一下字典的底層結(jié)構(gòu)，看看它是怎么設(shè)計的，以及在設(shè)計的過程中都需要做哪些考量。另外字典是基于哈希表實現(xiàn)的，而傳統(tǒng)的哈希表存在內(nèi)存浪費的問題，那么字典又是如何優(yōu)化的呢？帶著這些問題，開始今天的內(nèi)容。
字典的底層結(jié)構(gòu)
Python 一切皆對象，字典也不例外，它在底層也由某個結(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：對象的頭部信息，里面包含了對象的引用計數(shù)和類型。
- ma_used：字典的長度，它充當(dāng)了 ob_size。
- ma_version_tag：字典的版本號，對字典的每一次修改都會導(dǎo)致其改變。
- ma_keys：從定義上來看它是一個指針，指向了 PyDictKeysObject。而 Python 里面的哈希表分為兩種，分別是 combined table 和 split table，即結(jié)合表和分離表。如果是結(jié)合表，那么鍵值對全部由 ma_keys 維護(hù)，此時 ma_values 為 NULL。
- ma_values：如果是分離表，那么鍵由 ma_keys 維護(hù)，值由 ma_values 維護(hù)。而 ma_values 是一個二級指針，指向 PyObject * 類型的指針數(shù)組的首元素；
這里先解釋一下結(jié)合表和分離表的由來。結(jié)合表的話，鍵和值會存在一起；分離表的話，鍵和值會存在不同的地方。那么問題來了，為什么要將哈希表分為兩種呢？事實上，早期的哈希表只有結(jié)合表這一種，并且現(xiàn)在創(chuàng)建一個字典使用的也是結(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é)果是一個 None，證明是結(jié)合表，值不是由 ma_values 維護(hù)，而是和鍵一起，都由 ma_keys 負(fù)責(zé)維護(hù)。
而分離表是在 PEP-0412 中被引入的，主要是為了提高內(nèi)存使用率，也就是讓不同的字典共享相同的一組 key。比如自定義類的實例對象，它們默認(rèn)都有自己的屬性字典，如果對某個類多次實例化，那么改成分離表會更有效率。因為它們的屬性名稱是相同的，完全可以共享同一組 key；如果是結(jié)合表，那么每個實例的屬性字典都要將相同的 key 單獨保存一次，這顯然是一種浪費。
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()
# 因為類型指定的是 void *，所以打印的結(jié)果是一串地址
# 但我們看到輸出不為 None，說明采用的確實是分離表
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é)果確實是一樣的，不同實例對象的屬性字典里面的 key 是共享的
# 因為是同一個類的實例對象，屬性字典的 key 是相同的，所以沒必要將同一組 key 保存多次以上就是結(jié)合表和分離表之間的區(qū)別，只需要知道分離表是 Python 為了提高內(nèi)存使用率而專門引入的即可。我們平時自己創(chuàng)建的字典，使用的都是結(jié)合表，因此我們的重點也將會放在結(jié)合表身上。
而結(jié)合表的話，鍵值都由 ma_keys 維護(hù)，它是一個指向 PyDictKeysObject 的指針，因此玄機(jī)就隱藏在這個結(jié)構(gòu)體里面。
// Include/cpython/dictobject.h
typedef enum {
DICT_KEYS_GENERAL = 0,
DICT_KEYS_UNICODE = 1,
DICT_KEYS_SPLIT = 2
} DictKeysKind; // 鍵的種類，下面會用到
typedef struct _dictkeysobject PyDictKeysObject;
// Include/internal/pycore_dict.h
struct _dictkeysobject {
// key 的引用計數(shù)，也就是 key 被多少個字典所使用
// 如果是結(jié)合表，那么該成員始終是 1，因為結(jié)合表獨占一組 key
// 如果是分離表，那么該成員大于等于 1，因為分離表可以共享一組 key
Py_ssize_t dk_refcnt;
// 1 << dk_log2_size 便是哈希表的大小、或者說長度
// 因此可以看出哈希表的大小滿足 2 的 n 次方，這樣可以將取模運(yùn)算優(yōu)化成按位與運(yùn)算
// 比如 size 滿足 2 的 n 次方，那么整數(shù) num % size 等價于 num & (size - 1)
uint8_t dk_log2_size;
// 通過 1 << dk_log2_index_bytes 可以計算出哈希索引數(shù)組總共占多少字節(jié)
// 關(guān)于什么是哈希索引數(shù)組，稍后解釋
uint8_t dk_log2_index_bytes;
// 鍵的種類，有三個可選值，分別是 0、1、2
// 如果字典的鍵可以是任意類型，那么 dk_kind 為 0，即 DICT_KEYS_GENERAL
// 如果字典的所有鍵都是 unicode 字符串，那么 dk_kind 為 1，即 DICT_KEYS_UNICODE
// 以上兩種取值，不論是哪一種，都表示字典使用的是結(jié)合表
// 如果是分離表，那么 dk_kind 為 2，即 DICT_KEYS_SPLIT，這里分離表不做過多討論
// 那么問題來了，為什么要對鍵（key）做這種區(qū)分呢？
// 首先一個鍵值對就是一個 entry，它里面包含了鍵和值，而它的類型有兩種
// 如果 dk_kind == 0，那么 entry 由 PyDictKeyEntry 結(jié)構(gòu)體表示
// 如果 dk_kind == 1，那么 entry 由 PyDictUnicodeEntry 結(jié)構(gòu)體表示
uint8_t dk_kind;
// 字典的版本號，如果字典被修改，那么會重置為 0
// 通過該字段，可以檢測字典是否在迭代過程中被修改
uint32_t dk_version;
// 鍵值對數(shù)組的長度，說白了就是鍵值對數(shù)組可以容納多少個 entry（鍵值對）
// 關(guān)于什么是鍵值對數(shù)組，以及它和哈希索引數(shù)組之間有什么區(qū)別，稍后會解釋
Py_ssize_t dk_usable;
// 鍵值對數(shù)組里面已經(jīng)存儲了多少個鍵值對
Py_ssize_t dk_nentries;
// 哈希索引數(shù)組
char dk_indices[];
// 注：dk_indices 后面其實還有一個字段 dk_entries，只不過沒有寫在結(jié)構(gòu)體里面
// 從字段名也可以看出，它表示鍵值對數(shù)組，因此它的類型就是個數(shù)組
// 然后數(shù)組里面存儲的是鍵值對，即 entry，而根據(jù) dk_kind 的不同
// entry 可以是 PyDictKeyEntry 結(jié)構(gòu)體實例，也可以是 PyDictUnicodeEntry 結(jié)構(gòu)體實例
};字典的定義還是稍微有點復(fù)雜的，如果目前感到困惑，沒有關(guān)系，稍后我們會一點點解釋清楚。這里再來看看鍵值對長什么樣子。
// 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;如果對象要作為字典的 key，那么它一定是可哈希的，所以 PyDictKeyEntry 里面除了鍵和值（指針）之外，還包含了鍵的哈希值。并且在 3.8 版本的時候，鍵值對統(tǒng)一使用 PyDictKeyEntry 結(jié)構(gòu)體表示。
但在 3.12 的時候，又設(shè)計出了 PyDictUnicodeEntry，它的使用場景是字典里面的 key 全部都是字符串。相比 PyDictKeyEntry ，它內(nèi)部不再保存 me_hash 字段，因為字符串內(nèi)部已經(jīng)維護(hù)了哈希值。所以通過該設(shè)計，可以更加節(jié)省內(nèi)存，不得不說，Python 底層為了優(yōu)化真的是殫精竭慮。
至此，字典的整個底層結(jié)構(gòu)就非常清晰了，我們畫一張圖，然后再來從頭解釋一下，并解答之前留下的疑問。
圖片
字典的真正實現(xiàn)藏在 PyDictKeysObject 中，它的內(nèi)部包含兩個關(guān)鍵數(shù)組：一個是哈希索引數(shù)組 dk_indices，另一個是鍵值對數(shù)組 dk_entries。
字典維護(hù)的鍵值對（entry）會按照先來后到的順序保存在鍵值對數(shù)組中，而哈希索引數(shù)組則保存鍵值對在鍵值對數(shù)組中的索引。另外，哈希索引數(shù)組中的一個位置我們稱之為一個槽，比如圖中的哈希索引數(shù)組便有 8 個槽，其數(shù)量由 1 << dk_log2_size 維護(hù)。
比如我們創(chuàng)建一個空字典，注意：雖然字典是空的，但是容量已經(jīng)有了，然后往里面插入鍵值對 "komeiji":99 的時候，Python 會執(zhí)行以下步驟：
- 將鍵值對保存在 dk_entries 中，由于初始字典是空的，所以會保存在 dk_entries 數(shù)組中索引為 0 的位置。
- 通過哈希函數(shù)計算出 "komeiji" 的哈希值，然后將哈希值映射成索引，假設(shè)是 6。
- 將 "鍵值對" 在 "鍵值對數(shù)組" 中的索引 0，保存在哈希索引數(shù)組中索引為 6 的槽里面。
然后當(dāng)我們在查找鍵 "komeiji" 對應(yīng)的值的時候，便可瞬間定位。過程如下：
- 通過哈希函數(shù)計算出 "komeiji" 的哈希值，然后映射成索引。因為在設(shè)置的時候索引是 6，所以在獲取時，映射出來的索引肯定也是 6。
- 找到哈希索引數(shù)組中索引為 6 的槽，得到其保存的 0，這里的 0 對應(yīng)鍵值對數(shù)組的索引。
- 找到鍵值對數(shù)組中索引為 0 的位置存儲的 entry，然后判斷 entry->me_key 和查找的 key 是否一致，不一致則重新映射。如果一致，則取出 me_value，然后返回。
由于哈希值計算以及數(shù)組索引查找均是 O(1) 的時間復(fù)雜度，所以字典的查詢速度才會這么快。
另外前面介紹哈希表的時候，為了避免牽扯太多，說得相對簡化了。比如："xxx": 80，假設(shè) "xxx" 映射出來的索引是 2，那么鍵值對就直接存在索引為 2 的地方。這實際上是簡化了，因為這相當(dāng)于把哈希索引數(shù)組和鍵值對數(shù)組合在一塊了，而早期的 Python 也確實是這么做的。
但是從上面字典的結(jié)構(gòu)圖中我們看到，實際上是先將鍵值對按照先來后到的順序存在一個數(shù)組（鍵值對數(shù)組）中，然后再將它在鍵值對數(shù)組中的索引存放在另一個數(shù)組（哈希索引數(shù)組）的某個槽里面，因為 "xxx" 映射出來的是 2，所以就存在索引為 2 的槽里面。
而在查找的時候，映射出來的索引 2 其實是哈希索引數(shù)組的索引。然后索引為 2 的槽又存儲了一個索引，這個索引是鍵值對數(shù)組的索引，會再根據(jù)該索引從鍵值對數(shù)組里面獲取指定的 entry。最后比較 key 是否相同、如果相同則返回指定的 value。
所以能看出兩者整體思想是基本類似的，理解起來區(qū)別不大，甚至第一種方式實現(xiàn)起來還更簡單一些。但為什么要采用后者這種實現(xiàn)方式，以及這兩者之間的區(qū)別，我們下面來專門分析，之所以采用后者主要是基于內(nèi)存的考量。
哈希表的內(nèi)存優(yōu)化
在早期，哈希表并沒有分成兩個數(shù)組實現(xiàn)，而是只由一個鍵值對數(shù)組實現(xiàn)，這個數(shù)組也承擔(dān)哈希索引數(shù)組的角色。
圖片
我們看到這種結(jié)構(gòu)不正是我們在介紹哈希表時說的嗎？鍵值對數(shù)組不僅負(fù)責(zé)存儲 entry，同時也負(fù)責(zé)承載映射后的索引，而無需分成兩個數(shù)組，這種方式似乎更簡單、更直觀。沒錯，Python 在早期確實是通過這種方式實現(xiàn)的哈希表，只是這種實現(xiàn)方式有一個弊端，就是太耗費內(nèi)存了。
前面說了，基于 key 映射出的索引是隨機(jī)的，所以肯定會存在索引沖突的情況，即不同的 key 映射到了同一個槽。并且隨著存儲的 entry 增多，沖突也會越頻繁，性能也就越差。因此哈希表必須要預(yù)留一定的空間，而經(jīng)過實踐表明，預(yù)留的空間至少要占總?cè)萘康?1/3。
換句話說，哈希表存儲的 entry 的數(shù)量不能超過總?cè)萘康?2/3。
// Objects/dictobject.c
#define USABLE_FRACTION(n) (((n) << 1)/3)宏 USABLE_FRACTION 會根據(jù)哈希表的長度，或者說容量，計算出哈希表可存儲的元素個數(shù)。以長度為 8 的哈希表為例，最多可以保存 5 個鍵值對，超出則需要擴(kuò)容，顯然這存在嚴(yán)重的內(nèi)存浪費。
所以 Python 為了節(jié)省內(nèi)存，想出了一個妙招。既然只能用 2/3，那就將鍵值對數(shù)組的空間變?yōu)樵瓉淼?2/3，只用來存儲鍵值對（entry），而對 key 進(jìn)行映射得到的索引則由另一個數(shù)組（哈希索引數(shù)組）來承載。假設(shè)映射出的索引是 4，那么就去找哈希索引數(shù)組中索引為 4 的槽，該槽存儲的便是鍵值對在鍵值對數(shù)組中的索引。
之所以這么設(shè)計，是因為鍵值對數(shù)組里面一個元素要占用 24 或 16 字節(jié)，而哈希索引數(shù)組在容量不超過 255 的時候，里面一個元素只占一個字節(jié)，容量不超過 65535 的時候，里面一個元素只占兩個字節(jié)，其它以此類推。
所以哈希索引數(shù)組里面的元素大小比鍵值對數(shù)組要小很多，將哈希表分成兩個數(shù)組（避免鍵值對數(shù)組的浪費）來實現(xiàn)會更加節(jié)省內(nèi)存。我們可以舉個例子計算一下，假設(shè)有一個容量為 65535 的哈希表。
如果是通過第一種方式，只用一個數(shù)組來存儲的話：
# 總共需要 1572840 字節(jié)
>>> 65535 * 24
1572840
# 除以 3, 會浪費 524280 字節(jié)
>>> 65535 * 24 // 3
524280
>>>如果是通過第二種方式，使用兩個數(shù)組來存儲的話：
# 容量雖然是 65535
# 但鍵值對數(shù)組是容量的 2 / 3
# 然后加上哈希索引數(shù)組的大小
>>> 65535 * 24 * 2 // 3 + 65535 * 2
1179630
>>>所以一個數(shù)組存儲比兩個數(shù)組存儲要多用 393210 字節(jié)的內(nèi)存，因此 Python 選擇使用兩個數(shù)組來存儲。
我們再以長度為 8 的哈希表為例，畫一張圖對比一下，由于哈希表長度為 8，那么它最多存儲 5 個鍵值對。
圖片
如果哈希表只使用一個鍵值對數(shù)組，那么基于 key 映射出的索引就是鍵值對數(shù)組的索引，這種方式簡單直觀，但內(nèi)存浪費嚴(yán)重，因為要浪費掉 1/3 的空間。于是為了解決這個問題，哈希表選擇使用兩個數(shù)組實現(xiàn)，分別是哈希索引數(shù)組和鍵值對數(shù)組。
哈希索引數(shù)組的長度就是哈希表的長度，key 映射之后的索引也是哈希索引數(shù)組的索引，只不過它存儲的不再是鍵值對，而是鍵值對在鍵值對數(shù)組中的索引。那么問題來了，明明多了一個數(shù)組，為啥內(nèi)存占用反而變少了呢？很明顯，由于引入了哈希索引數(shù)組，鍵值對數(shù)組的長度可以減少到原來的 2/3。
因為相比鍵值對數(shù)組，哈希索引數(shù)組的內(nèi)存占用非常低，引入它需要的成本遠(yuǎn)小于避免鍵值對數(shù)組浪費 1/3 所帶來的收益，所以使用兩個數(shù)組來實現(xiàn)哈希表是更加合理的。
然后我們再來回顧一下 PyDictKeysObject 結(jié)構(gòu)體，此時里面的字段就非常清晰了。
圖片
哈希表本質(zhì)上就是個數(shù)組，只不過 Python 選擇使用兩個數(shù)組實現(xiàn)，其中哈希索引數(shù)組的長度便是哈希表的容量，而該長度由 1 << dk_log2_size 表示。然后 1 << dk_log2_index_bytes 則表示哈希索引數(shù)組占的內(nèi)存大小，之所以要維護(hù)這個大小信息，是為了能夠快速定位到位于哈希索引數(shù)組之后的鍵值對數(shù)組。
由于哈希表最多使用 2/3，那么就只為鍵值對數(shù)組申請 2/3 容量的空間。對于容量為 8 的哈希表，那么哈希索引數(shù)組的長度就是 8，鍵值對數(shù)組的長度就是 5。而鍵值對數(shù)組的長度由 dk_usable 字段維護(hù)，所以它的值是 5。
假設(shè)哈希表，或者說鍵值對數(shù)組存儲了 3 個鍵值對，那么 dk_nentries 就是 3，因為該字段負(fù)責(zé)維護(hù)當(dāng)前已存在的鍵值對的數(shù)量。咦，前面介紹 PyDictObject 的時候，看到里面有一個 ma_used 字段，表示字典的長度。那么 dk_nentries 和 ma_used 有啥區(qū)別呢，從字面意思上看，兩者的含義貌似是等價的，關(guān)于這一點后續(xù)再解釋。
最后就是 dk_indices 和 dk_entries，它們表示哈希索引數(shù)組和鍵值對數(shù)組。到此我們就把每個字段的含義又重新回顧了一遍，現(xiàn)在再來看是不是就清晰多了呢。
字典遍歷的有序性
我們知道 Python 從 3.6 開始，字典的遍歷是有序的，那么這是怎么實現(xiàn)的呢？
其實很簡單，在存儲時，雖然映射之后的索引是隨機(jī)的，但鍵值對本身始終是按照先來后到的順序被添加進(jìn)鍵值對數(shù)組中。而字典在 for 循環(huán)時，會直接遍歷鍵值對數(shù)組，所以遍歷的結(jié)果是有序的。但即便如此，我們也不應(yīng)該依賴此特性。
還是以之前的圖為例，我們順序?qū)懭肴齻€鍵值對，key 分別是 "a"、"b"、"c"：
圖片
早期的哈希表只有一個鍵值對數(shù)組，鍵值對在存儲時本身就是無序的，那么遍歷的結(jié)果自然也是無序的。對于當(dāng)前來說，遍歷的結(jié)果就是 "b"、"a"、"c"。
但從 3.6 開始，鍵值對數(shù)組中的鍵值對，和添加順序是一致的。而遍歷時，會直接遍歷鍵值對數(shù)組，因此遍歷的結(jié)果是有序的。對于當(dāng)前來說，遍歷的結(jié)果就是 "a"、"b"、"c"。
當(dāng)然，如果你是 Python 的設(shè)計者，希望遍歷依舊不保持有序的話，那么該怎么做呢？很簡單，可以先遍歷哈希索引數(shù)組，將存儲的有效索引依次取出，對于當(dāng)前來說就是 1、0、2。然后基于這些索引，從鍵值對數(shù)組中獲取鍵值對，那么遍歷的結(jié)果也是 "b"、"a"、"c"。
字典的內(nèi)存大小
下面來分析一下字典占用的內(nèi)存大小，首先字典和列表一樣都有容量的概念，由于空間已經(jīng)申請了，不管有沒有使用，大小都必須算進(jìn)去。而字典的容量策略相比列表要簡單很多，因為大小要滿足 2 的 n 次方，所以容量一定按照 8、16、32、64、······ 進(jìn)行變化。
注意：字典的容量（或者說哈希表的容量）指的是內(nèi)部哈希索引數(shù)組的長度，它要滿足 2 的 n 次方，從而將取模運(yùn)算優(yōu)化成按位與運(yùn)算。當(dāng)哈希索引數(shù)組存儲的元素（鍵值對數(shù)組的索引）個數(shù)達(dá)到了總長度的 2/3，同時也意味著鍵值對數(shù)組已經(jīng)滿了，那么說明字典（哈希表）該擴(kuò)容了。
知道了容量規(guī)則，我們來看一下字典的內(nèi)存大小怎么計算。
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 實例占 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 和鍵值對數(shù)組 dk_entries
// 那么 PyDictKeysObject 實例占 31 + 1 = 32 個字節(jié)
// 注意：結(jié)構(gòu)體會因內(nèi)存對齊而多出 1 字節(jié)的空洞，所以是 32 字節(jié)
// 另外事實上在計算 PyDictKeysObject 的大小時，兩個數(shù)組并沒有被包含在內(nèi)
// 因為 dk_indices 是靈活數(shù)組，它在結(jié)構(gòu)體定義中沒有固定的大小，所以相當(dāng)于是 0
// 至于 dk_entries 更不用說了，它壓根就沒有定義在結(jié)構(gòu)體中
// 因此 sizeof(PyDictKeysObject) 返回的結(jié)果就是 32
// 但在申請內(nèi)存的時候，是要根據(jù)字典的容量，為兩個數(shù)組申請內(nèi)存的所以一個字典的大小至少是 48 字節(jié)，如果大小等于 48，說明字典為空，它的 ma_keys 為 NULL。
圖片
但如果字典里面存在元素，那么還需要計算 PyDictKeysObject 的大小。
圖片
手動創(chuàng)建的字典使用的都是結(jié)合表，因此它的 ma_keys 字段指向的 PyDictKeysObject 實例負(fù)責(zé)存儲鍵值對，而如果忽略掉內(nèi)部的兩個數(shù)組，那么它的大小為 32 字節(jié)。
所以當(dāng)字典不為空時，其內(nèi)存大小等于 48 + 32 + 哈希索引數(shù)組的內(nèi)存大小 + 鍵值對數(shù)組的內(nèi)存大小。有了這個公式，如果再能分析出兩個數(shù)組的長度，那么任何一個字典，我們都可以計算出它的內(nèi)存大小。
我們以容量為 8 的字典為例，值得一提的是，當(dāng)字典不為空時，它的容量至少是 8。
// Objects/dictobject.c
#define PyDict_LOG_MINSIZE 3
#define PyDict_MINSIZE 8從這個宏定義中我們可以得知，一個字典的最小容量是 8，即 1 << 3，或者說內(nèi)部哈希索引數(shù)組的長度最小是 8。
那么我們來算一下容量為 8 的字典的內(nèi)存大小，字典的容量是 8 說明哈希索引數(shù)組的長度是 8，每個元素占 1 字節(jié)，因此哈希索引數(shù)組的大小是 8 字節(jié)。然后鍵值對數(shù)組的長度是 (8 << 1) / 3 = 5，每個元素可能占 16 或 24 字節(jié)。
- 如果所有 key 都是字符串，那么鍵值對用 PyDictUnicodeEntry 表示，一個 entry 占 16 字節(jié)，那么字典的內(nèi)存大小為 48 + 32 + 8 + 5 * 16 = 168 字節(jié)。
- 否則鍵值對使用 PyDictKeyEntry 表示，一個 entry 占 24 字節(jié)，那么字典的內(nèi)存大小為 48 + 32 + 8 + 5 * 24 = 208 字節(jié)。
我們來測試一下，看看是不是這個樣子。
圖片
結(jié)果和我們分析的一樣，那么問題來了，如果一個字典有 7 個鍵值對，那么這個字典的內(nèi)存大小是多少呢？
長度為 8 的哈希表，鍵值對數(shù)組的長度是 5，最多能容納 5 個鍵值對。長度為 16 的哈希表，鍵值對數(shù)組的長度為 10，最多能容納 10 個鍵值對。所以對于鍵值對個數(shù)為 7 的字典，它內(nèi)部哈希表的長度為 16。
字典是翻倍擴(kuò)容的，因為容量要滿足 2 的 n 次方。
因此當(dāng)鍵值對的個數(shù)為 7 時，字典的內(nèi)存大小等于 48 + 32 + 16 + 10 * entry_size。如果 entry_size 為 16，那么大小就是 256，如果 entry_size 為 24，那么大小就是 336。
圖片
結(jié)果沒有問題，以上我們就計算出了字典的內(nèi)存大小，你也可以自己創(chuàng)建個字典測試一下。
小結(jié)
通過研究字典的具體實現(xiàn)，我們可以得出以下結(jié)論：
- 字典是一種高效的映射型容器，能夠以 O(1) 的時間復(fù)雜度執(zhí)行查詢和寫入操作；
- 字典之所以這么快，是因為它由哈希表實現(xiàn)。但快是要付出代價的，哈希表必須保證一定的稀疏性，否則會頻繁出現(xiàn)索引沖突，導(dǎo)致哈希表性能下降，因為索引映射是隨機(jī)的；
- 既然哈希表要保證稀疏性，就意味著內(nèi)存開銷大，因為存在內(nèi)存浪費。
- 但 Python 為優(yōu)化內(nèi)存使用，選擇基于兩個數(shù)組來實現(xiàn)哈希表，通過避免鍵值對數(shù)組的浪費，來減少內(nèi)存占用；
- 鍵值對數(shù)組里的 entry 除了保存 key 和 value 之外，還保存了 key 的哈希值。但如果所有的 key 都是字符串類型，那么為優(yōu)化內(nèi)存使用，會選擇不再保存哈希值，因為字符串本身已經(jīng)維護(hù)了自身的哈希值。
