字典是怎么擴(kuò)容的？它會經(jīng)歷哪些過程？
在介紹字典的底層結(jié)構(gòu)時我們看到，當(dāng)已使用的 entry 數(shù)量達(dá)到總?cè)萘康?2/3 時，會發(fā)生擴(kuò)容。
而在早期，哈希表只使用一個鍵值對數(shù)組，這個鍵值對數(shù)組不僅要存儲具體的 entry，還要承載哈希索引數(shù)組的功能。本來這個方式很簡單，但是內(nèi)存浪費(fèi)嚴(yán)重，于是后面 Python 官方就將一個數(shù)組拆成兩個數(shù)組來實(shí)現(xiàn)。
不是說只能用 2/3 嗎？那就只給鍵值對數(shù)組申請 2/3 容量的空間，并且只負(fù)責(zé)存儲鍵值對。至于索引，則由哈希索引數(shù)組來體現(xiàn)。通過將 key 映射成索引，找到指定的哈希槽，再根據(jù)槽里面存儲的索引，找到鍵值對數(shù)組中存儲的 entry。
因此減少內(nèi)存開銷的核心就在于，避免鍵值對數(shù)組的浪費(fèi)。
所以哈希索引數(shù)組的長度就可以看成是哈希表的容量，而鍵值對數(shù)組的長度本身就是哈希索引數(shù)組的 2/3、或者說容量的 2/3。那么很明顯，當(dāng)鍵值對數(shù)組滿了，就說明當(dāng)前的哈希表要擴(kuò)容了。
// Objects/dictobject.c
#define GROWTH_RATE(d) ((d)->ma_used*3)擴(kuò)容之后的新哈希表的容量要大于等于 ma_used * 3，注意：是大于等于 ma_used * 3，不是 dk_nentries * 3。因?yàn)?dk_nentries 還包含了被刪除的 entry，但哈希表在擴(kuò)容的時候會將其丟棄，所以擴(kuò)容之后新哈希表的容量取決于 ma_used。
當(dāng)然啦，哈希表的容量還要等于 2 的冪次方，所以有兩個條件：
- 大于等于 ma_used * 3；
- 等于 2 的冪次方；
基于以上兩個限制條件，取到的最小值便是擴(kuò)容之后的容量。為此 Python 底層專門提供了一個 calculate_log2_keysize 函數(shù)，看一下它的邏輯。
// Objects/dictobject.c
static inline uint8_t
calculate_log2_keysize(Py_ssize_t minsize)
{
// 參數(shù) minsize 表示字典的 ma_used * 3，即長度 * 3
// 1 << log2_size 便是擴(kuò)容之后的字典的容量
uint8_t log2_size;
// PyDict_LOG_MINSIZE 是一個宏，值為 3，所以字典的最小容量是 8
// 如果 (1 << log2_size) < minsize，那么不斷循環(huán)
// 直到條件不滿足時，便找到了大于等于 minsize 的最小 2 的冪次方數(shù)
for (log2_size = PyDict_LOG_MINSIZE;
(((Py_ssize_t)1) << log2_size) < minsize;
log2_size++)
;
return log2_size;
}只不過返回的不是擴(kuò)容之后的字典的容量，而是以 2 為底、容量的對數(shù)。
然后我們來看看擴(kuò)容對應(yīng)的具體邏輯。
// Objects/dictobject.c
static int
insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode)
{
// 當(dāng)字典添加 entry 卻發(fā)現(xiàn)容量不夠時，會調(diào)用 insertion_resize 函數(shù)
// 該函數(shù)內(nèi)部會調(diào)用 dictresize 函數(shù)，傳遞的參數(shù)的含義如下：
/*
* 參數(shù)一：進(jìn)程狀態(tài)對象
* 參數(shù)二：字典
* 參數(shù)三：擴(kuò)容之后的字典的容量的對數(shù)
* 參數(shù)四：是否是 unicode table，即字典的 key 是否都是字符串
*/
return dictresize(interp, mp,
calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
}所以核心在于 dictresize 函數(shù)，但這個函數(shù)比較長，在看它的內(nèi)部實(shí)現(xiàn)之前，先來回顧一下基礎(chǔ)知識。
圖片
以上是字典的底層結(jié)構(gòu)，假設(shè)變量 mp 指向了 PyDictObject 實(shí)例，那么可以得到如下信息。
- mp->ma_keys->dk_indices 便是哈希索引數(shù)組，它的長度便是哈希表的容量。
- mp->ma_keys->dk_entries 便是鍵值對數(shù)組，里面的一個 entry 就是一個鍵值對。
- 如果字典使用的是結(jié)合表，那么 entry 的 me_key、me_value 字段負(fù)責(zé)存儲鍵和值，此時 mp->ma_values 為 NULL。
- 如果字典使用的是分離表，那么 entry 的 me_key 字段負(fù)責(zé)存儲鍵，me_value 字段則始終為 NULL，此時由 mp->ma_values 負(fù)責(zé)存儲值，這種做法可以讓多個字典共享一組 key，從而節(jié)省內(nèi)存。
因?yàn)榉蛛x表是 Python 針對實(shí)例對象的屬性字典單獨(dú)設(shè)計(jì)的，我們平時創(chuàng)建的都是結(jié)合表，所以一開始并沒有討論分離表。但分離表其實(shí)非常簡單，這里來補(bǔ)充一下吧，我們看一下 ma_values 是怎么定義的。
// Include/dictobject.h
typedef struct _dictvalues PyDictValues;
// Include/internal/pycore_dict.h
struct _dictvalues {
PyObject *values[1];
};結(jié)構(gòu)非常簡單，就是維護(hù)了一個數(shù)組，保存所有的 value。另外我們發(fā)現(xiàn)字段 values 是一個數(shù)組，而不是指向數(shù)組首元素的二級指針，這就說明使用分離表的字典的容量是固定的，如果要擴(kuò)容，那么結(jié)構(gòu)會發(fā)生改變，分離表會重構(gòu)為結(jié)合表。
現(xiàn)在假設(shè)有一個字典，里面有三個鍵值對 "a": 1, "b": 2, "c": 3，我們看一下分別使用結(jié)合表和分離表存儲時，字典的結(jié)構(gòu)是什么樣子。
結(jié)合表：
圖片
分離表：
圖片
所以結(jié)合表是鍵和值存在一起，分離表是鍵和值分開存儲，非常好理解。我們自己創(chuàng)建的字典，使用的都是結(jié)合表，分離表是為了減少對象屬性字典的內(nèi)存使用而專門引入的。
然后是字典（哈希表）的三種形式：
- Unicode split table：分離表，key 全部是字符串。
- Unicode combined table：結(jié)合表，key 全部是字符串。
- Generic combined table：結(jié)合表，key 的類型沒有限制。
所以對于一個分離表而言，它的 key 一定都是字符串，否則不可能是分離表。而如果 key 都是字符串，那么既可以是分離表，也可以是結(jié)合表。
但如果不滿足 key 都是字符串，或者說 key 沒有類型限制，那么一定是結(jié)合表。所以 Generic combined table 里面的 combined 可以省略，因?yàn)楫?dāng) key 的類型是 Generic 時，哈希表一定是 combined。
接著是轉(zhuǎn)換關(guān)系：
- split 可以轉(zhuǎn)成 combined，但反過來不行。
- unicode 可以轉(zhuǎn)成 generic，但反過來不行。
好，最后我們看一下 dictresize 函數(shù)。
// Objects/dictobject.c
static int
dictresize(PyInterpreterState *interp, PyDictObject *mp,
uint8_t log2_newsize, int unicode)
{
// mp->ma_keys
PyDictKeysObject *oldkeys;
// mp->ma_values
PyDictValues *oldvalues;
// log2_newsize 是擴(kuò)容之后的字典的容量的對數(shù)
// 它是由 insertion_resize 函數(shù)傳過來的
// SIZEOF_SIZE_T 是一個宏，在 64 位機(jī)器上等于 8
// 所以 log2_newsize 不能超過 64，即字典的容量不能達(dá)到 2 ** 64
if (log2_newsize >= SIZEOF_SIZE_T*8) {
PyErr_NoMemory(); // 否則拋出 MemoryError
return -1;
}
assert(log2_newsize >= PyDict_LOG_MINSIZE);
oldkeys = mp->ma_keys;
oldvalues = mp->ma_values;
// 如果 !(dk->dk_kind != DICT_KEYS_GENERAL)，說明字典之前是 Generic table
// 而一個 Generic table 不可能變成 Unicode table，所以將 unicode 設(shè)置為 0
if (!DK_IS_UNICODE(oldkeys)) {
unicode = 0;
}
// 在介紹字典的創(chuàng)建時，我們說過這個函數(shù)，它負(fù)責(zé)為 PyDictKeysObject 實(shí)例申請內(nèi)存
mp->ma_keys = new_keys_object(interp, log2_newsize, unicode);
if (mp->ma_keys == NULL) {
mp->ma_keys = oldkeys;
return -1;
}
assert(mp->ma_keys->dk_usable >= mp->ma_used);
// 字典的長度
Py_ssize_t numentries = mp->ma_used;
// 如果 oldvalues 不為 NULL，說明字典使用的是分離表
// 那么當(dāng)字典發(fā)生擴(kuò)容時，要轉(zhuǎn)成結(jié)合表
if (oldvalues != NULL) {
// oldentries，一個 entry 16 字節(jié)
PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys);
// split -> Generic combined
if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) {
// newentries，一個 entry 24 字節(jié)
PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
for (Py_ssize_t i = 0; i < numentries; i++) {
int index = get_index_from_order(mp, i);
PyDictUnicodeEntry *ep = &oldentries[index];
assert(oldvalues->values[index] != NULL);
// key 始終存儲在 entry 中
newentries[i].me_key = Py_NewRef(ep->me_key);
// 設(shè)置哈希值
newentries[i].me_hash = unicode_get_hash(ep->me_key);
// 將 mp->ma_values 里面的值，賦值給 entry->me_value
newentries[i].me_value = oldvalues->values[index];
}
// 因?yàn)閿U(kuò)容了，所以遍歷鍵值對數(shù)組，依次對里面的 key 進(jìn)行索引映射
// 找到指定的哈希槽，讓其保存 key 對應(yīng)的 entry 在鍵值對數(shù)組中的索引
// 因此這一步就是在重新構(gòu)建哈希索引數(shù)組
build_indices_generic(mp->ma_keys, newentries, numentries);
}
// split -> Unicode combined
else {
// 代碼和上面是一樣的，唯一的區(qū)別就是這里 entry 的類型和之前是一樣的
// 因?yàn)橹貥?gòu)前后都是 Unicode table，所以 entry 的類型不變
PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys);
for (Py_ssize_t i = 0; i < numentries; i++) {
int index = get_index_from_order(mp, i);
PyDictUnicodeEntry *ep = &oldentries[index];
assert(oldvalues->values[index] != NULL);
newentries[i].me_key = Py_NewRef(ep->me_key);
newentries[i].me_value = oldvalues->values[index];
}
build_indices_unicode(mp->ma_keys, newentries, numentries);
}
dictkeys_decref(interp, oldkeys);
// 釋放 ma_values
mp->ma_values = NULL;
free_values(oldvalues);
}
// 說明字典使用的是結(jié)合表，重構(gòu)的結(jié)果依舊是結(jié)合表
else {
// Generic -> Generic
if (oldkeys->dk_kind == DICT_KEYS_GENERAL) {
assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
PyDictKeyEntry *oldentries = DK_ENTRIES(oldkeys);
PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
// 如果 entry 的數(shù)量等于字典的長度，說明沒有被刪除的 entry
// 那么直接 memcpy 過去即可
if (oldkeys->dk_nentries == numentries) {
memcpy(newentries, oldentries,
numentries * sizeof(PyDictKeyEntry));
}
// 否則要遍歷 oldentries，將 me_value != NULL 的 entry 拷貝過去
else {
PyDictKeyEntry *ep = oldentries;
for (Py_ssize_t i = 0; i < numentries; i++) {
while (ep->me_value == NULL)
ep++;
newentries[i] = *ep++;
}
}
// 重構(gòu)哈希索引數(shù)組
build_indices_generic(mp->ma_keys, newentries, numentries);
}
else {
PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys);
// Unicode combined -> Unicode combined
if (unicode) {
// 邏輯和上面類似，如果不存在被刪除的 entry，那么直接拷貝
// 否則的話，依次遍歷，獲取 me_value 不為 NULL 的 entry
PyDictUnicodeEntry *newentries = DK_UNICODE_ENTRIES(mp->ma_keys);
if (oldkeys->dk_nentries == numentries &&
mp->ma_keys->dk_kind == DICT_KEYS_UNICODE) {
memcpy(newentries, oldentries,
numentries * sizeof(PyDictUnicodeEntry));
}
else {
PyDictUnicodeEntry *ep = oldentries;
for (Py_ssize_t i = 0; i < numentries; i++) {
while (ep->me_value == NULL)
ep++;
newentries[i] = *ep++;
}
}
build_indices_unicode(mp->ma_keys, newentries, numentries);
}
// Unicode combined -> Generic combined
else {
// 因?yàn)榍昂?entry 的大小不一樣，一個 16 字節(jié)，一個 24 字節(jié)
// 所以只能遍歷，然后重新給字段賦值
PyDictKeyEntry *newentries = DK_ENTRIES(mp->ma_keys);
PyDictUnicodeEntry *ep = oldentries;
for (Py_ssize_t i = 0; i < numentries; i++) {
while (ep->me_value == NULL)
ep++;
newentries[i].me_key = ep->me_key;
newentries[i].me_hash = unicode_get_hash(ep->me_key);
newentries[i].me_value = ep->me_value;
ep++;
}
build_indices_generic(mp->ma_keys, newentries, numentries);
}
}
// Py_EMPTY_KEYS 是靜態(tài)定義好的，永遠(yuǎn)存在
// 如果 oldkeys != Py_EMPTY_KEYS，那么要釋放掉
if (oldkeys != Py_EMPTY_KEYS) {
assert(oldkeys->dk_kind != DICT_KEYS_SPLIT);
assert(oldkeys->dk_refcnt == 1);
// 以下是緩存池操作，我們下一篇文章細(xì)說
#if PyDict_MAXFREELIST > 0
struct _Py_dict_state *state = get_dict_state(interp);
if (DK_LOG_SIZE(oldkeys) == PyDict_LOG_MINSIZE &&
DK_IS_UNICODE(oldkeys) &&
state->keys_numfree < PyDict_MAXFREELIST)
{
state->keys_free_list[state->keys_numfree++] = oldkeys;
OBJECT_STAT_INC(to_freelist);
}
else
#endif
{
PyObject_Free(oldkeys);
}
}
}
// dk_usable 表示還可以容納多少個鍵值對
// dk_nentries 表示已經(jīng)容納了多少個鍵值對
// 而 numentries 表示字典的長度，所以重構(gòu)之后
// dk_usable 的大小要減去 numentries，dk_nentries 直接等于 numentries
mp->ma_keys->dk_usable -= numentries;
mp->ma_keys->dk_nentries = numentries;
ASSERT_CONSISTENT(mp);
return 0;
}因?yàn)橐獙１淼姆N類分情況討論，所以導(dǎo)致代碼有點(diǎn)長，但邏輯不難理解：
- 首先確定哈希表的容量，它要滿足 2 的冪次方，并且大于等于 ma_used * 3。
- 為 ma_keys 重新申請內(nèi)存。
- 根據(jù)哈希表的種類分情況討論，但核心都是將老的沒有被刪除的 entry 搬過去。
- 釋放 ma_keys，如果字典之前是分離表，還要釋放 ma_values。
以上就是哈希表的擴(kuò)容，或者說字典的擴(kuò)容，我們就介紹到這兒，下一篇文章來介紹字典的緩存池。
