Python的Dict對象源碼分析

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

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

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

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

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

1、entry與dict對象

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對象所擁有的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)存
};

元素數(shù)量不同時，可使用不同策略

2、搜索策略

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

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

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

Python每種類型的對象都實現(xiàn)了各自的hash函數(shù)，如string對象函數(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ù)，Python中如下：

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

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

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

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

直至探測到匹配的元素，返回該對象；

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

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

3、dict對象使用

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

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

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

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

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

4、dict對象緩沖池

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

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

最新評論