Python字典對(duì)象實(shí)現(xiàn)原理詳解

字典類型是Python中最常用的數(shù)據(jù)類型之一，它是一個(gè)鍵值對(duì)的集合，字典通過鍵來索引，關(guān)聯(lián)到相對(duì)的值，理論上它的查詢復(fù)雜度是 O(1) ：

>>> d = {'a': 1, 'b': 2}
>>> d['c'] = 3
>>> d
{'a': 1, 'b': 2, 'c': 3}

在字符串的實(shí)現(xiàn)原理文章中，曾經(jīng)出現(xiàn)過字典對(duì)象用于intern操作，那么字典的內(nèi)部結(jié)構(gòu)是怎樣的呢？PyDictObject對(duì)象就是dict的內(nèi)部實(shí)現(xiàn)。

哈希表 (HASH TABLES)

哈希表（也叫散列表），根據(jù)關(guān)鍵值對(duì)(Key-value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過把key和value映射到表中一個(gè)位置來訪問記錄，這種查詢速度非?？欤乱部?。而這個(gè)映射函數(shù)叫做哈希函數(shù)，存放值的數(shù)組叫做哈希表。 哈希函數(shù)的實(shí)現(xiàn)方式?jīng)Q定了哈希表的搜索效率。具體操作過程是：

1.數(shù)據(jù)添加：把key通過哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。

2.數(shù)據(jù)查詢：再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到數(shù)組的位置獲取value。

但是，對(duì)key進(jìn)行hash的時(shí)候，不同的key可能hash出來的結(jié)果是一樣的，尤其是數(shù)據(jù)量增多的時(shí)候，這個(gè)問題叫做哈希沖突。如果解決這種沖突情況呢？通常的做法有兩種，一種是鏈接法，另一種是開放尋址法，Python選擇后者。

開放尋址法（OPEN ADDRESSING）

開放尋址法中，所有的元素都存放在散列表里，當(dāng)產(chǎn)生哈希沖突時(shí)，通過一個(gè)探測(cè)函數(shù)計(jì)算出下一個(gè)候選位置，如果下一個(gè)獲選位置還是有沖突，那么不斷通過探測(cè)函數(shù)往下找，直到找個(gè)一個(gè)空槽來存放待插入元素。

PYDICTENTRY

字典中的一個(gè)key-value鍵值對(duì)元素稱為entry（也叫做slots），對(duì)應(yīng)到Python內(nèi)部是PyDictEntry，PyDictObject就是PyDictEntry的集合。PyDictEntry的定義是：

typedef struct {
/* Cached hash code of me_key. Note that hash codes are C longs.
* We have to use Py_ssize_t instead because dict_popitem() abuses
* me_hash to hold a search finger.
*/
Py_ssize_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;

me_hash用于緩存me_key的哈希值，防止每次查詢時(shí)都要計(jì)算哈希值，entry有三種狀態(tài)。

1.Unused： me_key == me_value == NULL

Unused是entry的初始狀態(tài)，key和value都為NULL。插入元素時(shí)，Unused狀態(tài)轉(zhuǎn)換成Active狀態(tài)。這是me_key為NULL的唯一情況。

2. Active： me_key != NULL and me_key != dummy 且 me_value != NULL

插入元素后，entry就成了Active狀態(tài)，這是me_value唯一不為NULL的情況，刪除元素時(shí)Active狀態(tài)刻轉(zhuǎn)換成Dummy狀態(tài)。

3. Dummy： me_key == dummy 且 me_value == NULL

此處的dummy對(duì)象實(shí)際上一個(gè)PyStringObject對(duì)象，僅作為指示標(biāo)志。Dummy狀態(tài)的元素可以在插入元素的時(shí)候?qū)⑺兂葾ctive狀態(tài)，但它不可能再變成Unused狀態(tài)。

