python dict

发表于 | 分类于
it is pythonic

定义

字典结构体的定义在文件Include/cpython/dictobject.h

具体内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct {
    PyObject_HEAD

    /* Number of items in the dictionary */
    Py_ssize_t ma_used; //字典中的元素个数

    /* Dictionary version: globally unique, value change each time
       the dictionary is modified */
    uint64_t ma_version_tag;//字典版本号，每次字典有变更，这个值也会变更

    PyDictKeysObject *ma_keys; //指针，指向存储的键值对

    /* If ma_values is NULL, the table is "combined": keys and values
       are stored in ma_keys.

       If ma_values is not NULL, the table is splitted:
       keys are stored in ma_keys and values are stored in ma_values */
    PyObject **ma_values; //指向指针的指针，如果为空，则key和value都是存储在ma_keys,否则，key存放在ma_keys,value存放在ma_values，一般创建的字典都是联合表字典combined-table，分离表字典split-table字典用于__dict__属性，它们的键表被缓存在类型属性中，并允许所有该类型的实例共享值。
} PyDictObject;

而存储键值对的结构，PyDictKeysObject，即_dictkeysobject，定义在Objects/dict-common.h中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
struct _dictkeysobject {
    Py_ssize_t dk_refcnt; //引用计数

    /* Size of the hash table (dk_indices). It must be a power of 2. */
    Py_ssize_t dk_size; // 容量，是2的倍数，这样在寻址的时候，可以用异或

    /* Function to lookup in the hash table (dk_indices):

       - lookdict(): general-purpose, and may return DKIX_ERROR if (and
         only if) a comparison raises an exception.

       - lookdict_unicode(): specialized to Unicode string keys, comparison of
         which can never raise an exception; that function can never return
         DKIX_ERROR.

       - lookdict_unicode_nodummy(): similar to lookdict_unicode() but further
         specialized for Unicode string keys that cannot be the <dummy> value.

       - lookdict_split(): Version of lookdict() for split tables. */
    dict_lookup_func dk_lookup; // hash查找函数

    /* Number of usable entries in dk_entries. */
    Py_ssize_t dk_usable; // 可使用的entry

    /* Number of used entries in dk_entries. */
    Py_ssize_t dk_nentries; //已使用的entry

    /* Actual hash table of dk_size entries. It holds indices in dk_entries,
       or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).

       Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).

       The size in bytes of an indice depends on dk_size:

       - 1 byte if dk_size <= 0xff (char*)
       - 2 bytes if dk_size <= 0xffff (int16_t*)
       - 4 bytes if dk_size <= 0xffffffff (int32_t*)
       - 8 bytes otherwise (int64_t*)

       Dynamically sized, SIZEOF_VOID_P is minimum. */
    char dk_indices[];  /* char is required to avoid strict aliasing. */
    //存入的entries，元素类型是PyDictKeyEntry
    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
       see the DK_ENTRIES() macro */
};

1
2
3
4
5
6
7

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash; //存储me_key的hash值
    PyObject *me_key; //键
    PyObject *me_value; /* This field is only meaningful for combined tables */ //值
} PyDictKeyEntry;

内存结构图如下

avatar

hash冲突

当某俩个不同的key，计算的hash一样的时候，就产生了hash冲突。 产生hash冲突的时候，就需要解决冲突，一般有以下的思路

  1. 用某种方法再找个地址，直到没有冲突，这个思路下有以下方法
    • 将key用其他方式再hash
    • 查找这个地址之前/之后的可用地址 以上新增时可能会增加时间，比如出发扩容和多次查找会很耗时，但是访问速度快，可以序列化
  2. 将这些冲突的key，额外存储下
    • 用一个链表/红黑树存储这些key，适合经常插入和删除，访问的时间可能会增加
    • 建立公共益处区，专门存储冲突的key

dict的各个接口函数的实现，都在文件Objects/dictobject.c文件中，

一般都是创建dict和给dict添加元素的时候，就会遇到hash冲突，所以可以直接观察插入元素的实现逻辑，从中看看python如何解决hash冲突的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

