字典的整理收納課（下）

在上個章節我們已經看到如何建立字典物件，不過隨著字典物件的 dk_indices 陣列越來越滿，發生碰撞的頻率也會越來越高，導致效能下降。所以當容量快不夠的時候，Python 就會自動幫我們增加容量，我們身為一般使用者完全不用擔心這些細節，但是，這是怎麼做到的？

可用空間太小跟系統討更多的記憶體來用，如果一口氣拿了過多的空間，碰撞機率雖然降低了，但同時可能也造成空間的浪費，所以「什麼時候」應該要再去拿更多記憶體空間以及「應該拿多少」，才能在性能跟記憶體空間之間取得平衡？這一章節我們就來看看 Python 是怎麼處理這些問題的。

字典的空間管理術

繼續新增元素

在上個章節我們看到如果是針對全新的字典物件，要加入第一顆元素的時候是呼叫 insert_to_emptydict() 函數，但如果要新增到一個不是空的字典物件裡，也就是要在同一個字典裡加入第二顆物件的時候，它會呼叫 insertdict() 函數。這個函數的行數比較多，做的事也比較複雜，我們分段來看：

檔案：Objects/dictobject.c

static int
insertdict(PyInterpreterState *interp, PyDictObject *mp,
           PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;

    if (DK_IS_UNICODE(mp->ma_keys) && !PyUnicode_CheckExact(key)) {
        if (insertion_resize(interp, mp, 0) < 0)
            goto Fail;
        assert(mp->ma_keys->dk_kind == DICT_KEYS_GENERAL);
    }
    // ... 略 ...
 }

DK_IS_UNICODE() 巨集透過比對這顆字典物件的 ma_keys 成員裡的 dk_kind 確認目前這顆字典物件是否使用了專門為 Unicode 字串做最佳化的狀態，如果是，但接下來要加入的 Key 不是卻 Unicode 字串，例如 hero[42] = "Kitty"，Python 為了可以存放不同類型的 Key，會把原本對已經針對 Unicode 的 Key 最佳化的格式轉換為一般通用的格式，這種轉換本質上就是一個變更容量的操作，所以這裡呼叫了 insertion_resize() 進行容量變更。變更容量的細節晚點再討論，這裡我舉個例子：

import sys

fruits1 = {"apple": "蘋果", "banana": "香蕉"}
fruits2 = {"apple": "蘋果", "banana": "香蕉"}

print(sys.getsizeof(fruits1))
print(sys.getsizeof(fruits2))

fruits1["pineapple"] = "鳳梨"
fruits2[42] = "鳳梨"

print(sys.getsizeof(fruits1))
print(sys.getsizeof(fruits2))

在「為你自己學 Python」一書的字典章節有介紹過，在 Python 裡不是只有字串才能當 Key，只要是可雜湊物件都可以。這裡我分別用字串 "pineapple" 跟數字 42 當做 Key，結果會造成原本一樣的兩個字典變的不一樣大，在我電腦執行之後，會印出以下結果：

184
184
184
352

為什麼 fruits2 的大小會變大呢？因為 fruits2 加入了不是 Unicode 字串的 Key，所以 Python 會把 fruits2 的 dk_kind 從 Unicode 專用格式 DICT_KEYS_UNICODE 轉換為一般通用的格式 DICT_KEYS_GENERAL，這個轉換會增加記憶體的使用量。也就是說，雖然 Python 的字典沒有規定只能用字串，但用字串當做 Key 的效能會是最好的。

再回來 insertdict() 函數繼續往下看：

檔案：Objects/dictobject.c

static int
insertdict(PyInterpreterState *interp, PyDictObject *mp,
           PyObject *key, Py_hash_t hash, PyObject *value)
{
    // ... 略 ...
    Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);

    // ... 略 ...
    if (ix == DKIX_EMPTY) {
        assert(old_value == NULL);
        if (mp->ma_keys->dk_usable <= 0) {
            if (insertion_resize(interp, mp, 1) < 0)
                goto Fail;
        }

        // ... 略 ...
    }
}

這裡再次發現 insertion_resize() 函數，當 ix 的值是 DKIX_EMPTY 時，代表這個 Key 是全新的，也就是要新增這個 Key，這時候就要檢查目前的字典物件是否還有可用的空間，這其實是這個函數裡主要變更容量的檢查點，如果字典裡的空間不夠用的話，就要呼叫 insertion_resize() 函數來增加容量。

這個 dk_usable <= 0 判斷看起來很簡單，但其實不是它帳面上看起來這麼單純...

要拿更多容量嗎？

dk_usable 是 PyDictKeysObject 結構裡的一個成員變數，從名字可能可以猜的出來在這個字典還可以使用的空格數量，但其實不是。如果真的是這樣，這裡判斷 dk_usable <= 0 的話才準備增加容量的話是不是有點太節省啦？前面才提到如果字典內的可用空間不足會因為容易碰撞而導致效能變差，所以等到 db_usable <= 0 才要求更多空間有點沒道理。其實 dk_usable 這個值不是它表面看起來這麼簡單。

先看一下上個章節介紹到的 PyDictKeysObject 結構：

檔案：Include/internal/pycore_dict.h

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    uint8_t dk_log2_size;
    uint8_t dk_log2_index_bytes;
    uint8_t dk_kind;
    uint32_t dk_version;
    Py_ssize_t dk_usable;
    Py_ssize_t dk_nentries;
    char dk_indices[];
};

順便借用上個章節的例子：

dk_indices:
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
|   |   | 2 | 1 |   | 3 |   |   |
+---+---+---+---+---+---+---+---+

來看一下目前這個 PyDictKeysObject 結構的成員變數：

• dk_log2_size 這顆字典的大小是 2³ = 8，就是可以容納 8 個元素的意思，所以這個欄位的值就是 2³ 的 3。
• dk_nentries 也是 3，就是目前這顆字典裡已經存了 3 個 Key，表示目前有 3 個 Entry 的意思。

dk_log2_index_bytes 比較特別一點，另外特別拿出來說明。在上個章節有講到 new_keys_object() 函數，是用來建立一個新的 PyDictKeysObject 結構的，這個函數裡有一段程式碼是這樣寫的：

檔案：Objects/dictobject.c

static PyDictKeysObject*
new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode)
{
    // ... 略 ...
    if (log2_size < 8) {
        log2_bytes = log2_size;
    }
    else if (log2_size < 16) {
        log2_bytes = log2_size + 1;
    }
    else {
        log2_bytes = log2_size + 2;
    }
    // ... 略 ...
}

根據這段程式，dk_log2_index_bytes 的值跟字典的元素數量有關。

在小型的字典（log2_size = 0 ~ 7，也就是 2⁷ = 128 個元素以內）這個值等於 dk_log2_size；如果是中型的字典（2⁸ = 256 到 2¹⁵ = 32,768 個元素內）這個值是 dk_log2_size + 1，如果是大型的字典（2¹⁶ = 65,536 個格子以上）這個值 dk_log2_size + 2。

接下來要介紹一個名詞叫做「負載因子（Load Factor）」，這裡我用 α 表示，這個值的計算公式如下：

α = 已經使用的空間 / 總共可用的空間

以剛才的例子來說，目前已經使用的格子有 3 個，總共可用的格子有 8 個，所以 α 是 3/8，也就是 0.375。在 Python 的字典通常保持一個較低的 α 值以確保高效的操作。隨著字典裡的元素越來越多，當 α 值超過 2/3 的時候，在下回新增元素的時候就會觸發增加容量的機制。

但我們剛剛看到的 dk_usable <= 0 判斷，這個 dk_usable 是怎麼算的？跟 α 值的關係又是什麼？來看一下：

檔案：Objects/dictobject.c

static PyDictKeysObject*
new_keys_object(PyInterpreterState *interp, uint8_t log2_size, bool unicode)
{
    PyDictKeysObject *dk;
    Py_ssize_t usable;
    // ... 略 ...

    usable = USABLE_FRACTION((size_t)1<<log2_size);
    // ... 略 ...
}

把 USABLE_FRACTION() 巨集展開：