為什么entry有Dummy狀態(tài)呢？這是因?yàn)椴捎瞄_放尋址法中，遇到哈希沖突時(shí)會(huì)找到下一個(gè)合適的位置，例如某元素經(jīng)過哈希計(jì)算應(yīng)該插入到A處，但是此時(shí)A處有元素的，通過探測(cè)函數(shù)計(jì)算得到下一個(gè)位置B，仍然有元素，直到找到位置C為止，此時(shí)ABC構(gòu)成了探測(cè)鏈，查找元素時(shí)如果hash值相同，那么也是順著這條探測(cè)鏈不斷往后找，當(dāng)刪除探測(cè)鏈中的某個(gè)元素時(shí)，比如B，如果直接把B從哈希表中移除，即變成Unused狀態(tài)，那么C就不可能再找到了，因?yàn)锳C之間出現(xiàn)了斷裂的現(xiàn)象，正是如此才出現(xiàn)了第三種狀態(tài)---Dummy，Dummy是一種類似的偽刪除方式，保證探測(cè)鏈的連續(xù)性。

PYDICTOBJECT

PyDictObject就是PyDictEntry對(duì)象的集合，PyDictObject的結(jié)構(gòu)是：

typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; /* # Active + # Dummy */
Py_ssize_t ma_used; /* # Active */
/* The table contains ma_mask + 1 slots, and that's a power of 2.
* We store the mask instead of the size because the mask is more
* frequently needed.
*/
Py_ssize_t ma_mask;
/* ma_table points to ma_smalltable for small tables, else to
* additional malloc'ed memory. ma_table is never NULL! This rule
* saves repeated runtime null-tests in the workhorse getitem and
* setitem calls.
*/
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

• ma_fill ：所有處于Active以及Dummy的元素個(gè)數(shù)
• ma_used ：所有處于Active狀態(tài)的元素個(gè)數(shù)
• ma_mask ：所有entry的元素個(gè)數(shù)（Active+Dummy+Unused）
• ma_smalltable：創(chuàng)建字典對(duì)象時(shí)，一定會(huì)創(chuàng)建一個(gè)大小為PyDict_MINSIZE==8的PyDictEntry數(shù)組。
• ma_table：當(dāng)entry數(shù)量小于PyDict_MINSIZE，ma_table指向ma_smalltable的首地址，當(dāng)entry數(shù)量大于8時(shí)，Python把它當(dāng)做一個(gè)大字典來處理，此刻會(huì)申請(qǐng)額外的內(nèi)存空間，同時(shí)將ma_table指向這塊空間。
• ma_lookup：字典元素的搜索策略

PyDictObject使用PyObject_HEAD而不是PyObject_Var_HEAD，雖然字典也是變長(zhǎng)對(duì)象，但此處并不是通過ob_size來存儲(chǔ)字典中元素的長(zhǎng)度，而是通過ma_used字段。

PYDICTOBJECT的創(chuàng)建過程

PyObject *
PyDict_New(void)
{
register PyDictObject *mp;
if (dummy == NULL) { /* Auto-initialize dummy */
dummy = PyString_FromString("<dummy key>");
if (dummy == NULL)
return NULL;
}
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
if (mp->ma_fill) {
EMPTY_TO_MINSIZE(mp);
} else {
/* At least set ma_table and ma_mask; these are wrong
if an empty but presized dict is added to freelist */
INIT_NONZERO_DICT_SLOTS(mp);
}
assert (mp->ma_used == 0);
assert (mp->ma_table == mp->ma_smalltable);
assert (mp->ma_mask == PyDict_MINSIZE - 1);
} else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL)
return NULL;
EMPTY_TO_MINSIZE(mp);
}
mp->ma_lookup = lookdict_string;
return (PyObject *)mp;
}

• 初始化dummy對(duì)象
• 如果緩沖池還有可用的對(duì)象，則從緩沖池中讀取，否則，執(zhí)行步驟3
• 分配內(nèi)存空間，創(chuàng)建PyDictObject對(duì)象，初始化對(duì)象
• 指定添加字典元素時(shí)的探測(cè)函數(shù)，元素的搜索策略

