dictobject

dict底层结构

PyDictKeyEntry

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;

me_hash是用来缓存键的哈希值，这样可以避免每次查询的时候重复计算。
me_key：用于存储键，PyObject *类型，以存储各种可散列对象。
me_value：用于存储值，PyObject *类型，以存储各种类型对象。

_dictkeysobject

即PyDictKeysObject，通过宏定义typedef struct _dictkeysobject PyDictKeysObject;

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    Py_ssize_t dk_nentries;
    char dk_indices[];  
};

dk_refcnt：引用计数。
dk_size：指hash表的大小，即dk_indices的大小，它的值必须为2的幂。
dk_lookup：字典的查找函数。
dk_usable：dk_entries中的可用的键值对数量。
dk_nentries：dk_entries中已经使用的键值对数量。
dk_indices：存储dk_entries的哈希索引，真正的哈希表。在python3.6版本之前，只有一个指向python内部字典对象的入口指针，没有dk_indices这个字段，当有比较多的字典对象, 且当它们以稀疏的哈希表存储时，会浪费较多的内存空间，为了用更紧凑的方式来实现哈希表，Python3.6之后把哈希索引和真正的键值对分开存放，节省内存空间。
- 3.6前：entries表中会有空闲，元素按照散列函数插入不同的位置。
  - entries
    hash key value
    hash0 key0 value0
    None None None
    hash1 key1 value1
    hash2 key2 value2
    None None None
- 3.6后：indices表中会有空闲，但entries表中按元素插入顺序排列，无空闲。元素顺序插入entries表中，并在indices表中记录插入entries表的索引，查找时，通过hash值找到indices里的元素，再拿拿到的元素作为entries的索引找元素。由于entries是按照插入顺序进行插入的数组, 对字典进行遍历时能按照插入顺序进行遍历, 而在旧的哈希表方案中, 由于不同键的哈希值不一样, 哈希表中的顺序是按照哈希值大小排序的, 遍历时从前往后遍历表现起来就是无序的, 这也是为什么python3.6以前的版本字典对象是无序的但是python3.6以后的版本字典对象是有序的原因。
  - indices
    -1 0 -1 2 -1 -1 1
  - entries
    hash key value
    hash0 key0 value0
    hash1 key1 value1
    hash2 key2 value2

hash	key	value
hash0	key0	value0
None	None	None
hash1	key1	value1
hash2	key2	value2
None	None	None

hash	key	value
hash0	key0	value0
hash1	key1	value1
hash2	key2	value2

PyDictObject

typedef struct _dictkeysobject PyDictKeysObject;

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;

ma_used：字典中条目个数，当我们使用内置函数len()去获取字典的长度时，底层返回这个成员的值。
ma_version_tag：字典的唯一标识，字典每次改，这个值也要改。
ma_keys：指向另一个核心结构体PyDictKeysObject。
ma_values：指向指针的指针，当它为NULL时，散列表是组合的(combined)，即key和value存储在ma_keys里；当它不为NULL时，散列表是分离的(splited)，key存储在ma_keys里，而value存储在ma_values里。

DK_ENTRIES

#define DK_ENTRIES(dk) \
    ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))

重写为

size_t indices_offset = DK_SIZE(dk) * DK_IXSIZE(dk);
int8_t *pointer_to_indices = (int8_t *)(dk->dk_indices);
int8_t *pointer_to_entries = pointer_to_indices + indices_offset;
PyDictKeyEntry *entries = (PyDictKeyEntry *) pointer_to_entries;

可以发现indices和entries是一段连续的连起来的空间, indices指向哈希索引, entries指向真正存储数据的数组头部。

dict方法

PyDict_New

PyObject *
PyDict_New(void)
{
    dictkeys_incref(Py_EMPTY_KEYS);
    return new_dict(Py_EMPTY_KEYS, empty_values);
}

dictkeys_incref(Py_EMPTY_KEYS)：增加Py_EMPTY_KEYS的引用计数。

dictkeys_incref：

static inline void
dictkeys_incref(PyDictKeysObject *dk)
{
#ifdef Py_REF_DEBUG
    _Py_RefTotal++;
#endif
    dk->dk_refcnt++;
}

Py_EMPTY_KEYS：初始化了一个PyDictKeysObject对象。

static PyDictKeysObject empty_keys_struct = {
        1, /* dk_refcnt */
        1, /* dk_size */
        lookdict_split, /* dk_lookup */
        0, /* dk_usable (immutable) */
        0, /* dk_nentries */
        {DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY,
        DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY, DKIX_EMPTY}, /* dk_indices */
};

new_dict：开始创建字典对象。

/* Consumes a reference to the keys object */
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
    PyDictObject *mp;
    assert(keys != NULL);
    struct _Py_dict_state *state = get_dict_state();
