>>d={'a':1,'b':2}>>>d['c']=3>>>d{'a':1,'b':2,'c':3}在字符串的實現原理文章中,曾經出現過字典對象用于intern操作,那么字典的內部結構是怎樣的呢?PyDictObject對象就是dict的內部實現。哈希表(HASHTABLES)哈希表(也叫散列表),根據關鍵值對(Key-" />

亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python字典對象實現原理詳解

系統 1820 0

字典類型是Python中最常用的數據類型之一,它是一個鍵值對的集合,字典通過鍵來索引,關聯到相對的值,理論上它的查詢復雜度是 O(1) :

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

在字符串的實現原理文章中,曾經出現過字典對象用于intern操作,那么字典的內部結構是怎樣的呢?PyDictObject對象就是dict的內部實現。

哈希表 (HASH TABLES)

哈希表(也叫散列表),根據關鍵值對(Key-value)而直接進行訪問的數據結構。它通過把key和value映射到表中一個位置來訪問記錄,這種查詢速度非常快,更新也快。而這個映射函數叫做哈希函數,存放值的數組叫做哈希表。 哈希函數的實現方式決定了哈希表的搜索效率。具體操作過程是:

1.數據添加:把key通過哈希函數轉換成一個整型數字,然后就將該數字對數組長度進行取余,取余結果就當作數組的下標,將value存儲在以該數字為下標的數組空間里。

2.數據查詢:再次使用哈希函數將key轉換為對應的數組下標,并定位到數組的位置獲取value。

但是,對key進行hash的時候,不同的key可能hash出來的結果是一樣的,尤其是數據量增多的時候,這個問題叫做哈希沖突。如果解決這種沖突情況呢?通常的做法有兩種,一種是鏈接法,另一種是開放尋址法,Python選擇后者。

開放尋址法(OPEN ADDRESSING)

開放尋址法中,所有的元素都存放在散列表里,當產生哈希沖突時,通過一個探測函數計算出下一個候選位置,如果下一個獲選位置還是有沖突,那么不斷通過探測函數往下找,直到找個一個空槽來存放待插入元素。

PYDICTENTRY

字典中的一個key-value鍵值對元素稱為entry(也叫做slots),對應到Python內部是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的哈希值,防止每次查詢時都要計算哈希值,entry有三種狀態。

1.Unused: me_key == me_value == NULL

Unused是entry的初始狀態,key和value都為NULL。插入元素時,Unused狀態轉換成Active狀態。這是me_key為NULL的唯一情況。

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

插入元素后,entry就成了Active狀態,這是me_value唯一不為NULL的情況,刪除元素時Active狀態刻轉換成Dummy狀態。

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

此處的dummy對象實際上一個PyStringObject對象,僅作為指示標志。Dummy狀態的元素可以在插入元素的時候將它變成Active狀態,但它不可能再變成Unused狀態。

為什么entry有Dummy狀態呢?這是因為采用開放尋址法中,遇到哈希沖突時會找到下一個合適的位置,例如某元素經過哈希計算應該插入到A處,但是此時A處有元素的,通過探測函數計算得到下一個位置B,仍然有元素,直到找到位置C為止,此時ABC構成了探測鏈,查找元素時如果hash值相同,那么也是順著這條探測鏈不斷往后找,當刪除探測鏈中的某個元素時,比如B,如果直接把B從哈希表中移除,即變成Unused狀態,那么C就不可能再找到了,因為AC之間出現了斷裂的現象,正是如此才出現了第三種狀態---Dummy,Dummy是一種類似的偽刪除方式,保證探測鏈的連續性。

Python字典對象實現原理詳解_第1張圖片

PYDICTOBJECT

PyDictObject就是PyDictEntry對象的集合,PyDictObject的結構是:

            
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的元素個數
  • ma_used :所有處于Active狀態的元素個數
  • ma_mask :所有entry的元素個數(Active+Dummy+Unused)
  • ma_smalltable:創建字典對象時,一定會創建一個大小為PyDict_MINSIZE==8的PyDictEntry數組。
  • ma_table:當entry數量小于PyDict_MINSIZE,ma_table指向ma_smalltable的首地址,當entry數量大于8時,Python把它當做一個大字典來處理,此刻會申請額外的內存空間,同時將ma_table指向這塊空間。
  • ma_lookup:字典元素的搜索策略

PyDictObject使用PyObject_HEAD而不是PyObject_Var_HEAD,雖然字典也是變長對象,但此處并不是通過ob_size來存儲字典中元素的長度,而是通過ma_used字段。

PYDICTOBJECT的創建過程

            
PyObject *
PyDict_New(void)
{
register PyDictObject *mp;
if (dummy == NULL) { /* Auto-initialize dummy */
dummy = PyString_FromString("
            
              ");
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對象
  • 如果緩沖池還有可用的對象,則從緩沖池中讀取,否則,執行步驟3
  • 分配內存空間,創建PyDictObject對象,初始化對象
  • 指定添加字典元素時的探測函數,元素的搜索策略

字典搜索策略

            
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;
}
          

字典在添加元素和查詢元素時,都需要用到字典的搜索策略,搜索時,如果不存在該key,那么返回Unused狀態的entry,如果存在該key,但是key是一個Dummy對象,那么返回Dummy狀態的entry,其他情況就表示存在Active狀態的entry,那么對于字典的插入操作,針對不同的情況進行操作也不一樣。對于Active的entry,直接替換me_value值即可;對于Unused或Dummy的entry,需要同時設置me_key,me_hash和me_value

PYDICTOBJECT對象緩沖池

PyDictObject對象緩沖池和PyListObject對象緩沖池的原理是類似的,都是在對象被銷毀的時候把該對象添加到緩沖池中去,而且值保留PyDictObject對象本身,如果ma_table維護的時從系統堆中申請的空間,那么Python會釋放這塊內存,如果ma_table維護的是ma_smalltable,那么只需把smalltable中的元素的引用計數減少即可。

            
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)
}
          

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲精品一二三四区 | 一本大道香蕉中文在线高清 | 日本四虎影院 | 久热re这里只有精品视频 | 精品一区二区三区中文字幕 | 精品福利一区 | 亚洲国产精品a一区 | 久久尹人香蕉国产免费天天 | 在线亚洲精品国产波多野结衣 | 优优色综合 | 亚洲欧美精品中字久久99 | 亚洲精品动漫3d一区二区 | 亚洲国产成人精品久久 | 女人18毛片特级一级免费视频 | 亚洲欧美不卡中文字幕 | 欧美精品1区 | 手机在线精品视频每日更新 | 老司机亚洲精品影视www | 中文字幕日韩精品麻豆系列 | 久久久久久久久久爱 | 日日拍夜夜操 | 毛片成人永久免费视频 | 亚洲国产高清美女在线观看 | 美女被cao的视频免费看 | 美女视频黄的免费视频网页 | 99精品小视频 | 国产精品欧美在线 | 一 级 黄 色蝶 片 | 99九九成人免费视频精品 | 日韩午夜在线视频 | 日本吻胸抓胸激烈视频网站 | 男人的天堂在线视频 | 国产精品呦呦 | 99在线播放视频 | 老子影院午夜伦手机不四虎 | 国产一区二区三区日韩 | 亚洲精品国产精品乱码不卞 | 99久久精品视香蕉蕉er热资源 | 久久伊人亚洲 | 91九色视频无限观看免费 | 国产精品青草久久久久婷婷 |