快捷導(dǎo)航

深入理解Python虛擬機(jī)中字典(dict)的實現(xiàn)原理及源碼剖析

更新時間：2023年03月23日 08:22:37 作者：一無是處的研究僧

這篇文章主要介紹了在?cpython?當(dāng)中字典的實現(xiàn)原理，在本篇文章當(dāng)中主要介紹在早期?python3?當(dāng)中的版本字典的實現(xiàn)，現(xiàn)在的字典做了部分優(yōu)化,希望對大家有所幫助

字典數(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;

上面的各個字段的含義為：

ob_refcnt，對象的引用計數(shù)。
ob_type，對象的數(shù)據(jù)類型。
ma_used，當(dāng)前哈希表當(dāng)中的數(shù)據(jù)個數(shù)。
ma_keys，指向保存鍵值對的數(shù)組。
ma_values，這個指向值的數(shù)組，但是在 cpython 的具體實現(xiàn)當(dāng)中不一定使用這個值，因為 _dictkeysobject 當(dāng)中的 PyDictKeyEntry 數(shù)組當(dāng)中的對象也是可以存儲 value 的，這個值只有在鍵全部是字符串的時候才可能會使用，在本篇文章當(dāng)中主要使用 PyDictKeyEntry 當(dāng)中的 value 來討論字典的實現(xiàn)，因此大家可以忽略這個變量。
dk_refcnt，這個也是用于表示引用計數(shù)，這個跟字典的視圖有關(guān)系，原理和引用計數(shù)類似，這里暫時不管。
dk_size，這個表示哈希表的大小，必須是 2n，這樣的話可以將模運算變成位與運算。
dk_lookup，這個表示哈希表的查找函數(shù)，他是一個函數(shù)指針。
dk_usable，表示當(dāng)前數(shù)組當(dāng)中還有多少個可以使用的鍵值對。
dk_entries，哈希表，真正存儲鍵值對的地方。

整個哈希表的布局大致如下圖所示：

創(chuàng)建新字典對象

這個函數(shù)還是比較簡單，首先申請內(nèi)存空間，然后進(jìn)行一些初始化操作，申請哈希表用于保存鍵值對。

static PyObject *
dict_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
{
    PyObject *self;
    PyDictObject *d;
 
    assert(type != NULL && type->tp_alloc != NULL);
    // 申請內(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);
    // 因為還沒有增加數(shù)據(jù) 因此哈希表當(dāng)中 ma_used = 0
    d->ma_used = 0;
    // 申請保存鍵值對的數(shù)組  PyDict_MINSIZE_COMBINED 是一個宏定義 值為 8 表示哈希表數(shù)組的最小長度
    d->ma_keys = new_keys_object(PyDict_MINSIZE_COMBINED);
    // 如果申請失敗返回 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));
    // 這里是申請內(nèi)存的位置真正申請內(nèi)存空間的大小為 PyDictKeysObject 的大小加上 size-1 個PyDictKeyEntry的大小
    // 這里你可能會有一位為啥不是 size 個 PyDictKeyEntry 的大小 因為在結(jié)構(gòu)體 PyDictKeysObject 當(dāng)中已經(jīng)申請了一個 PyDictKeyEntry 對象了
    dk = PyMem_MALLOC(sizeof(PyDictKeysObject) +
                      sizeof(PyDictKeyEntry) * (size-1));
    if (dk == NULL) {
        PyErr_NoMemory();
        return NULL;
    }
    // 下面主要是一些初始化的操作 dk_refcnt 設(shè)置成 1 因為目前只有一個字典對象使用 這個 PyDictKeysObject 對象
    DK_DEBUG_INCREF dk->dk_refcnt = 1;
    dk->dk_size = size; // 哈希表的大小
    // 下面這行代碼主要是表示哈希表當(dāng)中目前還能存儲多少個鍵值對 在 cpython 的實現(xiàn)當(dāng)中允許有 2/3 的數(shù)組空間去存儲數(shù)據(jù) 超過這個數(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;
    // 將所有的鍵值對初始化成 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ī)制

首先我們先了解一下字典實現(xiàn)當(dāng)中哈希表的擴(kuò)容機(jī)制，當(dāng)我們不斷的往字典當(dāng)中加入新的數(shù)據(jù)的時候，很快字典當(dāng)中的數(shù)據(jù)就會達(dá)到數(shù)組長度的 23 ，這個時候就需要擴(kuò)容，擴(kuò)容之后的數(shù)組大小計算方式如下：

#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))

新的數(shù)組的大小等于原來鍵值對的個數(shù)乘以 2 加上原來數(shù)組長度的一半。

總的來說擴(kuò)容主要有三個步驟：

計算新的數(shù)組的大小。
創(chuàng)建新的數(shù)組。
將原來的哈希表當(dāng)中的數(shù)據(jù)加入到新的數(shù)組當(dāng)中（也就是再哈希的過程）。

具體的實現(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;
    // 下面的代碼的主要作用就是計算得到能夠大于等于 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ù)

我們在不斷的往字典當(dāng)中插入數(shù)據(jù)的時候很可能會遇到哈希沖突，字典處理哈希沖突的方法基本和集合遇到哈希沖突的處理方法是差不多的，都是使用開發(fā)地址法，但是這個開放地址法實現(xiàn)的相對比較復(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) {
        // 下面便是遇到哈希沖突時的處理辦法
        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)部字典的實現(xiàn)機(jī)制，總的來說整個字典的實現(xiàn)機(jī)制還是相當(dāng)復(fù)雜的，本篇文章只是談到了整個字典實現(xiàn)的一小部分，主要設(shè)計字典的內(nèi)存布局以及相關(guān)的數(shù)據(jù)結(jié)構(gòu)，最重要的字典的創(chuàng)建擴(kuò)容和插入，這對我們理解哈希表的結(jié)構(gòu)還是非常有幫助的！??！

以上就是深入理解Python虛擬機(jī)中字典(dict)的實現(xiàn)原理及源碼剖析的詳細(xì)內(nèi)容，更多關(guān)于Python虛擬機(jī)字典的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: