本文同步刊載於 「為你自己學 Python - 字典的整理收納課（上）」
跟串列一樣，Python 的字典（dict）是很常使用的資料型態，字典透過 Key & Value 的方式存取，效能相當好，這個章節我們就來看看 Python 裡的字典是怎麼實作的。
大家從前面看到現在這個章節，大概可以不用看原始碼就能猜到在 CPython 裡字典的物件叫什麼名字，是的，就是 PyDictObject。來看看這傢伙的結構長什麼樣子：
在 CPython 裡，字典的內部結構定義在 Include/dictobject.h 檔案中，我把結構裡的一些條件編譯拿掉，看起來像這樣：
// 檔案：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;
先不論這些欄位是什麼用途，可以看到在這個結構裡有好幾個成員都是 ma_ 開頭的，這什麼意思？這是 Python 的命名慣例，ma 代表 Mapping，這是 Python 裡的一個通用名詞，表示可以透過 Key / Value 方式存取的資料結構，像是字典、集合等等。其實我們之前也有看過類似的慣例，像是：
ob_：用在 PyObject 裡的成員，例如 ob_refcnt、ob_size 等。tp_：用於 PyTypeObject 裡的成員，例如 tp_name、tp_init 等。sq_：用於序列（Sequence）的成員，例如 sq_length、sq_item 等。nb_：用於數字類型的成員，例如 nb_add、nb_subtract 等。co_：用於程式碼物件（Code Object）的成員，例如 co_argcount、co_consts 等。回到 PyDictObject 結構，這裡有幾個重要的成員：
ma_used：目前這個字典裡的元素數量。ma_keys：一個 PyDictKeysObject 物件。ma_values：一個 PyDictValues 物件。嗯...初步看起來像是一個字典物件裡的 Key 跟 Value 是分開成不同的物件存放的？感覺有點不太合理，為什麼不直接放在同一個物件裡就好？沒關係，先繼續往下看看這兩個結構裡有什麼，先看 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[];
};
裡面大概有 Reference Count，還有一些目前看不太出來用途的成員，沒關係，再接著看 PyDictValues 結構：
// 檔案：Include/internal/pycore_dict.h
struct _dictvalues {
PyObject *values[1];
};
裡面只有個簡單的 values 成員，相當簡單，但看到這裡，我的問題就是如果這麼簡單的結構，為什麼不直接擺在 PyDictKeysObject 裡就好？我們先看看 Python 是怎麼建立一個新的字典物件。
照著我們之前學過的流程，這應該會去找 PyDict_Type 型別的 tp_new 成員：
// 檔案：Objects/dictobject.c
static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
// ... 略 ...
PyObject *self = type->tp_alloc(type, 0);
if (self == NULL) {
return NULL;
}
// ... 略 ...
return self;
}
果然也是先去找 tp_alloc，結果會發現字典的 tp_alloc 成員也是指向 _PyType_AllocNoTrack() 函數，這跟在上個章節看到的串列物件是一樣的，也就是說串列跟字典雖然看起來結構不太一樣，但在計算以及取得記憶體的方式是一樣的。再回來 dict_new 往下看：
// 檔案：Objects/dictobject.c
static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
// ... 略 ...
PyDictObject *d = (PyDictObject *)self;
d->ma_used = 0;
d->ma_version_tag = DICT_NEXT_VERSION(
_PyInterpreterState_GET());
dictkeys_incref(Py_EMPTY_KEYS);
d->ma_keys = Py_EMPTY_KEYS;
d->ma_values = NULL;
// ... 略 ...
}
看起來是在做初始化，把 ma_used 設定成 0，表示目前字典裡沒有元素，然後把 ma_values 設定成 NULL 表示現在沒有值，這些比較容易理解。但 ma_keys 指向的 Py_EMPTY_KEYS 是什麼：
// 檔案：Objects/dictobject.c
static PyDictKeysObject empty_keys_struct = {
_Py_IMMORTAL_REFCNT, /* dk_refcnt */
0, /* dk_log2_size */
0, /* dk_log2_index_bytes */
DICT_KEYS_UNICODE, /* dk_kind */
1, /* dk_version */
0, /* dk_usable (immutable) */
0, /* dk_nentries */
{DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};
Py_EMPTY_KEYS 其實就是一個 PyDictKeysObject 物件，不過比較特別是這個空字典不能被改變，也是個不會被銷毀的不死身物件，這樣可以讓所有的空字典共用這個物件，這樣可以節省記憶體，也可以避免重複建立空字典物件。
另外，在這個空的 Key 物件的最後放了 8 個 DKIX_EMPTY，DKIX_EMPTY 的值是 -1，用來表示這個位置是空的，如果在查找的過程中得到這個值，表示這個位置是空的，不用再繼續往下找。
也就是說，即使是空的字典，也還是會分配一些空間給它，的確這樣會造成一些浪費，但站在效能的角度來看，對於不到 8 個 Key/Value 的字典來說，可以直接使用這個預分配的空間，可以省下一些記憶體的分配時間，就是有點用空間換取時間的概念。
看到這裡，我好像稍微可以理解為什麼字典的 Key 跟 Value 要分開成不同的物件了。
知道大概字典物件的結構後，接著來看看新增元素的流程。假設我有個空的字典，然後試著在這個字典裡新增一個 Key，並且把 "悟空" 指定給它：
hero = {}
hero["name"] = "悟空"
字典透過中括號存取元素的過程，根據我們看到現在，應該能猜出來是放在 PyDict_Type 的 tp_as_mapping 成員裡：
// 檔案：Objects/dictobject.c
static PyMappingMethods dict_as_mapping = {
(lenfunc)dict_length, /*mp_length*/
(binaryfunc)dict_subscript, /*mp_subscript*/
(objobjargproc)dict_ass_sub, /*mp_ass_subscript*/
};
而 hero["name"] = "悟空" 這個行為，應該會觸發 dict_ass_sub 方法：
// 檔案：Objects/dictobject.c
static int
dict_ass_sub(PyDictObject *mp, PyObject *v, PyObject *w)
{
if (w == NULL)
return PyDict_DelItem((PyObject *)mp, v);
else
return PyDict_SetItem((PyObject *)mp, v, w);
}
這段滿容易懂的，接下來應該就是呼叫 PyDict_SetItem() 函數，不過追進 PyDict_SetItem() 會看到又呼叫了 _PyDict_SetItem_Take2()，我猜 _Take2 這名字大概是想不到好名字所以就先這樣命名的吧。
// 檔案：Objects/dictobject.c
int
_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
{
// ... 略 ...
Py_hash_t hash;
if (!PyUnicode_CheckExact(key) || (hash = unicode_get_hash(key)) == -1) {
hash = PyObject_Hash(key);
if (hash == -1) {
Py_DECREF(key);
Py_DECREF(value);
return -1;
}
}
// ... 略 ...
}
首先會先檢查這個 key 是不是 Unicode 字串，如果是的話就執行 unicode_get_hash() 計算雜湊值，否則就執行 PyObject_Hash() 函數計算雜湊值。我個人其實沒很喜歡這麼「簡潔」的寫法，但也許是我自己能力不足所以得多花一點時間看懂它。先看看 unicode_get_hash() 怎麼計算：
// 檔案：Objects/dictobject.c
static inline Py_hash_t
unicode_get_hash(PyObject *o)
{
assert(PyUnicode_CheckExact(o));
return _PyASCIIObject_CAST(o)->hash;
}
這個函數用了 inline 的寫法，表示這個函數會被直接插入到呼叫的地方，雖然編譯之後的檔案可能會大一點，但可以省下一些函數呼叫的時間，看起來是要拼速度的樣子，也是用空間換時間的做法。而這個函數的結果就只是回傳我們之前介紹過的 PyASCIIObject 的 hash 成員而已，這個 hash 是在建立 Unicode 物件時就計算好的。那另一個 PyObject_Hash() 函數又是怎麼計算的呢？
// 檔案：Objects/object.c
Py_hash_t
PyObject_Hash(PyObject *v)
{
PyTypeObject *tp = Py_TYPE(v);
if (tp->tp_hash != NULL)
return (*tp->tp_hash)(v);
// ... 略 ...
return PyObject_HashNotImplemented(v);
}
就是直接回傳這個物件的型別的 tp_hash 成員而已。知道雜湊值怎麼算之後，再回來往下看：
// 檔案：Objects/dictobject.c
int
_PyDict_SetItem_Take2(PyDictObject *mp, PyObject *key, PyObject *value)
{
// ... 略 ...
PyInterpreterState *interp = _PyInterpreterState_GET();
if (mp->ma_keys == Py_EMPTY_KEYS) {
return insert_to_emptydict(interp, mp, key, hash, value);
}
return insertdict(interp, mp, key, hash, value);
}
如果這個字典是空的，也就是 ma_keys 是 Py_EMPTY_KEYS，會呼叫 insert_to_emptydict() 函數，否則就執行 insertdict() 函數，這兩個函數應該就是這整串流程的重點了。先看 insert_to_emptydict() 函數，不過這個函數做的事比較多，我們先看第一部份：
// 檔案：Objects/dictobject.c
static int
insert_to_emptydict(PyInterpreterState *interp, PyDictObject *mp,
PyObject *key, Py_hash_t hash, PyObject *value)
{
// ... 略 ...
PyDictKeysObject *newkeys = new_keys_object(
interp, PyDict_LOG_MINSIZE, unicode);
// ... 略 ...
mp->ma_keys = newkeys;
mp->ma_values = NULL;
MAINTAIN_TRACKING(mp, key, value);
size_t hashpos = (size_t)hash & (PyDict_MINSIZE-1);
dictkeys_set_index(mp->ma_keys, hashpos, 0);
}
這裡呼叫 new_keys_object() 函數建立一個新的 PyDictKeysObject 物件，然後把這個物件指定給 ma_keys 成員，然後把 ma_values 設定成 NULL。
然後我們剛剛不是有算出這個 Key 對應到的雜湊值嗎？在這裡會再利用這個雜湊值來計算它的「位置」。這裡 PyDict_MINSIZE 的值是 8，所以 & (PyDict_MINSIZE-1) 的效果等同於 % 8，也就是取 8 的餘數，只是用二進位的方式運算比較快而已。要算什麼位置？就是它待會在這顆 PyDictKeysObject 物件，也就是 newkeys 裡的 dk_indices 陣列裡的哪個位置。
你可能會想，如果是取 8 的餘數，那不是只有 0 到 7 共 8 個位置嗎？格子夠不夠是一回事，晚點我們可以再想辦法增加格子，但這樣不會重複嗎？當然有機會重複的，當發生重複的 hashpos 時，又稱為「雜湊碰撞（Hash Collision）」。Python 使用「開放定址法（Open Addressing）」的策略來解決，這策略聽起來很厲害，但其實就是「找下一個沒人用的空間」而已。舉個例子，例如原本有 8 個格子，全部都是空的：
dk_indices:
0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
| | | | | | | | |
+----+----+----+----+----+----+----+----+
如果現在來個 hero["aa"] = "Hello"，表示要新增一個 Key 叫做 "aa"，假設這個 "aa" 字串的 hash 值 81761723，那麼 hashpos 就是 81761723 % 8，也就是 3，這時候就會把這個 key 放在索引值 3 的位置：
dk_indices:
0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
| | | | aa | | | | |
+----+----+----+----+----+----+----+----+
同理，hero["bb"] = "World"，表示要加一個 Key "bb"，假設 "bb" 字串的 hash 值是 28716210，那麼它的 hashpos 就是 28716210 % 8，也是 2，它就會被放在索引值 2 的位置：
dk_indices:
0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
| | | bb | aa | | | | |
+----+----+----+----+----+----+----+----+
到這裡都還很順利，但如果算出來的索引值已經有東西了呢？
我想要再來個 hero["cc"] = "Kitty"，表示要再加一個 Key "cc"，假設 "cc" 字串的 hash 值是 14500523，計算出來的 hashpos 是 3，但是這個位置已經有東西了，這就是所謂的碰撞。
發生碰撞的時候，Python 會試著幫我們找下一個可以用的空間。最直覺的想法可能會是 i + 1 找下一個，萬一還是被佔用就 i + 2，依此類推。像這樣的「線性探測（Linear Probing）」的策略是單純，但這樣可能會造成「聚集（Clustering）」的情形，也就是越後面的位置越容易被佔滿，查找的時間就會增加。老實說我想都沒想過這種問題，我也是看到原始碼才知道為了效能，需要考慮的事情這麼多。
Python 遇到碰撞的時候採用的不是 i + 1 的線性探測，而是採用另外的計算公式：
i = ((5 * i) + 1) % 8
不只這樣，Python 為了增加隨機性，還會對 Key 的 hash 下手，讓它一次右移 5 個位元，讓這個右移之後的結果加到原本的公式裡：
i = ((5 * i) + p + 1) % 8
這個 p 就是 hash 右移 5 個位元的結果，目的是讓碰撞的處理更加均勻。當然一直往右移到最後 p 也會變 0，最後還是變回原本的公式，但至少在過程中想辦法增加一些隨機性。如果大家有機會在翻 CPython 原始碼的時候看到這樣的寫法：
perturb >>= PERTURB_SHIFT;
i = mask & (i*5 + perturb + 1);
其實就是在做這件事，其中 PERTURB_SHIFT 在 CPython 的值就是 5。那我們把 "cc" 字串的 hash 值 14500523 代入這個公式：
i = ((5 * 3) + (14500523 >> 5) + 1) % 8
計算之後會得到 5，這樣 "cc" 就會被放在索引值 5 的位置：
dk_indices:
0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
| | | bb | aa | | cc | | |
+----+----+----+----+----+----+----+----+
用這種方式，在空間足夠的情況下，可以讓平均查找時間接近 O(1)，因為大多數空間足夠的情況下，都能透過 hashpos 的計算直接找到正確的位置。知道 Key 放哪裡後，接下來就是把 Key 跟 Value 放進去：
// 檔案：Objects/dictobject.c
static int
insert_to_emptydict(PyInterpreterState *interp, PyDictObject *mp,
PyObject *key, Py_hash_t hash, PyObject *value)
{
// ... 略 ...
if (unicode) {
PyDictUnicodeEntry *ep = DK_UNICODE_ENTRIES(mp->ma_keys);
ep->me_key = key;
ep->me_value = value;
}
else {
PyDictKeyEntry *ep = DK_ENTRIES(mp->ma_keys);
ep->me_key = key;
ep->me_hash = hash;
ep->me_value = value;
}
mp->ma_used++;
mp->ma_version_tag = new_version;
mp->ma_keys->dk_usable--;
mp->ma_keys->dk_nentries++;
return 0;
}
這裡會根據 Key 是不是 Unicode 字串來決定要放在哪種結構裡，可能是 PyDictKeyEntry 或是 PyDictUnicodeEntry，這兩個的結構如下：
// 檔案：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 跟 Value 的組合而已。在函數的最後更新 ma_used、ma_version_tag、dk_usable 跟 dk_nentries 等成員，這樣就完成了一個 Key/Value 的新增操作。
但是這個 Entry 擺在哪裡？其實它是緊跟著剛剛前面建立的 newkeys，也就是 PyDictKeysObject 物件的後面，如果要找到它們的話，就是透過 DK_ENTRIES() 或是 DK_UNICODE_ENTRIES() 這兩個巨集，如果追過去看的話，會發現這兩個巨集都是根據 ma_keys 的記憶體位置算出來在哪裡。是說這怎麼看出來的？在 new_keys_object() 函數最後有這麼一段：
// 檔案：Objects/dictobject.c
dk = PyObject_Malloc(sizeof(PyDictKeysObject)
+ ((size_t)1 << log2_bytes)
+ entry_size * usable);
照理說跟系統要記憶體應該就取得夠用的就好，但在這裡卻多要了 entry_size * usable 的空間，多要的這個空間就是用來放這些 Entry 的。
但這些物件們的關連要怎麼串起來？還記得剛才有透過取 8 的餘數計算索引值然後把 Key 擺放在指定的格子裡嗎？
dk_indices:
0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
| | | bb | aa | | cc | | |
+----+----+----+----+----+----+----+----+
但其實並不是在這個格子裡直接存放 "aa"、"bb"、"cc" 這些 Key，而是會存放這個 Key 對應的 Entry 的位置。什麼意思？讓我再畫個圖：
dk_indices:
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| | | 2 | 1 | | 3 | | |
+---+---+---+---+---+---+---+---+
dk_entries:
+---+----------------------------+
| 0 | DKIX_DUMMY |
+---+----------------------------+
| 1 | {81761723, "aa", "Hello"} |
+---+----------------------------+
| 2 | {28716210, "bb", "World"} |
+---+----------------------------+
| 3 | {14500523, "cc", "Kitty"} |
+---+----------------------------+
Entry 是按照新增的順序填充進去的，而在 dk_indices 只會存放這些 Entry 的索引值，這樣在查找的時候就可以直接找到這個 Entry 的位置，這樣就可以達到快速查找的效果。
雖然有點複雜，但看起來好像可以對起來沒錯...等等，剛剛有提到如果發生碰撞的時候，會往下找下一個有空位的地方，那這麼不就會造成索引對不起來了嗎？這是個好問題，讓我們來看看查找元素的流程。
當在 Python 的字典裡找一個 Key 的時候，例如 hero["aa"]，會經過以下步驟：
"aa" 本身是個字串物件，所以首先先取得這個 "aa" 字串的 hash 值，以上面的例子來說會得到 81761723。dk_indices 找到對應的值，得到 1。dk_entries 陣列拿資料，找到對應的 Entry，最終可以得到 "Hello" 字串。如果找不到，就會在步驟 C 的時候發現在 dk_indices 的對應格子裡是空的，也就是得到 DKIX_EMPTY，表示這個 Key 不存在，然後丟出 KeyError 的例外。
問題是，如果發生碰撞的時候呢？例如上面例子的 hero["cc"]：
"cc" 字串的 hash 值，得到 14500523。dk_indices 找到對應的值，得到 1。dk_entries 陣列拿資料，找到對應的 Entry，但比對之後就會發現這個 Key 的 hash 值對不起來，表示這個 Entry 並不是我要找的那個。(5 x 3 + perturb + 1) % 8 計算的結果，得到 5。dk_entries 找到對應的 Entry，經比對後發現這就是我要找的那個，打完收工！(5 x 5 + perturb + 1) % 8，計算索引值再進行步驟 D，以此類推。DKIX_EMPTY，就表示這個 Key 不存在這個字典裡，丟出 KeyError 的例外。字典的查找流程看起來有點複雜，但這些計算的速度都滿快的，可以讓字典在大多數情況下都能達到 O(1) 的查找效率。是說如果遇到碰撞的次數越頻繁，效能就會變差，這表示 dk_indices 的空間不夠用了，是時候該擴建啦，我們下個章節就來看看字典的擴建流程，看看應該擴建應該增加多少容積率... 啊，不是，是多少空間才夠用。
本文同步刊載於 「為你自己學 Python - 字典的整理收納課（上）」
iThome鐵人賽
看影片追技術