字典是怎么擴容的？它會經歷哪些過程？

作者：古明地覺 2024-08-29 12:37:11

擴容之后的新哈希表的容量要大于等于 ma_used * 3，注意：是大于等于?ma_used * 3，不是?dk_nentries * 3。因為 dk_nentries 還包含了被刪除的 entry，但哈希表在擴容的時候會將其丟棄，所以擴容之后新哈希表的容量取決于 ma_used。

在介紹字典的底層結構時我們看到，當已使用的 entry 數量達到總容量的 2/3 時，會發生擴容。

而在早期，哈希表只使用一個鍵值對數組，這個鍵值對數組不僅要存儲具體的 entry，還要承載哈希索引數組的功能。本來這個方式很簡單，但是內存浪費嚴重，于是后面 Python 官方就將一個數組拆成兩個數組來實現。

不是說只能用 2/3 嗎？那就只給鍵值對數組申請 2/3 容量的空間，并且只負責存儲鍵值對。至于索引，則由哈希索引數組來體現。通過將 key 映射成索引，找到指定的哈希槽，再根據槽里面存儲的索引，找到鍵值對數組中存儲的 entry。

因此減少內存開銷的核心就在于，避免鍵值對數組的浪費。

所以哈希索引數組的長度就可以看成是哈希表的容量，而鍵值對數組的長度本身就是哈希索引數組的 2/3、或者說容量的 2/3。那么很明顯，當鍵值對數組滿了，就說明當前的哈希表要擴容了。

// Objects/dictobject.c
#define GROWTH_RATE(d) ((d)->ma_used*3)

擴容之后的新哈希表的容量要大于等于 ma_used * 3，注意：是大于等于 ma_used * 3，不是 dk_nentries * 3。因為 dk_nentries 還包含了被刪除的 entry，但哈希表在擴容的時候會將其丟棄，所以擴容之后新哈希表的容量取決于 ma_used。

當然啦，哈希表的容量還要等于 2 的冪次方，所以有兩個條件：

大于等于 ma_used * 3；
等于 2 的冪次方；

基于以上兩個限制條件，取到的最小值便是擴容之后的容量。為此 Python 底層專門提供了一個 calculate_log2_keysize 函數，看一下它的邏輯。

// Objects/dictobject.c
static inline uint8_t
calculate_log2_keysize(Py_ssize_t minsize)
{
    // 參數 minsize 表示字典的 ma_used * 3，即長度 * 3
    // 1 << log2_size 便是擴容之后的字典的容量
    uint8_t log2_size;
    // PyDict_LOG_MINSIZE 是一個宏，值為 3，所以字典的最小容量是 8
    // 如果 (1 << log2_size) < minsize，那么不斷循環
    // 直到條件不滿足時，便找到了大于等于 minsize 的最小 2 的冪次方數
    for (log2_size = PyDict_LOG_MINSIZE;
            (((Py_ssize_t)1) << log2_size) < minsize;
            log2_size++)
        ;
    return log2_size;
}

只不過返回的不是擴容之后的字典的容量，而是以 2 為底、容量的對數。

然后我們來看看擴容對應的具體邏輯。