檔案：Objects/dictobject.c

#define USABLE_FRACTION(n) (((n) << 1)/3)

<< 1 位元左移就是乘以 2，/ 3 等於除以 3，所以這個巨集計算出來的結果，就是我們剛剛提到的 2/3 總容量。再次借用剛才的範例計算：

  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
|   |   | 2 | 1 |   | 3 |   |   |
+---+---+---+---+---+---+---+---+

在這個範例中，一開始總空間是 8 格，dk_usable 是 USABLE_FRACTION(8)，算出來的答案是 8 x 2 / 3 = 5。也就是說，以一個剛剛出生的新字典，它的 dk_usable 等於 5。接下來不管是呼叫 insert_to_emptydict() 或是 insertdict() 函數，只要新增一個 Key，dk_usable 就會減 1。在我們的範例中已經新增了 3 個 Key，所以現在的 dk_usable 是 5 - 3 = 2，表示現在字典裡的空間「還可以再放 2 個元素」才會觸發增加容量的機制。

所以，dk_usable 實際上比較像是一個計數器，表示在這個字典還可以再放多少個新元素項目而不需要 resize。當 dk_usable 減到 0 或更小時，就是表示 α 值已經超過 2/3 了，是時候該去要更多的記憶體來用了。

只是，我好奇的是為什麼是 2/3？這個數字是怎麼來的？我從原始碼裡看不太出來，但我想字典這個資料結構在 Python 也行之有年，我猜核心開發者們基於實驗以及用各種不同負載因子的性能測試最終得到 2/3 這個數字。

現在知道這些值之間的關係之後，我們來看一下增加元素時候的變化：

+---------+------------+-----------+---------+
| dk_size | dk_entries | dk_usable |    α    |
+---------+------------+-----------+---------+
|    8    |     3      |     2     |  0.375  |
+---------+------------+-----------+---------+
|    8    |     4      |     1     |  0.5    |
+---------+------------+-----------+---------+
|    8    |     5      |     0     |  0.625  |
+---------+------------+-----------+---------+

原本 8 格，目前用了 5 個，db_usable 已經是 0 了，到了差不多該增加容量的時候了，如果再新增一個元素的話：

+---------+------------+-----------+---------+
| dk_size | dk_entries | dk_usable |    α    |
+---------+------------+-----------+---------+
|    8    |     3      |     2     |  0.375  |
+---------+------------+-----------+---------+
|    8    |     4      |     1     |  0.5    |
+---------+------------+-----------+---------+
|    8    |     5      |     0     |  0.625  |
+---------+------------+-----------+---------+
|   16    |     6      |     4     |  0.375  |
+---------+------------+-----------+---------+

這時候整體的容量會變成 16 格，為什麼是 16 格待會我再算給大家看。因為加了一個新元素，所以 db_entries 從原本的 5 變成 6，但因為 dk_size 變大了，所以 dk_usable 也會變多，α 值也會跟著變小。也就是藉由增加容量讓 α 值維持在 2/3 以下，降低發生碰撞的機會。

該拿多少空間？

現在知道大概用到超過 2/3 左右的空間的之後，如果還要再新增元素的話，Python 會再跟系統要更多的記憶體空間，但要增加多少呢？一次拿太多可能會造成浪費，一次拿太少過不久又要再拿一次，效能可能又沒那麼好。怎麼說？並不是只有拿更多記憶體空間回來就沒事了，拿到新的空間之後，還要把原本的元素根據每個元素的 hash 值再重新計算過再放到新的空間裡，這個過程是很耗時的。

那麼 Python 擴張容量的策略是什麼？在 insertion_resize() 函數裡有提到：

檔案：Objects/dictobject.c

static int
insertion_resize(PyInterpreterState *interp, PyDictObject *mp, int unicode)
{
    return dictresize(interp, mp, calculate_log2_keysize(GROWTH_RATE(mp)), unicode);
}

這個 GROWTH_RATE(mp) 巨集看名字就知道應該是什麼意思，看看它是怎麼定義的：

檔案：Objects/dictobject.c

#define GROWTH_RATE(d) ((d)->ma_used*3)

