深入理解 Python 虛擬機器器：字典（dict）的實現原理及原始碼剖析
2023-03-23 06:03:30
深入理解 Python 虛擬機器器：字典（dict）的實現原理及原始碼剖析
在本篇文章當中主要給大家深入介紹一下在 cpython 當中字典的實現原理，在本篇文章當中主要介紹在早期 python3 當中的版本字典的實現，現在的字典做了部分優化，我們在後面的文章當中再介紹。
字典資料結構分析
/* The ma_values pointer is NULL for a combined table
* or points to an array of PyObject* for a split table
*/
typedef struct {
PyObject_HEAD
Py_ssize_t ma_used;
PyDictKeysObject *ma_keys;
PyObject **ma_values;
} PyDictObject;
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
Py_ssize_t dk_size;
dict_lookup_func dk_lookup;
Py_ssize_t dk_usable;
PyDictKeyEntry dk_entries[1];
};
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
上面的各個欄位的含義為：
- ob_refcnt，物件的參照計數。
- ob_type，物件的資料型別。
- ma_used，當前雜湊表當中的資料個數。
- ma_keys，指向儲存鍵值對的陣列。
- ma_values，這個指向值的陣列，但是在 cpython 的具體實現當中不一定使用這個值，因為 _dictkeysobject 當中的 PyDictKeyEntry 陣列當中的物件也是可以儲存 value 的，這個值只有在鍵全部是字串的時候才可能會使用，在本篇文章當中主要使用 PyDictKeyEntry 當中的 value 來討論字典的實現，因此大家可以忽略這個變數。
- dk_refcnt，這個也是用於表示參照計數，這個跟字典的檢視有關係，原理和參照計數類似，這裡暫時不管。
- dk_size，這個表示雜湊表的大小，必須是 \(2^n\)，這樣的話可以將模運算變成位與運算。
- dk_lookup，這個表示雜湊表的查詢函數，他是一個函數指標。
- dk_usable，表示當前陣列當中還有多少個可以使用的鍵值對。
- dk_entries，雜湊表，真正儲存鍵值對的地方。
整個雜湊表的佈局大致如下圖所示：
建立新字典物件
這個函數還是比較簡單，首先申請記憶體空間，然後進行一些初始化操作，申請雜湊表用於儲存鍵值對。
static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
PyObject *self;
PyDictObject *d;
assert(type != NULL && type->tp_alloc != NULL);
// 申請記憶體空間
self = type->tp_alloc(type, 0);
if (self == NULL)
return NULL;
d = (PyDictObject *)self;
/* The object has been implicitly tracked by tp_alloc */
if (type == &PyDict_Type)
_PyObject_GC_UNTRACK(d);
// 因為還沒有增加資料 因此雜湊表當中 ma_used = 0
d->ma_used = 0;
// 申請儲存鍵值對的陣列 PyDict_MINSIZE_COMBINED 是一個宏定義 值為 8 表示雜湊表陣列的最小長度
d->ma_keys = new_keys_object(PyDict_MINSIZE_COMBINED);
// 如果申請失敗返回 NULL
if (d->ma_keys == NULL) {
Py_DECREF(self);
return NULL;
}
return self;
}
// new_keys_object 函數如下所示
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
PyDictKeysObject *dk;
Py_ssize_t i;
PyDictKeyEntry *ep0;
assert(size >= PyDict_MINSIZE_SPLIT);
assert(IS_POWER_OF_2(size));
// 這裡是申請記憶體的位置真正申請記憶體空間的大小為 PyDictKeysObject 的大小加上 size-1 個PyDictKeyEntry的大小
// 這裡你可能會有一位為啥不是 size 個 PyDictKeyEntry 的大小 因為在結構體 PyDictKeysObject 當中已經申請了一個 PyDictKeyEntry 物件了
dk = PyMem_MALLOC(sizeof(PyDictKeysObject) +
sizeof(PyDictKeyEntry) * (size-1));
if (dk == NULL) {
PyErr_NoMemory();
return NULL;
}
// 下面主要是一些初始化的操作 dk_refcnt 設定成 1 因為目前只有一個字典物件使用 這個 PyDictKeysObject 物件
DK_DEBUG_INCREF dk->dk_refcnt = 1;
dk->dk_size = size; // 雜湊表的大小
// 下面這行程式碼主要是表示雜湊表當中目前還能儲存多少個鍵值對 在 cpython 的實現當中允許有 2/3 的陣列空間去儲存資料 超過這個數則需要進行擴容
dk->dk_usable = USABLE_FRACTION(size); // #define USABLE_FRACTION(n) ((((n) << 1)+1)/3)
ep0 = &dk->dk_entries[0];
/* Hash value of slot 0 is used by popitem, so it must be initialized */
ep0->me_hash = 0;
// 將所有的鍵值對初始化成 NULL
for (i = 0; i < size; i++) {
ep0[i].me_key = NULL;
ep0[i].me_value = NULL;
}
dk->dk_lookup = lookdict_unicode_nodummy;
return dk;
}
雜湊表擴容機制
首先我們先了解一下字典實現當中雜湊表的擴容機制，當我們不斷的往字典當中加入新的資料的時候，很快字典當中的資料就會達到陣列長度的 \(\frac{2}{3}\) ，這個時候就需要擴容，擴容之後的陣列大小計算方式如下：
#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))
新的陣列的大小等於原來鍵值對的個數乘以 2 加上原來陣列長度的一半。
總的來說擴容主要有三個步驟：
-
計算新的陣列的大小。
-
建立新的陣列。
-
將原來的雜湊表當中的資料加入到新的陣列當中（也就是再雜湊的過程）。
具體的實現程式碼如下所示：
static int
insertion_resize(PyDictObject *mp)
{
return dictresize(mp, GROWTH_RATE(mp));
}
static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
Py_ssize_t newsize;
PyDictKeysObject *oldkeys;
PyObject **oldvalues;
Py_ssize_t i, oldsize;
// 下面的程式碼的主要作用就是計算得到能夠大於等於 minused 最小的 2 的整數次冪
/* Find the smallest table size > minused. */
for (newsize = PyDict_MINSIZE_COMBINED;
newsize <= minused && newsize > 0;
newsize <<= 1)
;
if (newsize <= 0) {
PyErr_NoMemory();
return -1;
}
oldkeys = mp->ma_keys;
oldvalues = mp->ma_values;
/* Allocate a new table. */
// 建立新的陣列
mp->ma_keys = new_keys_object(newsize);
if (mp->ma_keys == NULL) {
mp->ma_keys = oldkeys;
return -1;
}
if (oldkeys->dk_lookup == lookdict)
mp->ma_keys->dk_lookup = lookdict;
oldsize = DK_SIZE(oldkeys);
mp->ma_values = NULL;
/* If empty then nothing to copy so just return */
if (oldsize == 1) {
assert(oldkeys == Py_EMPTY_KEYS);
DK_DECREF(oldkeys);
return 0;
}
/* Main loop below assumes we can transfer refcount to new keys
* and that value is stored in me_value.
* Increment ref-counts and copy values here to compensate
* This (resizing a split table) should be relatively rare */
if (oldvalues != NULL) {
for (i = 0; i < oldsize; i++) {
if (oldvalues[i] != NULL) {
Py_INCREF(oldkeys->dk_entries[i].me_key);
oldkeys->dk_entries[i].me_value = oldvalues[i];
}
}
}
/* Main loop */
// 將原來陣列當中的元素加入到新的陣列當中
for (i = 0; i < oldsize; i++) {
PyDictKeyEntry *ep = &oldkeys->dk_entries[i];
if (ep->me_value != NULL) {
assert(ep->me_key != dummy);
insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
}
}
// 更新一下當前雜湊表當中能夠插入多少資料
mp->ma_keys->dk_usable -= mp->ma_used;
if (oldvalues != NULL) {
/* NULL out me_value slot in oldkeys, in case it was shared */
for (i = 0; i < oldsize; i++)
oldkeys->dk_entries[i].me_value = NULL;
assert(oldvalues != empty_values);
free_values(oldvalues);
DK_DECREF(oldkeys);
}
else {
assert(oldkeys->dk_lookup != lookdict_split);
if (oldkeys->dk_lookup != lookdict_unicode_nodummy) {
PyDictKeyEntry *ep0 = &oldkeys->dk_entries[0];
for (i = 0; i < oldsize; i++) {
if (ep0[i].me_key == dummy)
Py_DECREF(dummy);
}
}
assert(oldkeys->dk_refcnt == 1);
DK_DEBUG_DECREF PyMem_FREE(oldkeys);
}
return 0;
}
字典插入資料
我們在不斷的往字典當中插入資料的時候很可能會遇到雜湊衝突，字典處理雜湊衝突的方法基本和集合遇到雜湊衝突的處理方法是差不多的，都是使用開發地址法，但是這個開放地址法實現的相對比較複雜，具體程式如下所示：
static void
insertdict_clean(PyDictObject *mp, PyObject *key, Py_hash_t hash,
PyObject *value)
{
size_t i;
size_t perturb;
PyDictKeysObject *k = mp->ma_keys;
// 首先得到 mask 的值
size_t mask = (size_t)DK_SIZE(k)-1;
PyDictKeyEntry *ep0 = &k->dk_entries[0];
PyDictKeyEntry *ep;
i = hash & mask;
ep = &ep0[i];
for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) {
// 下面便是遇到雜湊衝突時的處理辦法
i = (i << 2) + i + perturb + 1;
ep = &ep0[i & mask];
}
assert(ep->me_value == NULL);
ep->me_key = key;
ep->me_hash = hash;
ep->me_value = value;
}
總結
在本篇文章當中主要給大家簡單介紹了一下在 cpython 內部字典的實現機制，總的來說整個字典的實現機制還是相當複雜的，本篇文章只是談到了整個字典實現的一小部分，主要設計字典的記憶體佈局以及相關的資料結構，最重要的字典的建立擴容和插入，這對我們理解雜湊表的結構還是非常有幫助的！！！
本篇文章是深入理解 python 虛擬機器器系列文章之一，文章地址：https://github.com/Chang-LeHung/dive-into-cpython
更多精彩內容合集可存取專案：https://github.com/Chang-LeHung/CSCore
關注公眾號：一無是處的研究僧，瞭解更多計算機（Java、Python、計算機系統基礎、演演算法與資料結構）知識。