// Objects/dictobject.c
static int
insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode)
{
    // 當字典添加 entry 卻發現容量不夠時，會調用 insertion_resize 函數
    // 該函數內部會調用 dictresize 函數，傳遞的參數的含義如下：
    /*
     * 參數一：進程狀態對象
     * 參數二：字典
     * 參數三：擴容之后的字典的容量的對數
     * 參數四：是否是 unicode table，即字典的 key 是否都是字符串
     */
    return dictresize(interp, mp, 
        calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
}

所以核心在于 dictresize 函數，但這個函數比較長，在看它的內部實現之前，先來回顧一下基礎知識。

圖片

以上是字典的底層結構，假設變量 mp 指向了 PyDictObject 實例，那么可以得到如下信息。

mp->ma_keys->dk_indices 便是哈希索引數組，它的長度便是哈希表的容量。
mp->ma_keys->dk_entries 便是鍵值對數組，里面的一個 entry 就是一個鍵值對。
如果字典使用的是結合表，那么 entry 的 me_key、me_value 字段負責存儲鍵和值，此時 mp->ma_values 為 NULL。
如果字典使用的是分離表，那么 entry 的 me_key 字段負責存儲鍵，me_value 字段則始終為 NULL，此時由 mp->ma_values 負責存儲值，這種做法可以讓多個字典共享一組 key，從而節省內存。

因為分離表是 Python 針對實例對象的屬性字典單獨設計的，我們平時創建的都是結合表，所以一開始并沒有討論分離表。但分離表其實非常簡單，這里來補充一下吧，我們看一下 ma_values 是怎么定義的。

// Include/dictobject.h
typedef struct _dictvalues PyDictValues;
// Include/internal/pycore_dict.h
struct _dictvalues {
    PyObject *values[1];
};

結構非常簡單，就是維護了一個數組，保存所有的 value。另外我們發現字段 values 是一個數組，而不是指向數組首元素的二級指針，這就說明使用分離表的字典的容量是固定的，如果要擴容，那么結構會發生改變，分離表會重構為結合表。

現在假設有一個字典，里面有三個鍵值對 "a": 1, "b": 2, "c": 3，我們看一下分別使用結合表和分離表存儲時，字典的結構是什么樣子。

結合表：

圖片

分離表：

圖片

所以結合表是鍵和值存在一起，分離表是鍵和值分開存儲，非常好理解。我們自己創建的字典，使用的都是結合表，分離表是為了減少對象屬性字典的內存使用而專門引入的。

然后是字典（哈希表）的三種形式：

Unicode split table：分離表，key 全部是字符串。
Unicode combined table：結合表，key 全部是字符串。
Generic combined table：結合表，key 的類型沒有限制。

所以對于一個分離表而言，它的 key 一定都是字符串，否則不可能是分離表。而如果 key 都是字符串，那么既可以是分離表，也可以是結合表。

但如果不滿足 key 都是字符串，或者說 key 沒有類型限制，那么一定是結合表。所以 Generic combined table 里面的 combined 可以省略，因為當 key 的類型是 Generic 時，哈希表一定是 combined。

接著是轉換關系：

split 可以轉成 combined，但反過來不行。
unicode 可以轉成 generic，但反過來不行。

好，最后我們看一下 dictresize 函數。

// 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 是擴容之后的字典的容量的對數
    // 它是由 insertion_resize 函數傳過來的
    // SIZEOF_SIZE_T 是一個宏，在 64 位機器上等于 8
    // 所以 log2_newsize 不能超過 64，即字典的容量不能達到 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 設置為 0
    if (!DK_IS_UNICODE(oldkeys)) {
        unicode = 0;
    }

    // 在介紹字典的創建時，我們說過這個函數，它負責為 PyDictKeysObject 實例申請內存
    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，說明字典使用的是分離表
    // 那么當字典發生擴容時，要轉成結合表
    if (oldvalues != NULL) {
        // oldentries，一個 entry 16 字節
        PyDictUnicodeEntry *oldentries = DK_UNICODE_ENTRIES(oldkeys);
        // split -> Generic combined
        if (mp->ma_keys->dk_kind == DICT_KEYS_GENERAL) {
            // newentries，一個 entry 24 字節
            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);
                // 設置哈希值
                newentries[i].me_hash = unicode_get_hash(ep->me_key);
                // 將 mp->ma_values 里面的值，賦值給 entry->me_value
                newentries[i].me_value = oldvalues->values[index];
            }
            // 因為擴容了，所以遍歷鍵值對數組，依次對里面的 key 進行索引映射
            // 找到指定的哈希槽，讓其保存 key 對應的 entry 在鍵值對數組中的索引
            // 因此這一步就是在重新構建哈希索引數組
            build_indices_generic(mp->ma_keys, newentries, numentries);
        }
        // split -> Unicode combined
        else { 
            // 代碼和上面是一樣的，唯一的區別就是這里 entry 的類型和之前是一樣的
            // 因為重構前后都是 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);
    }
    // 說明字典使用的是結合表，重構的結果依舊是結合表
    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 的數量等于字典的長度，說明沒有被刪除的 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++;
                }
            }
            // 重構哈希索引數組
            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 {
                // 因為前后 entry 的大小不一樣，一個 16 字節，一個 24 字節
                // 所以只能遍歷，然后重新給字段賦值
                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 是靜態定義好的，永遠存在
        // 如果 oldkeys != Py_EMPTY_KEYS，那么要釋放掉
        if (oldkeys != Py_EMPTY_KEYS) {
            assert(oldkeys->dk_kind != DICT_KEYS_SPLIT);
            assert(oldkeys->dk_refcnt == 1);
            // 以下是緩存池操作，我們下一篇文章細說
#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 表示已經容納了多少個鍵值對
    // 而 numentries 表示字典的長度，所以重構之后
    // dk_usable 的大小要減去 numentries，dk_nentries 直接等于 numentries
    mp->ma_keys->dk_usable -= numentries;
    mp->ma_keys->dk_nentries = numentries;
    ASSERT_CONSISTENT(mp);
    return 0;
}

因為要對哈希表的種類分情況討論，所以導致代碼有點長，但邏輯不難理解：

首先確定哈希表的容量，它要滿足 2 的冪次方，并且大于等于 ma_used * 3。
為 ma_keys 重新申請內存。
根據哈希表的種類分情況討論，但核心都是將老的沒有被刪除的 entry 搬過去。
釋放 ma_keys，如果字典之前是分離表，還要釋放 ma_values。

以上就是哈希表的擴容，或者說字典的擴容，我們就介紹到這兒，下一篇文章來介紹字典的緩存池。

責任編輯：武曉燕來源：古明地覺的編程教室

字典過程鍵值