深入理解Python虛擬機(jī)中字典(dict)的實(shí)現(xiàn)原理及源碼剖析
字典數(shù)據(jù)結(jié)構(gòu)分析
/* The ma_values pointer is NULL for a combined table * or points to an array of PyObject* for a split table */ typedef struct { PyObject_HEAD Py_ssize_t ma_used; PyDictKeysObject *ma_keys; PyObject **ma_values; } PyDictObject; struct _dictkeysobject { Py_ssize_t dk_refcnt; Py_ssize_t dk_size; dict_lookup_func dk_lookup; Py_ssize_t dk_usable; PyDictKeyEntry dk_entries[1]; }; typedef struct { /* Cached hash code of me_key. */ Py_hash_t me_hash; PyObject *me_key; PyObject *me_value; /* This field is only meaningful for combined tables */ } PyDictKeyEntry;
上面的各個(gè)字段的含義為:
- ob_refcnt,對(duì)象的引用計(jì)數(shù)。
- ob_type,對(duì)象的數(shù)據(jù)類型。
- ma_used,當(dāng)前哈希表當(dāng)中的數(shù)據(jù)個(gè)數(shù)。
- ma_keys,指向保存鍵值對(duì)的數(shù)組。
- ma_values,這個(gè)指向值的數(shù)組,但是在 cpython 的具體實(shí)現(xiàn)當(dāng)中不一定使用這個(gè)值,因?yàn)?_dictkeysobject 當(dāng)中的 PyDictKeyEntry 數(shù)組當(dāng)中的對(duì)象也是可以存儲(chǔ) value 的,這個(gè)值只有在鍵全部是字符串的時(shí)候才可能會(huì)使用,在本篇文章當(dāng)中主要使用 PyDictKeyEntry 當(dāng)中的 value 來討論字典的實(shí)現(xiàn),因此大家可以忽略這個(gè)變量。
- dk_refcnt,這個(gè)也是用于表示引用計(jì)數(shù),這個(gè)跟字典的視圖有關(guān)系,原理和引用計(jì)數(shù)類似,這里暫時(shí)不管。
- dk_size,這個(gè)表示哈希表的大小,必須是 2n,這樣的話可以將模運(yùn)算變成位與運(yùn)算。
- dk_lookup,這個(gè)表示哈希表的查找函數(shù),他是一個(gè)函數(shù)指針。
- dk_usable,表示當(dāng)前數(shù)組當(dāng)中還有多少個(gè)可以使用的鍵值對(duì)。
- dk_entries,哈希表,真正存儲(chǔ)鍵值對(duì)的地方。
整個(gè)哈希表的布局大致如下圖所示:
創(chuàng)建新字典對(duì)象
這個(gè)函數(shù)還是比較簡單,首先申請(qǐng)內(nèi)存空間,然后進(jìn)行一些初始化操作,申請(qǐng)哈希表用于保存鍵值對(duì)。
static PyObject * dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds) { PyObject *self; PyDictObject *d; assert(type != NULL && type->tp_alloc != NULL); // 申請(qǐng)內(nèi)存空間 self = type->tp_alloc(type, 0); if (self == NULL) return NULL; d = (PyDictObject *)self; /* The object has been implicitly tracked by tp_alloc */ if (type == &PyDict_Type) _PyObject_GC_UNTRACK(d); // 因?yàn)檫€沒有增加數(shù)據(jù) 因此哈希表當(dāng)中 ma_used = 0 d->ma_used = 0; // 申請(qǐng)保存鍵值對(duì)的數(shù)組 PyDict_MINSIZE_COMBINED 是一個(gè)宏定義 值為 8 表示哈希表數(shù)組的最小長度 d->ma_keys = new_keys_object(PyDict_MINSIZE_COMBINED); // 如果申請(qǐng)失敗返回 NULL if (d->ma_keys == NULL) { Py_DECREF(self); return NULL; } return self; } // new_keys_object 函數(shù)如下所示 static PyDictKeysObject *new_keys_object(Py_ssize_t size) { PyDictKeysObject *dk; Py_ssize_t i; PyDictKeyEntry *ep0; assert(size >= PyDict_MINSIZE_SPLIT); assert(IS_POWER_OF_2(size)); // 這里是申請(qǐng)內(nèi)存的位置真正申請(qǐng)內(nèi)存空間的大小為 PyDictKeysObject 的大小加上 size-1 個(gè)PyDictKeyEntry的大小 // 這里你可能會(huì)有一位為啥不是 size 個(gè) PyDictKeyEntry 的大小 因?yàn)樵诮Y(jié)構(gòu)體 PyDictKeysObject 當(dāng)中已經(jīng)申請(qǐng)了一個(gè) PyDictKeyEntry 對(duì)象了 dk = PyMem_MALLOC(sizeof(PyDictKeysObject) + sizeof(PyDictKeyEntry) * (size-1)); if (dk == NULL) { PyErr_NoMemory(); return NULL; } // 下面主要是一些初始化的操作 dk_refcnt 設(shè)置成 1 因?yàn)槟壳爸挥幸粋€(gè)字典對(duì)象使用 這個(gè) PyDictKeysObject 對(duì)象 DK_DEBUG_INCREF dk->dk_refcnt = 1; dk->dk_size = size; // 哈希表的大小 // 下面這行代碼主要是表示哈希表當(dāng)中目前還能存儲(chǔ)多少個(gè)鍵值對(duì) 在 cpython 的實(shí)現(xiàn)當(dāng)中允許有 2/3 的數(shù)組空間去存儲(chǔ)數(shù)據(jù) 超過這個(gè)數(shù)則需要進(jìn)行擴(kuò)容 dk->dk_usable = USABLE_FRACTION(size); // #define USABLE_FRACTION(n) ((((n) << 1)+1)/3) ep0 = &dk->dk_entries[0]; /* Hash value of slot 0 is used by popitem, so it must be initialized */ ep0->me_hash = 0; // 將所有的鍵值對(duì)初始化成 NULL for (i = 0; i < size; i++) { ep0[i].me_key = NULL; ep0[i].me_value = NULL; } dk->dk_lookup = lookdict_unicode_nodummy; return dk; }
哈希表擴(kuò)容機(jī)制
首先我們先了解一下字典實(shí)現(xiàn)當(dāng)中哈希表的擴(kuò)容機(jī)制,當(dāng)我們不斷的往字典當(dāng)中加入新的數(shù)據(jù)的時(shí)候,很快字典當(dāng)中的數(shù)據(jù)就會(huì)達(dá)到數(shù)組長度的 23 ,這個(gè)時(shí)候就需要擴(kuò)容,擴(kuò)容之后的數(shù)組大小計(jì)算方式如下:
#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))
新的數(shù)組的大小等于原來鍵值對(duì)的個(gè)數(shù)乘以 2 加上原來數(shù)組長度的一半。
總的來說擴(kuò)容主要有三個(gè)步驟:
- 計(jì)算新的數(shù)組的大小。
- 創(chuàng)建新的數(shù)組。
- 將原來的哈希表當(dāng)中的數(shù)據(jù)加入到新的數(shù)組當(dāng)中(也就是再哈希的過程)。
具體的實(shí)現(xiàn)代碼如下所示:
static int insertion_resize(PyDictObject *mp) { return dictresize(mp, GROWTH_RATE(mp)); } static int dictresize(PyDictObject *mp, Py_ssize_t minused) { Py_ssize_t newsize; PyDictKeysObject *oldkeys; PyObject **oldvalues; Py_ssize_t i, oldsize; // 下面的代碼的主要作用就是計(jì)算得到能夠大于等于 minused 最小的 2 的整數(shù)次冪 /* Find the smallest table size > minused. */ for (newsize = PyDict_MINSIZE_COMBINED; newsize <= minused && newsize > 0; newsize <<= 1) ; if (newsize <= 0) { PyErr_NoMemory(); return -1; } oldkeys = mp->ma_keys; oldvalues = mp->ma_values; /* Allocate a new table. */ // 創(chuàng)建新的數(shù)組 mp->ma_keys = new_keys_object(newsize); if (mp->ma_keys == NULL) { mp->ma_keys = oldkeys; return -1; } if (oldkeys->dk_lookup == lookdict) mp->ma_keys->dk_lookup = lookdict; oldsize = DK_SIZE(oldkeys); mp->ma_values = NULL; /* If empty then nothing to copy so just return */ if (oldsize == 1) { assert(oldkeys == Py_EMPTY_KEYS); DK_DECREF(oldkeys); return 0; } /* Main loop below assumes we can transfer refcount to new keys * and that value is stored in me_value. * Increment ref-counts and copy values here to compensate * This (resizing a split table) should be relatively rare */ if (oldvalues != NULL) { for (i = 0; i < oldsize; i++) { if (oldvalues[i] != NULL) { Py_INCREF(oldkeys->dk_entries[i].me_key); oldkeys->dk_entries[i].me_value = oldvalues[i]; } } } /* Main loop */ // 將原來數(shù)組當(dāng)中的元素加入到新的數(shù)組當(dāng)中 for (i = 0; i < oldsize; i++) { PyDictKeyEntry *ep = &oldkeys->dk_entries[i]; if (ep->me_value != NULL) { assert(ep->me_key != dummy); insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value); } } // 更新一下當(dāng)前哈希表當(dāng)中能夠插入多少數(shù)據(jù) mp->ma_keys->dk_usable -= mp->ma_used; if (oldvalues != NULL) { /* NULL out me_value slot in oldkeys, in case it was shared */ for (i = 0; i < oldsize; i++) oldkeys->dk_entries[i].me_value = NULL; assert(oldvalues != empty_values); free_values(oldvalues); DK_DECREF(oldkeys); } else { assert(oldkeys->dk_lookup != lookdict_split); if (oldkeys->dk_lookup != lookdict_unicode_nodummy) { PyDictKeyEntry *ep0 = &oldkeys->dk_entries[0]; for (i = 0; i < oldsize; i++) { if (ep0[i].me_key == dummy) Py_DECREF(dummy); } } assert(oldkeys->dk_refcnt == 1); DK_DEBUG_DECREF PyMem_FREE(oldkeys); } return 0; }
字典插入數(shù)據(jù)
我們?cè)诓粩嗟耐值洚?dāng)中插入數(shù)據(jù)的時(shí)候很可能會(huì)遇到哈希沖突,字典處理哈希沖突的方法基本和集合遇到哈希沖突的處理方法是差不多的,都是使用開發(fā)地址法,但是這個(gè)開放地址法實(shí)現(xiàn)的相對(duì)比較復(fù)雜,具體程序如下所示:
static void insertdict_clean(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) { size_t i; size_t perturb; PyDictKeysObject *k = mp->ma_keys; // 首先得到 mask 的值 size_t mask = (size_t)DK_SIZE(k)-1; PyDictKeyEntry *ep0 = &k->dk_entries[0]; PyDictKeyEntry *ep; i = hash & mask; ep = &ep0[i]; for (perturb = hash; ep->me_key != NULL; perturb >>= PERTURB_SHIFT) { // 下面便是遇到哈希沖突時(shí)的處理辦法 i = (i << 2) + i + perturb + 1; ep = &ep0[i & mask]; } assert(ep->me_value == NULL); ep->me_key = key; ep->me_hash = hash; ep->me_value = value; }
總結(jié)
在本篇文章當(dāng)中主要給大家簡單介紹了一下在 cpython 內(nèi)部字典的實(shí)現(xiàn)機(jī)制,總的來說整個(gè)字典的實(shí)現(xiàn)機(jī)制還是相當(dāng)復(fù)雜的,本篇文章只是談到了整個(gè)字典實(shí)現(xiàn)的一小部分,主要設(shè)計(jì)字典的內(nèi)存布局以及相關(guān)的數(shù)據(jù)結(jié)構(gòu),最重要的字典的創(chuàng)建擴(kuò)容和插入,這對(duì)我們理解哈希表的結(jié)構(gòu)還是非常有幫助的?。?!
以上就是深入理解Python虛擬機(jī)中字典(dict)的實(shí)現(xiàn)原理及源碼剖析的詳細(xì)內(nèi)容,更多關(guān)于Python虛擬機(jī)字典的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Python實(shí)現(xiàn)自定義包的實(shí)例詳解
這篇文章主要介紹了實(shí)現(xiàn)自定義包的方法,本文通過示例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-12-12Python使用arrow庫優(yōu)雅地處理時(shí)間數(shù)據(jù)詳解
雖然Python提供了多個(gè)內(nèi)置模塊用于操作日期時(shí)間,但有的時(shí)候并不能滿足我們的需求,所以下面這篇文章主要給大家介紹了關(guān)于Python使用arrow庫如何優(yōu)雅地處理時(shí)間數(shù)據(jù)的相關(guān)資料,需要的朋友可以參考借鑒,下面來一起看看吧。2017-10-10Pandas自定義shift與DataFrame求差集的小技巧
Python是進(jìn)行數(shù)據(jù)分析的一種出色語言,主要是因?yàn)橐詳?shù)據(jù)為中心的python軟件包具有奇妙的生態(tài)系統(tǒng),下面這篇文章主要給大家介紹了關(guān)于Pandas自定義shift與DataFrame求差集的相關(guān)資料,需要的朋友可以參考下2022-02-02Python使用import導(dǎo)入本地腳本及導(dǎo)入模塊的技巧總結(jié)
這篇文章主要介紹了Python使用import導(dǎo)入本地腳本及導(dǎo)入模塊的技巧,結(jié)合實(shí)例形式總結(jié)分析了Python使用import導(dǎo)入本地腳本及導(dǎo)入模塊的使用方法及相關(guān)操作注意事項(xiàng),需要的朋友可以參考下2019-08-08Python訪問MongoDB,并且轉(zhuǎn)換成Dataframe的方法
今天小編就為大家分享一篇Python訪問MongoDB,并且轉(zhuǎn)換成Dataframe的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-10-10