Python的Dict對(duì)象源碼分析

PyDictObject即字典對(duì)象，類似于C++ STL中的map，但STL中以紅黑樹實(shí)現(xiàn)，Python中dict以hash表（散列表）實(shí)現(xiàn)。

散列表，通過Hash函數(shù)將特定對(duì)象映射為特定數(shù)字；

當(dāng)裝載率大于2/3時(shí)，散列沖突概率增加，解決散列沖突，STL采用開鏈法，而Python采用開放定址法。

開放定址法法，在探測(cè)沖突鏈上依次跳轉(zhuǎn)，如果刪除探測(cè)沖突鏈上某個(gè)元素，會(huì)使探測(cè)沖突鏈斷裂。

故而，刪除某元素時(shí)，不可在物理上真正刪除。

1、entry與dict對(duì)象

typedef struct {
    Py_ssize_t me_hash;	     // key的hash值
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;        /* # Active + # Dummy */
    Py_ssize_t ma_used;        /* # Active */
    Py_ssize_t ma_mask;        // dict對(duì)象所擁有的entry數(shù)量
    PyDictEntry *ma_table;     // 指向存放元素的內(nèi)存區(qū)域
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);    // 搜索函數(shù)指針
    PyDictEntry ma_smalltable[PyDict_MINSIZE];      // 自帶少量元素內(nèi)存
};

元素?cái)?shù)量不同時(shí)，可使用不同策略

2、搜索策略

由于采用開放定址法，探測(cè)沖突鏈上元素不可刪除，Python將每個(gè)元素設(shè)為三種狀態(tài)。

1. 從未使用是unused
2. 正在使用是Active
3. 當(dāng)將某個(gè)Active的元素刪除時(shí)將其置為dummy。

通過ma_key與ma_value的值來判定狀態(tài)。

Python每種類型的對(duì)象都實(shí)現(xiàn)了各自的hash函數(shù)，如string對(duì)象函數(shù)函數(shù)如下：

int len = strObject->length;
unsignedchar * p = (unsignedchar *)strObject->value;
long x = *p << 7;
while (--len >= 0)
    x = (1000003*x) ^ *p++;
x ^= strObject->length;
if (x == -1)
    x = -2;
strObject->hashValue = x;

產(chǎn)生散列沖突時(shí)，采用二次探測(cè)函數(shù)，Python中如下：

for (perturb = hash; ; perturb >>= 5) {
	i = (i << 2) + i + perturb + 1;
	ep = &ep0[i & mask];
}

沖突探測(cè)鏈開端為通過hash函數(shù)找到的第一個(gè)entry，結(jié)尾為第一個(gè)unused狀態(tài)entry。

搜索整體思想為，在探測(cè)鏈上依次尋找；

遇到dummy狀態(tài)則記錄為freesplot，并繼續(xù)探測(cè)；

直至探測(cè)到匹配的元素，返回該對(duì)象；

或者直到最后一個(gè)元素即unused狀態(tài)entry，此時(shí)若freesplot為空則返回該unused，若不為空則返回freesplot記錄的dummy。

有圖示幾種情況，1-6依次返回A、C、D、E、X、Y。

3、dict對(duì)象使用

dict對(duì)象的各種應(yīng)用均依賴與搜索策略，而在python中使用PyStringObject*做key的情況特別多，python默認(rèn)使用針對(duì)string優(yōu)化的搜索函數(shù)，如果key不是string對(duì)象，返回通用搜索函數(shù)。

元素的插入，需注意dict對(duì)象會(huì)自動(dòng)調(diào)整內(nèi)存大小，以裝載率大于2/3為基準(zhǔn)。

調(diào)整大小時(shí)會(huì)重新分布元素，故dummy態(tài)不再需要，被銷毀。 元素的刪除，需注意該元素置為dummuy態(tài)。

元素的設(shè)置，若存在該key，直接更改value；

若不存在，添加該entry，即(key,value)。

4、dict對(duì)象緩沖池

和list對(duì)象緩沖池類似，在此就不多贅述。

到此這篇關(guān)于Python的Dict對(duì)象源碼分析的文章就介紹到這了,更多相關(guān)Python的Dict源碼內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論