字典類型是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是一種類似的偽刪除方式,保證探測鏈的連續性。
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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