#ifdef Py_DEBUG
    // new_dict() must not be called after _PyDict_Fini()
    assert(state->numfree != -1);
#endif
    if (state->numfree) {
        mp = state->free_list[--state->numfree];
        assert (mp != NULL);
        assert (Py_IS_TYPE(mp, &PyDict_Type));
        _Py_NewReference((PyObject *)mp);
    }
    else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL) {
            dictkeys_decref(keys);
            if (values != empty_values) {
                free_values(values);
            }
            return NULL;
        }
    }
    mp->ma_keys = keys;
    mp->ma_values = values;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    ASSERT_CONSISTENT(mp);
    return (PyObject *)mp;
}

Python dict创建与Python list类似，都使用了缓冲池，首先先判断缓冲池中是否有dict对象，有则赋初值后返回，没有则使用PyObject_GC_New返回一个新的dict对象，赋初值，返回。

find_empty_slot

static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
    assert(keys != NULL);

    const size_t mask = DK_MASK(keys);
    size_t i = hash & mask;
    Py_ssize_t ix = dictkeys_get_index(keys, i);
    for (size_t perturb = hash; ix >= 0;) {
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
        ix = dictkeys_get_index(keys, i);
    }
    return i;
}

注意到Python使用开放定址法来解决哈希冲突。
其原理是产生哈希冲突时, python通过一个二次探测函数f，计算下一个候选位置，当下一个位置可用，则将数据插入该位置，如果不可用则再次调用探测函数f，获得下一个候选位置，因此经过不断探测，总会找到一个可用的位置。多次使用二次探测函数f，从一个位置出发就可以依次到达多个位置，这些位置形成了一个冲突探测链，代码中的for循环就在进行这个过程。
当需要删除探测链上的某个数据时，问题就产生了, 假如这条链路上的首个元素是a最后的元素是c现在需要删除处于中间位置的b，这样就会导致探测链断裂, 当下一次搜索c时会从a出发，沿着链路一步步出发，但是中途的链路断了导致无法到达c的位置, 因此无法搜索到c。所以在采用开放定地法解决哈希冲突的问题时，删除链路上的某个元素时，不能真正的删除元素，只能进行伪删除。
Python为每个key准备了三种状态。
```
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)  /* Used internally */
#define DKIX_ERROR (-3)
```
- Unused，DKIX_EMPTY，该状态下也就是当该字典中还没有存储key和value每个字典初始化时都是该状态，indices里的值为-1。
- Active，当字典中存储了key和value时状态就进入到了Active，此时indices数组里的值一定是大于等于0的。
- Dummy，DKIX_DUMMY当字典中的key和value被删除后字典不能从Active直接进入Unused状态，否则就会出现冲突链路中断，实际上python进行删除字典元素时，会将indices数组里的值改为Dummy

dict_dealloc

static void
dict_dealloc(PyDictObject *mp)
{
    PyObject **values = mp->ma_values;
    PyDictKeysObject *keys = mp->ma_keys;
    Py_ssize_t i, n;

    /* bpo-31095: UnTrack is needed before calling any callbacks */
    PyObject_GC_UnTrack(mp);
    Py_TRASHCAN_BEGIN(mp, dict_dealloc)
    if (values != NULL) {
        if (values != empty_values) {
            for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
                Py_XDECREF(values[i]);
            }
            free_values(values);
        }
        dictkeys_decref(keys);
    }
    else if (keys != NULL) {
        assert(keys->dk_refcnt == 1);
        dictkeys_decref(keys);
    }
    struct _Py_dict_state *state = get_dict_state();
#ifdef Py_DEBUG
    // new_dict() must not be called after _PyDict_Fini()
    assert(state->numfree != -1);
#endif
    if (state->numfree < PyDict_MAXFREELIST && Py_IS_TYPE(mp, &PyDict_Type)) {
        state->free_list[state->numfree++] = mp;
    }
    else {
        Py_TYPE(mp)->tp_free((PyObject *)mp);
    }
    Py_TRASHCAN_END
}

与list object类似，先对字典中的元素引用计数减一。
如果缓冲池未满，则将字典放入缓冲池中，若已满，则销毁。

Python dictobject 字典对象

dictobject

dict底层结构

PyDictKeyEntry

_dictkeysobject

PyDictObject

DK_ENTRIES

dict方法

PyDict_New

find_empty_slot

dict_dealloc

Python PyCodeObject 字节码对象

Python listobject 列表对象

Ronie

Comments | NOTHING

dictobject

dict底层结构

PyDictKeyEntry

_dictkeysobject

PyDictObject

DK_ENTRIES

dict方法

PyDict_New

find_empty_slot

dict_dealloc

Python PyCodeObject 字节码对象

Python listobject 列表对象

Ronie

Comments | NOTHING

你想搜索什么...