static int
insertdict(PyDictObject *mp/*被插入的字典*/, PyObject *key/*需要插入字典的键*/, Py_hash_t hash/*需要插入字典的键的hash*/, PyObject *value/*需要插入字典的值*/)
{
    PyObject *old_value;
    PyDictKeyEntry *ep;

    Py_INCREF(key); //添加引用计数
    Py_INCREF(value); //添加引用计数
    if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
        // ma_values 不为空表示该字典是分离表字典，PyUnicode_CheckExact检查key是否是unicode对象，不能是unicode子类对象
        // 如果mp是分离表字典，且key不是unicode对象
        if (insertion_resize(mp) < 0)
            // 如果无法给mp申请内存，转换成联合表字典，那么直接失败，
            goto Fail;
    }

    Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
    // 调用dk_lookup查找需要插入的键值对所在的位置，理论上，为了保证该位置可以插入，那么这个查找函数就需要返回解决hash冲突后的地址了
    // 所以查看dk_lookup的实现
    if (ix == DKIX_ERROR)
        goto Fail;

    assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
    MAINTAIN_TRACKING(mp, key, value);

    /* When insertion order is different from shared key, we can't share
     * the key anymore.  Convert this instance to combine table.
     */
    if (_PyDict_HasSplitTable(mp) &&
        ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
         (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
        if (insertion_resize(mp) < 0)
            goto Fail;
        ix = DKIX_EMPTY;
    }

    if (ix == DKIX_EMPTY) {
        /* Insert into new slot. */
        assert(old_value == NULL);
        if (mp->ma_keys->dk_usable <= 0) {
            /* Need to resize. */
            if (insertion_resize(mp) < 0)
                goto Fail;
        }
        Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
        ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
        dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
        ep->me_key = key;
        ep->me_hash = hash;
        if (mp->ma_values) {
            assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
            mp->ma_values[mp->ma_keys->dk_nentries] = value;
        }
        else {
            ep->me_value = value;
        }
        mp->ma_used++;
        mp->ma_version_tag = DICT_NEXT_VERSION();
        mp->ma_keys->dk_usable--;
        mp->ma_keys->dk_nentries++;
        assert(mp->ma_keys->dk_usable >= 0);
        ASSERT_CONSISTENT(mp);
        return 0;
    }

    if (old_value != value) {
        if (_PyDict_HasSplitTable(mp)) {
            mp->ma_values[ix] = value;
            if (old_value == NULL) {
                /* pending state */
                assert(ix == mp->ma_used);
                mp->ma_used++;
            }
        }
        else {
            assert(old_value != NULL);
            DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
        }
        mp->ma_version_tag = DICT_NEXT_VERSION();
    }
    Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
    ASSERT_CONSISTENT(mp);
    Py_DECREF(key);
    return 0;

Fail:
    Py_DECREF(value); //异常情况，去除添加的引用计数
    Py_DECREF(key); //异常情况，去除添加的引用计数
    return -1;
}

没有直接查找到dk_lookup的直接实现,是在实际调用中，给dk_lookup赋值为各种lookdict函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
         Py_hash_t hash, PyObject **value_addr)
{
    size_t i, mask, perturb;
    PyDictKeysObject *dk;
    PyDictKeyEntry *ep0;

top:
    dk = mp->ma_keys;
    ep0 = DK_ENTRIES(dk);
    mask = DK_MASK(dk);
    perturb = hash;
    i = (size_t)hash & mask;

    for (;;) {
        Py_ssize_t ix = dictkeys_get_index(dk, i);
        if (ix == DKIX_EMPTY) {//如果查找出的位置是空的，表示，这个位置可以插入新的键值对，那么直接返回这个地址
            *value_addr = NULL;
            return ix;
        }
        if (ix >= 0) {
            PyDictKeyEntry *ep = &ep0[ix];
            assert(ep->me_key != NULL);
            if (ep->me_key == key) {// key一致，表示这个位置就是要找的地方
                *value_addr = ep->me_value;
                return ix;
            }
            if (ep->me_hash == hash) { // key不一致，但是hash一直，表示发生了hash冲突
                PyObject *startkey = ep->me_key;
                Py_INCREF(startkey);
                int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
                Py_DECREF(startkey);
                if (cmp < 0) {
                    *value_addr = NULL;
                    return DKIX_ERROR;
                }
                if (dk == mp->ma_keys && ep->me_key == startkey) {
                    if (cmp > 0) {
                        *value_addr = ep->me_value;
                        return ix;
                    }
                }
                else {
                    /* The dict was mutated, restart */
                    goto top;
                }
            }
        }
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask; // ix <0,否则，将i运算后，进行下一轮计算
    }
    Py_UNREACHABLE();
}

通过上面的源码，看出来，python使用了实现起来最简单的开放地址法解决冲突，果然时刻践行着”怎么简单怎么来”的思想