嗯...會把目前字典裡已使用的元素數量乘以 3，我們拿剛才的例子來算算看：

+---------+------------+-----------+---------+
| dk_size | dk_entries | dk_usable |    α    |
+---------+------------+-----------+---------+
|    8    |     4      |     1     |  0.5    |
+---------+------------+-----------+---------+
|    8    |     5      |     0     |  0.625  |
+---------+------------+-----------+---------+

假設現在已經用了 5 個元素，所以 GROWTH_RATE() 巨集計算的結果會是 5 x 3 = 15，也就是說如果要增加容量的話，會從原本的 8 格擴增到 15 格。但因為 Python 的字典的空間有規定要是 2ⁿ 格，所以這個 15 格會被上修變成要拿滿 16 格。

好，假設現在拿了 16 格了，如果繼續新增元素的話，當 dk_entries 達到 10 的時候，dk_usable 就又會變成 0，再新增一個元素的話，會要再拿 10 x 3 = 30 格，然後會被上修至 2⁵ = 32 格。

按這個機制算下去，當字典容量不足的時候，差不多每次就是以兩倍的速度在擴張。如果剛剛你有跟著我追原始碼，在註解裡會看到 GROWTH_RATE 其實在不同的 Python 版本有不同的值：

• GROWTH_RATE was set to used*4 up to version 3.2.
• GROWTH_RATE was set to used*2 in version 3.3.0
• GROWTH_RATE was set to used*2 + capacity/2 in 3.4.0-3.6.0.

一開始是乘以 4，後來改成乘以 2，後來又改成乘以 2 再加上一半的容量，直到現在的版本是乘以 3。我猜這個值的設定也是經過不斷的實驗以及性能測試得來的，看到這裡，深深覺得數學跟演算法在這時候就很重要了！

有借有還...嗎？

現在我們知道字典的容量不夠的時候會去要更多的記憶體空間，但如果字典裡的元素數量變少了，Python 會把多餘的空間釋放掉嗎？想想看在我們的日常生活中，如果油價上漲的時候很多民生用品都會跟著漲價，但如果油價下跌的時候，民生用品的價格會跟著下降嗎？嗯...其實你也知道答案不是嗎？

例如空間從 8 格擴充到 16 格，如果這時候把這個字典裡的元素都刪掉，空間會退回 8 格嗎？答案是不會的。Python 的字典的容量不會因為元素數量變少而減少容量，如果會的話，這樣每次刪除元素的時候都要重新計算一次容量，這樣的話效能會變差。我來寫一段程式證明給大家看：

from sys import getsizeof

heroes = {
    "Frieren": "芙莉蓮",
    "Himmel": "欣梅爾",
    "Heiter": "海塔",
    "Fern": "費倫",
    "Stark": "修塔爾克",
}
print(getsizeof(heroes))

# 加 1 個，這裡會觸發增加容量的機制
heroes["Eisen"] = "艾冉"
print(getsizeof(heroes))

# 刪掉 3 個
del heroes["Eisen"]
del heroes["Stark"]
del heroes["Fern"]
print(getsizeof(heroes))

在原本 5 個元素之再加 1 個，會造成字典的容量擴張，從原本的 8 格增加到 16 格。但後面再刪掉 3 個的時候，擴張的容量並沒有變小。在我電腦執行之後的結果是：

184
272
272

如果你真的很想要把字典的容量縮小，有幾種做法。首先可以呼叫字典的 .clear() 方法清空字典，空間就會被還回來，如果想知道這怎麼做的，可以追一下在 Objects/dictobject.c 檔案裡的 PyDict_Clear() 函數，在這個函數裡你會看到清空字典裡的元素之後，還會把釋放佔用的記憶體。

另一個做法是 heroes = {}，直接讓這個變數指向一個全新的空字典，這樣原本的字典待會就會被資源回收機制給收掉，可以達到一樣的效果。只是通常需要真的這麼計較空間的機會不多，而且在 Python 這種小型字典的使用機會很多，如果每次都得這樣玩，程式碼寫起來就會變得囉嗦了。