快捷導(dǎo)航

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

更新時(shí)間：2023年08月16日 10:19:46 作者：efeics

這篇文章主要介紹了Python的Dict對(duì)象源碼分析,PyDictObject即字典對(duì)象，類(lèi)似于C++ STL中的map，但STL中以紅黑樹(shù)實(shí)現(xiàn)，Python中dict以hash表(散列表)實(shí)現(xiàn),需要的朋友可以參考下

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

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

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

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

開(kāi)放定址法法，在探測(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、搜索策略

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

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

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

Python每種類(lèi)型的對(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è)鏈開(kāi)端為通過(guò)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)用均依賴(lài)與搜索策略，而在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)不再需要，被銷(xiāo)毀。元素的刪除，需注意該元素置為dummuy態(tài)。

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

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