字典的整理收納課(上)
跟串列一樣,Python 的字典(dict)是很常使用的資料型態,字典透過 Key & Value 的方式存取,效能相當好,這個章節我們就來看看 Python 裡的字典是怎麼實作的。
字典的內部結構
大家從前面看到現在這個章節,大概可以不用看原始碼就能猜到在 CPython 裡字典的物件叫什麼名字,是的,就是 PyDictObject
。來看看這傢伙的結構長什麼樣子:
在 CPython 裡,字典的內部結構定義在 Include/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
:
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
結構:
struct _dictvalues {
PyObject *values[1];
};
裡面只有個簡單的 values
成員,相當簡單,但看到這裡,我的問題就是如果這麼簡單的結構,為什麼不直接擺在 PyDictKeysObject
裡就好?我們先看看 Python 是怎麼建立一個新的字典物件。
建立字典
照著我們之前學過的流程,這應該會去找 PyDict_Type
型別的 tp_new
成員:
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
往下看:
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
是什麼:
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
成員裡:
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
方法:
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
這名字大概是想不到好名字所以就先這樣命名的吧。
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()
怎麼計算:
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()
函數又是怎麼計算的呢?
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
成員而已。知道雜湊值怎麼算之後,再回來往下看:
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()
函數,不過這個函數做的事比較多,我們先看第一部份:
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 | | | | |
+----+----+----+----+----+----+----+----+