字典搜索策略

static PyDictEntry *
lookdict(PyDictObject *mp, PyObject *key, register long hash)
{
register size_t i;
register size_t perturb;
register PyDictEntry *freeslot;
register size_t mask = (size_t)mp->ma_mask;
PyDictEntry *ep0 = mp->ma_table;
register PyDictEntry *ep;
register int cmp;
PyObject *startkey;

i = (size_t)hash & mask;
ep = &ep0[i];
if (ep->me_key == NULL || ep->me_key == key)
return ep;

if (ep->me_key == dummy)
freeslot = ep;
else {
if (ep->me_hash == hash) {
startkey = ep->me_key;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0)
return NULL;
if (ep0 == mp->ma_table && ep->me_key == startkey) {
if (cmp > 0)
return ep;
}
else {
/* The compare did major nasty stuff to the
* dict: start over.
* XXX A clever adversary could prevent this
* XXX from terminating.
*/
return lookdict(mp, key, hash);
}
}
freeslot = NULL;
}

/* In the loop, me_key == dummy is by far (factor of 100s) the
least likely outcome, so test for that last. */
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
i = (i << 2) + i + perturb + 1;
ep = &ep0[i & mask];
if (ep->me_key == NULL)
return freeslot == NULL ? ep : freeslot;
if (ep->me_key == key)
return ep;
if (ep->me_hash == hash && ep->me_key != dummy) {
startkey = ep->me_key;
Py_INCREF(startkey);
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0)
return NULL;
if (ep0 == mp->ma_table && ep->me_key == startkey) {
if (cmp > 0)
return ep;
}
else {
/* The compare did major nasty stuff to the
* dict: start over.
* XXX A clever adversary could prevent this
* XXX from terminating.
*/
return lookdict(mp, key, hash);
}
}
else if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
}
assert(0); /* NOT REACHED */
return 0;
}

字典在添加元素和查詢?cè)貢r(shí)，都需要用到字典的搜索策略，搜索時(shí)，如果不存在該key，那么返回Unused狀態(tài)的entry，如果存在該key，但是key是一個(gè)Dummy對(duì)象，那么返回Dummy狀態(tài)的entry，其他情況就表示存在Active狀態(tài)的entry，那么對(duì)于字典的插入操作，針對(duì)不同的情況進(jìn)行操作也不一樣。對(duì)于Active的entry，直接替換me_value值即可；對(duì)于Unused或Dummy的entry，需要同時(shí)設(shè)置me_key，me_hash和me_value

PYDICTOBJECT對(duì)象緩沖池

PyDictObject對(duì)象緩沖池和PyListObject對(duì)象緩沖池的原理是類似的，都是在對(duì)象被銷毀的時(shí)候把該對(duì)象添加到緩沖池中去，而且值保留PyDictObject對(duì)象本身，如果ma_table維護(hù)的時(shí)從系統(tǒng)堆中申請(qǐng)的空間，那么Python會(huì)釋放這塊內(nèi)存，如果ma_table維護(hù)的是ma_smalltable，那么只需把smalltable中的元素的引用計(jì)數(shù)減少即可。

static void
dict_dealloc(register PyDictObject *mp)
{
register PyDictEntry *ep;
Py_ssize_t fill = mp->ma_fill;
PyObject_GC_UnTrack(mp);
Py_TRASHCAN_SAFE_BEGIN(mp)
for (ep = mp->ma_table; fill > 0; ep++) {
if (ep->me_key) {
--fill;
Py_DECREF(ep->me_key);
Py_XDECREF(ep->me_value);
}
}
if (mp->ma_table != mp->ma_smalltable)
PyMem_DEL(mp->ma_table);
if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
free_list[numfree++] = mp;
else
Py_TYPE(mp)->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。