源码分析Python的Dict关联式容器

一 、 背景

字典dict是Python开发中常用的数据结构之一，同样，其他语言中也有类似的数据结构，例如C++中的map，Golang中的map, Java中的HashMap等。dict是基于哈希表实现的，但实现的方式在每个语言中都不完全相同。接下来，就来探究下dict底层的数据结构，来学习一下Python的dict相关操作集，动态扩容机制以及如何在内存的使用上进行优化的。本篇文章所使用的的Python版本为3.10。

二 、dict所涉及的数据结构

PyDictKeyEntry键值对结构体，代码位于/Include/internal/pycore_dict.h头文件中

1
2
3
4
5
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key; 
    PyObject *me_value;
} PyDictKeyEntry;

说明：

(1).me_hash：缓存me_key键的hash值

(2).me_key： 键对象

(3).me_value: 值对象， 只在combined tables中有意义, 而在splited tables中无意义，如果是splited tables， 值对象存储在PyDictObject的ma_values中，不存于PyDictKeyEntry结构体中。

PyDictKeysObject结构体，代码位于/Include/internal/pycore_dict.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
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;

    /* Size of the hash table (dk_indices). It must be a power of 2. */
    /* hash表大小，必须是2的次幂方 */
    uint8_t dk_log2_size;

    /* Kind of keys*/
    /* 键的类型*/
    uint8_t dk_kind;

    /* Version number -- Reset to 0 by any modification to keys */
    uint32_t dk_version;

    /* Number of usable entries in dk_entries. */
    /* 键值对可用个数 */
    Py_ssize_t dk_usable;

    /* Number of used entries in dk_entries. */
    /* 键值对已用个数 */
    Py_ssize_t dk_nentries;

    /* 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. */
    /* 索引数组, 存放dk_entries中的索引值 */
    char dk_indices[];  /* char is required to avoid strict aliasing. */

    /* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
       see the DK_ENTRIES() macro */
};

说明：

1. dk_refcnt： 字典对象的引用计数
2. dk_log2_size： 哈希表(dk_indices)的大小所占的位数，为2的次幂方，便于使用位运算。
3. dk_kind： 键的类型
4. dk_version：版本号，任何对键的修改都会重置为0
5. dk_usable: 键值对可用个数，占hash表总容量的2/3, 用于判断是否需要动态扩容
6. dk_nentries: 键值对已用个数
7. dk_indices: 索引数组（真正的hash表)，存放hash值

文件下方同时还分别针对32位和64位的机器上提供了一些宏定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 哈希表的中大小所占的位数
#define DK_LOG_SIZE(dk)  ((dk)->dk_log2_size)
// 如果是64位机器
#if SIZEOF_VOID_P > 4
#define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))
#define DK_IXSIZE(dk)                     \
    (DK_LOG_SIZE(dk) <= 7 ?               \
        1 : DK_LOG_SIZE(dk) <= 15 ?       \
            2 : DK_LOG_SIZE(dk) <= 31 ?   \
                4 : sizeof(int64_t))
#else
// 32位机器
#define DK_SIZE(dk)      (1<<DK_LOG_SIZE(dk))
#define DK_IXSIZE(dk)                     \
    (DK_LOG_SIZE(dk) <= 7 ?               \
        1 : DK_LOG_SIZE(dk) <= 15 ?       \
            2 : sizeof(int32_t))
// 指针，指向哈希表中的键值对实体数组
#define DK_ENTRIES(dk) \
    ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))

说明：

(1).DK_IXSIZE宏定义：dk_log2_size位数不断增大，其值也在不断增大，目的是在hash表扩容时，能够扩容出更大的hash表，减少当hash表小的时候频繁扩容的现象。

(2).DK_ENTRIES宏定义: 指针类型，用于指向哈希表中的键值对数组的首地址。

三 、 阅读源码前的开胃小菜

在了解到了dict的真面目之后，接下来进入到/Objects/dictobject.c文件中，进一步学习下dict的各个操作集以及dict如何实现动态扩容。

在文件的开头有很多的注释，耐心看完会对下面函数源码的阅读有很大的帮助。

由于注释太多，我选取了部分注释说明：

1.PyDictKeysObject结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
+---------------+
| dk_refcnt     |
| dk_log2_size  |
| dk_kind       |
| dk_usable     |
| dk_nentries   |
+---------------+
| dk_indices    |
|               |
+---------------+
| dk_entries    |
|               |
+---------------+

这里比较重要的两个字段分别是dk_indices(哈希索引数组), dk_entries(键值对实体数组)

2. 字典容量的说明

1
2
3
4
5
6
7
8
9
10
* PyDict_MINSIZE is the starting size for any new dict.
* 8 allows dicts with no more than 5 active entries; experiments suggested
* this suffices for the majority of dicts (consisting mostly of usually-small
* dicts created to pass keyword arguments).
* Making this 8, rather than 4 reduces the number of resizes for most
* dictionaries, without any significant extra memory use.
* USABLE_FRACTION should be quick to calculate.
* Fractions around 1/2 to 2/3 seem to work well in practice.
* Increasing this ratio makes dictionaries more dense resulting in more collisions.  Decreasing it improves sparseness at the expense of spreading indices over more cache lines and at the cost of total memory consumed.

稍微解释一下，提取出以下三点：

(1).PyDict_MINSIZE是字典初始化的大小。

(2).根据实验得出，在总容量为8的字典中，键值对实体所占的容量不超过5，意味着键值对实体所占的hash表最大容量的2/3。

(3).将字典初始大小设定为8，而不是4，减少了字典的频繁扩容带来的内存的开销。

(4).#define USABLE_FRACTION(n) (((n) << 1)/3)宏定义规定了负载因子要<=2/3,负载因子过高将导致更多的冲突，过低的话，hash槽位会变得过于分散，带来更多的内存开销。

3.巧妙设定int类型的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
# python对int类型数据的hash函数做了额外的说明，是为了引出解决hash冲突的方法。

Major subtleties ahead:  Most hash schemes depend on having a "good" hash
function, in the sense of simulating randomness.  Python doesn't:  its most
important hash functions (for ints) are very regular in common
cases:

  >>>[hash(i) for i in range(4)]
  [0, 1, 2, 3]

This isn't necessarily bad!  To the contrary, in a table of size 2**i, taking
the low-order i bits as the initial table index is extremely fast, and there
are no collisions at all for dicts indexed by a contiguous range of ints. So
this gives better-than-random behavior in common cases, and that's very
desirable.

OTOH, when collisions occur, the tendency to fill contiguous slices of the
hash table makes a good collision resolution strategy crucial.  Taking only
the last i bits of the hash code is also vulnerable:  for example, consider
the list [i << 16 for i in range(20000)] as a set of keys.  Since ints are
their own hash codes, and this fits in a dict of size 2**15, the last 15 bits
 of every hash code are all 0:  they *all* map to the same table index.

But catering to unusual cases should not slow the usual ones, so we just take
the last i bits anyway.  It's up to collision resolution to do the rest.  If
we *usually* find the key we're looking for on the first try (and, it turns
out, we usually do -- the table load factor is kept under 2/3, so the odds
are solidly in our favor), then it makes best sense to keep the initial index
computation dirt cheap.

稍微解释一下：

很多语言中的hash函数设计的理念是基于随机数提供一个冲突性很小的hash函数，但是Python中并没有这样做，对于int类型来说，python直接将int本身的值作为哈希索引值。这产生的效果并不糟糕，相反，在2**i的哈希表中，选取低阶i位的数值作为哈希表的索引相比于通过随机性的hash函数计算得到的索引值来说是非常快的。而且在一定连续范围的int类型的数据中并不会产生冲突，通常情况下，这是一种比随机性hash行为更好的索引值选取方式。

当产生冲突时，hash冲突解决的方法显得至关重要。但是只采用低阶i位来说会带来冲突。

举个例子

1
[i << 16 for i in range(20000)]

注: i << 16表示i左移16位。

上述代码得到的每个数值转为二进制格式。如果按照之前选取低阶i位，由于左移16位后，低阶16位都是0，就会映射到同一个槽位上，从而产生冲突。为了兼容这种不寻常的例子，同时不降低正常情况下hash计算的速度。依然选用低阶i为作为hash值，而处理不寻常情况则交给hash冲突解决方案。

hash冲突解决方案的核心是如何高效的确定下一个槽位的位置，而Python中关于hash冲突的解决方案，我打算之后新开一个笔记专门学习，这里就暂且跳过。

四 、 源码分析dict的操作集和动态扩（缩）容等机制

接下来就开始阅读源码，学习下常见的dict的操作集和动态扩容。

源码位于/Objects/dictobject.c文件下。

1.字典对象引用计数加减操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 字典本身就是一个对象，可以被其他对象所引用，因而字典的引用计数用dk_refcnt表示，如下是队引用计数的加减操作，没什么好说的。

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

static inline void
dictkeys_decref(PyDictKeysObject *dk)
{
    assert(dk->dk_refcnt > 0);
#ifdef Py_REF_DEBUG
    _Py_RefTotal--;
#endif
    if (--dk->dk_refcnt == 0) {
        free_keys_object(dk);
    }
}

注：

(1).static关键字：用于控制变量的存储方式即可见性，对于全局变量来说，已经是静态存储，因此仅用作只在当前文件内访问，外部无法访问。对于局部变量来说，改变变量的存储方式，常见的在递归程序中，使用static声明，可以将变量的值保存到下一次调用的时候。

(2).inline关键字：将函数声明为内联函数，其类似于宏定义，无需将参数压入栈，调用一系列操作，相比于宏定义，可以在类中使用。在编译时，编译器会将inline修饰的函数代码段插入到调用者的代码段中，这样在执行时，就无须跳转到目标函数去执行，相比于调用普通函数，效率更高，但同样会带来空间上的开销。

2.new和free一个PyDictKeyObject对象

由于代码量太多，我不全部贴出来了，只说下其中对字典对象的复用机制。Python中的复用机制很多都是基于链表或者数组。对于字典复用的数据结构位于/include/internal/pycore_interp.h头文件中。

1
2
3
4
5
6
7
8
# define PyDict_MAXFREELIST 80
struct _Py_dict_state {
    /* Dictionary reuse scheme to save calls to malloc and free */
    PyDictObject *free_list[PyDict_MAXFREELIST];
    int numfree;
    PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
    int keys_numfree;
};

说明：

(1).free_list：指针数组，数组中每个元素都是指向PyDictObject对象的指针。存储split类型的hash表。

(2).keys_free_list：指针数组，元素指向PyDictKeyObject对象的指针。存储combined类型的hash表。

(3).numfree: free_list中空闲的个数

(4).keys_numfree: keys_free_list中空闲的个数

(5).空闲数组的最大长度不能超过80，一旦空闲数组满了，将调用PyObject_Malloc申请内存块。

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
// new_keys_object函数中代码段
static PyDictKeysObject*
new_keys_object(uint8_t log2_size)
{
    ...
    struct _Py_dict_state *state = get_dict_state();
    // 如果有空闲数组的长度未到最大上限，则从空闲数组中取出一个空的PyDictKeysObject对象
    if (log2_size == PyDict_LOG_MINSIZE && state->keys_numfree > 0) {
        dk = state->keys_free_list[--state->keys_numfree];
    }
    else
    {	
        // 新开辟的空间大小由PyDictKeysObject结构体大小, 键值对实体结构体*已用个数大小和es<<log2_size大小组成。
        dk = PyObject_Malloc(sizeof(PyDictKeysObject)
                             + (es<<log2_size大小组成,)
                             + sizeof(PyDictKeyEntry) * usable);
        if (dk == NULL) {
            PyErr_NoMemory();
            return NULL;
        }
    }
    ...
}

// free_keys_object函数
static void
free_keys_object(PyDictKeysObject *keys)
{
    ...
    if (DK_SIZE(keys) == PyDict_MINSIZE && state->keys_numfree < PyDict_MAXFREELIST) {
        state->keys_free_list[state->keys_numfree++] = keys;
        return;
    }
    PyObject_Free(keys);
    ...
}

说明：

(1).在new一个PyDictKeyObject对象前，首先会去检测下空闲数组中是否还有空闲位置，如果有，取出空的字典对象，否则调用PyObject_Malloc，为字典对象申请新的内存空间。

(2).在free一个PyDictKeyObject对象前，首先会去检查空闲数组是否满，如果不满，将其存储keys_free_list数组中; 反之，调用PyObject_Free, 释放掉字典对象。

(3).新开辟的空间大小由PyDictKeysObject结构体大小, 键值对实体结构体*已用个数大小和es<<log2_size大小组成。其中es大小取决于log2_size位数，当字典中包含大量元素时，发生扩容，将会申请更大的内存空间。所以，Python中新开辟的字典空间大小并不是线性的，一定程度上取决于log2_size大小。

3. 字典的get()涉及的底层函数_Py_dict_lookup()

在阅读_Py_dict_lookup源码前，先说明下dk_indices中可能存在的几种标识,

代码位于/Include/internal/pycore_dict.h头文件中。

1
2
3
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)  /* Used internally */
#define DKIX_ERROR (-3)

注：只要dk_indices数组槽位中的数值能够对应上dk_entries数组中的槽位，就说明键对象找到能够被找到。

在/Include/dictobject.h头文件中可以找到dict容器暴露出来的接口。以下是get()方法对应的接口。

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
PyObject *
PyDict_GetItem(PyObject *op, PyObject *key)
{
    if (!PyDict_Check(op)) {
        return NULL;
    }
    // 类型强转
    PyDictObject *mp = (PyDictObject *)op;

    Py_hash_t hash;
    
    // 如果对于非unicode编码的对象, 获取该对象的hash值, 规定了键对象必须是可哈希的
    if (!PyUnicode_CheckExact(key) ||
        (hash = ((PyASCIIObject *) key)->hash) == -1)
    {
        hash = PyObject_Hash(key);
        if (hash == -1) {
            PyErr_Clear();
            return NULL;
        }
    }

    PyThreadState *tstate = _PyThreadState_GET();
#ifdef Py_DEBUG
    // bpo-40839: Before Python 3.10, it was possible to call PyDict_GetItem()
    // with the GIL released.
    _Py_EnsureTstateNotNULL(tstate);
#endif

    /* Preserve the existing exception */
    PyObject *exc_type, *exc_value, *exc_tb;
    PyObject *value;
    Py_ssize_t ix; (void)ix;

    _PyErr_Fetch(tstate, &exc_type, &exc_value, &exc_tb);

    // 真正查找值对象的函数
    ix = _Py_dict_lookup(mp, key, hash, &value);

    /* Ignore any exception raised by the lookup */
    _PyErr_Restore(tstate, exc_type, exc_value, exc_tb);


    assert(ix >= 0 || value == NULL);
    // 返回值对象
    return value;
}

说明：

1.阅读PyDict_GetItem函数，我们可以发现真正实现查找功能的函数是_Py_dict_lookup函数。

2.字典中的键必须是可哈希的对象。

3.Python 3.10版本之前调用PyDict_GetItem()方法,可能会释放掉GIL解释器锁。

4.该函数默认会压制异常，所有的可能出现的错误都会被压制，甚至是当键值对存在，但可能由于堆栈溢出的错误也会被压制。

字典查询对应的主要源码位于/Objects/dictobject.c

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105

Py_ssize_t _Py_HOT_FUNCTION
_Py_dict_lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
{
    PyDictKeysObject *dk;
start:
    dk = mp->ma_keys;                     // PyDictKeysObject对象
    DictKeysKind kind = dk->dk_kind;      // 键的类型
    PyDictKeyEntry *ep0 = DK_ENTRIES(dk); // 找到与dk->dk_indices对应的dk_entries
    size_t mask = DK_MASK(dk);            
    size_t perturb = hash;
    size_t i = (size_t)hash & mask;       // 计算查找的值位于dk->dk_indices中的索引
    Py_ssize_t ix;
    // 检查标识以及键的类型,如果是unicode编码的键
    if (PyUnicode_CheckExact(key) && kind != DICT_KEYS_GENERAL) {
        /* Strings only */
        for (;;) {
            // 获取dk->dk_indices数组中索引i对应的数值（该数值作为dk_entries的索引值)
            ix = dictkeys_get_index(mp->ma_keys, i);
            if (ix >= 0) {
                 // 如果ix>=0,标志ix值匹配到dk_entries的索引项
                PyDictKeyEntry *ep = &ep0[ix];
                assert(ep->me_key != NULL);
                assert(PyUnicode_CheckExact(ep->me_key));
                // 比较key或者hash，然后根据hash表是split类型还是combined类型，返回对应的值
                if (ep->me_key == key ||
                        (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
                    goto found;
                }
            }
            else if (ix == DKIX_EMPTY) {
                // 如果ix等于DKIX_EMPTY，标识查找不到该键，结束查找
                *value_addr = NULL;
                return DKIX_EMPTY;
            }
            // 重新计算下一个槽位，然后再次在dk_indices数组中搜索，反复计算，直到遇见值为-1的槽位。
            perturb >>= PERTURB_SHIFT;
            i = mask & (i*5 + perturb + 1);
            ix = dictkeys_get_index(mp->ma_keys, i);
            if (ix >= 0) {
                PyDictKeyEntry *ep = &ep0[ix];
                assert(ep->me_key != NULL);
                assert(PyUnicode_CheckExact(ep->me_key));
                if (ep->me_key == key ||
                        (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {
                    goto found;
                }
            }
            else if (ix == DKIX_EMPTY) {
                *value_addr = NULL;
                return DKIX_EMPTY;
            }
            perturb >>= PERTURB_SHIFT;
            i = mask & (i*5 + perturb + 1);
        }
        Py_UNREACHABLE();
    }
    // 键为其他类型
    for (;;) {
        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) {
                goto found;
            }
            if (ep->me_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) {
                        goto found;
                    }
                }
                else {
                    /* The dict was mutated, restart */
                    goto start;
                }
            }
        }
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
    }
    Py_UNREACHABLE();
found:
    // split类型
    if (dk->dk_kind == DICT_KEYS_SPLIT) {
        *value_addr = mp->ma_values[ix];
    }
    // combined类型
    else {
        *value_addr = ep0[ix].me_value;
    }
    return ix;
}

注：Python3中，str对象默认是unicode编码的，所以对于以str对象作为键的字典，调用get()方法通常会进入第一个if分支。

说明：

具体的注释在源码中已经写了，下面主要总结一下查找键的过程。

(1).执行宏定义DK_ENTRIES，找到与dk->dk_indices对应的dk_entries，通过(size_t)hash & mask与运算计算出dk->dk_indices中的目标索引。

(2).检查键key的类型，如果是unicode编码的对象，如str，进入if分支。进入步骤(2)。

(3).通过调用dictkeys_get_index()方法，获取dk->dk_indices数组中索引i对应的数值ix（该数值作为dk_entries的索引值)。

(4).如果数值ix >= 0, 匹配到dk_entries的索引项，获取到对应的键值对实体对象ep，进入步骤(5)；如果数值ix == -1,表示遇到断链，无法继续查找，标识该键不存在，查找结束。其余情况，如ix==-2，可能槽位被其他键占用了，因此继续计算下一槽位，然后再次在dk_indices数组中搜索，反复执行步骤(4)，直到ix值 >=0 ，找到键，或者 ix值==-1退出。

(5).比较键值对实体对象ep->me_key对象与给定的key对象，或者比较他们的hash值是否相等

(6)如果相等，判断hash表的类型是split还是combined的，如果是spilt，从PyDictObject对象的ma_values获取对应值；如果是combined，从键值对实体PyDictKeyEntry对象中的me_value获取对应值。

4.字典的__setitem__涉及的底层函数PyDict_SetItem()

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
int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    mp = (PyDictObject *)op;
    // 键对象同样必须是可哈希的
    if (!PyUnicode_CheckExact(key) ||
        (hash = ((PyASCIIObject *) key)->hash) == -1)
    {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }

    // 如果mp->ma_keys对象的地址等于全局唯一的空对象的地址, 向空字典中插入
    if (mp->ma_keys == Py_EMPTY_KEYS) {
        return insert_to_emptydict(mp, key, hash, value);
    }
    /* insertdict() handles any resizing that might be necessary */
    // 包含动态扩容机制
    return insertdict(mp, key, hash, value);
}

说明：

1.键对象同样必须是可哈希的

2.插入键值对分两个函数, 当字典为空，等于全局唯一空对象时,调用insert_to_emptydict函数,不为空，调用insertdict函数,其中包含动态扩容机制。

字典插入的源码主要位于/Objects/dictobject.c

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;
    PyDictKeyEntry *ep;

    // 键对象, 值对象的引用计数+1
    Py_INCREF(key);
    Py_INCREF(value);
    
    if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
        // 动态扩容失败
        if (insertion_resize(mp) < 0)
            goto Fail;
    }

    // 判断键是否存在
    Py_ssize_t ix = _Py_dict_lookup(mp, key, hash, &old_value);
    // 键比较过程出错
    if (ix == DKIX_ERROR)
        goto Fail;

    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. */
        mp->ma_keys->dk_version = 0;
        assert(old_value == NULL);
        // 如果容器可用空间<=0, 则需要进行扩容
        if (mp->ma_keys->dk_usable <= 0) {
            /* Need to resize. */
            if (insertion_resize(mp) < 0)
                goto Fail;
        }
        if (!PyUnicode_CheckExact(key) && mp->ma_keys->dk_kind != DICT_KEYS_GENERAL) {
            mp->ma_keys->dk_kind = DICT_KEYS_GENERAL;
        }
        // 查找空槽位
        Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
        // 获取到键值对实体数组中的空位置，dk_nentries表示已用的键值对个数
        ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
        // 将键值对实体数组中待插入键值对的索引映射到哈希索引数组中索引为hashpos的槽位上
        dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
        // 赋值
        ep->me_key = key;
        ep->me_hash = hash;
        // 针对split/combined将值添加到指定值
        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;
    }
    
    // 如果字典中存在该键, 判断是否覆盖。

    // 字典键对应的值变了, 根据hash表不同类型进行覆盖
    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();
    }
    // 将旧值对象的引用计数减1
    // 因为值也是个对象
    // 如果重复执行dicts["name"] = obj1, 那么old_value的地址 == value, 因此Py_XDECREF(old_value) ==> Py_XDECREF(value)
    Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
    ASSERT_CONSISTENT(mp);
    // 由于键本身存在, 因此将key的引用计数减1
    Py_DECREF(key);
    return 0;

Fail:
    Py_DECREF(value);
    Py_DECREF(key);
    return -1;
}

源码的面容我们已经目睹，接下来就庖丁解牛，分析各个步骤：

(1).因为涉及到容器的操作，所以需要将键对象和值对象的引用计数分别+1。

(2).执行_Py_dict_lookup函数，判断键是否存在于字典中，如果不存在返回-1, 进入步骤(3); 如果存在, 进入步骤(8)。

(3).如果字典中不存在该键，需要将键添加进去，接下来判断字典容器是否还有可用空间, 如果没有，需要进行动态扩容，调用insertion_resize函数,函数体如下:

1
// 动态扩容的分析在下方

(4).查找哈希索引数组中的槽位值为-1的空槽位, 函数体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
    assert(keys != NULL);

    const size_t mask = DK_MASK(keys);
    // hash与字典容量-1进行与运算
    size_t i = hash & mask;
    // 获取hash索引数组中的索引为i的值
    Py_ssize_t ix = dictkeys_get_index(keys, i);
    // 反复查找下一个槽位, 直到对应的槽位的值匹配不到键值对实体对象中的索引项，即ix == -1 的空槽位。
    for (size_t perturb = hash; ix >= 0;) {
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
        ix = dictkeys_get_index(keys, i);
    }
    return i;
}

(5).执行宏定义ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries]获取到键值对实体数组dk_entries中的空位置，dk_nentries表示已用的键值对个数。由此，我们可以了解，Python中的键值对对象是顺序添加到数组中的。

(6).将键值对实体数组中待插入键值对的索引映射到哈希索引数组中索引为hashpos的槽位上。等价于mp->ma_keys->dk_indices[hashpos] = mp->ma_keys->dk_nentries

(7).对键值对结构体字段进行赋值,针对split/combined将值添加到指定字段上；修改mp的字段的数据，修改字典中的总键值对个数, 可用个数, 已用个数。最后返回0。

(8).如果字典中存在改键，判断是否需要覆盖，如果字典键对应的值改变，根据hash表不同类型进行覆盖。

(9).最后，将旧的值对象和键对象的引用计数减一，这里有一个注意点，如果old_value == value，两个对象地址相同，不需要进行覆盖，其引用计数在insertdict函数中不发生变化, 因此Py_XDECREF(old_value) <==> Py_XDECREF(value)，是不是非常的妙呢~

注:

通过阅读源码，不仅了解前辈们实现算法的思路，同时也能感受到逻辑的严密性。对于键对象来说，添加到容器中并不会增加引用计数, 而对于值对象来说，会增加引用计数。

特别是下面操作引用计数的这一代码段，我直呼妙哉！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 Py_INCREF(value);
 ...
 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();
    }
    // 将旧值对象的引用计数减1
    // 因为值也是个对象
    // 如果重复执行dicts["name"] = obj1, 那么old_value的地址 == value, 因此Py_XDECREF(old_value) ==> Py_XDECREF(value)
Py_XDECREF(old_value);
    ...

5.字典的动态扩(缩)容机制

Python中字典的动态扩(缩)容和其他语言中不一样，有些语言中字典的扩(缩)容是在原数据上进行，而有些语言会开辟一个更大(小)的容器，并将数据从原容器依次移到新容器中，接下来就学习下Python字典的动态扩(缩)容机制。

源码位于/Objects/dictobject.c中

1
2
3
4
5
6
static int
insertion_resize(PyDictObject *mp)
// 动态扩容
{
    return dictresize(mp, calculate_log2_keysize(GROWTH_RATE(mp)));
}

说明：

dictresize接受两个参数，第一个为带扩(缩)容的字典对象，第二个为预计扩(缩)容后的最小位数。

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
92
93
94
95
96
97
98
99
100
101
102
103
104
static int
dictresize(PyDictObject *mp, uint8_t log2_newsize)
{
    Py_ssize_t numentries;
    PyDictKeysObject *oldkeys;  // combined的字典
    PyObject **oldvalues;       
    PyDictKeyEntry *oldentries, *newentries;  // 新旧键值对实体

    if (log2_newsize >= SIZEOF_SIZE_T*8) {
        PyErr_NoMemory();
        return -1;
    }
    assert(log2_newsize >= PyDict_LOG_MINSIZE);

    oldkeys = mp->ma_keys;

    /* NOTE: Current odict checks mp->ma_keys to detect resize happen.
     * So we can't reuse oldkeys even if oldkeys->dk_size == newsize.
     * TODO: Try reusing oldkeys when reimplement odict.
     */

    /* Allocate a new table. */
    mp->ma_keys = new_keys_object(log2_newsize);
    if (mp->ma_keys == NULL) {
        // 申请内存失败, 扩(缩)容失败
        mp->ma_keys = oldkeys;
        return -1;
    }
    // New table must be large enough.
    assert(mp->ma_keys->dk_usable >= mp->ma_used);
    if (oldkeys->dk_kind == DICT_KEYS_GENERAL)
        mp->ma_keys->dk_kind = DICT_KEYS_GENERAL;

    numentries = mp->ma_used;
    oldentries = DK_ENTRIES(oldkeys);
    newentries = DK_ENTRIES(mp->ma_keys);
    oldvalues = mp->ma_values;
    // split -> combined
    if (oldvalues != NULL) {
        /* Convert split table into new combined table.
         * We must incref keys; we can transfer values.
         * Note that values of split table is always dense.
         */
        for (Py_ssize_t i = 0; i < numentries; i++) {
            assert(oldvalues[i] != NULL);
            PyDictKeyEntry *ep = &oldentries[i];
            PyObject *key = ep->me_key;
            Py_INCREF(key);
            newentries[i].me_key = key;
            newentries[i].me_hash = ep->me_hash;
            newentries[i].me_value = oldvalues[i];
        }

        dictkeys_decref(oldkeys);
        mp->ma_values = NULL;
        if (oldvalues != empty_values) {
            free_values(oldvalues);
        }
    }
    else {  // combined table.
        // 如果扩(缩)容后的大小和原数组大小一直, 采用memcpy拷贝过去, 意味着扩(缩)容前后,大小相等,不会对原数组进行复用
        if (oldkeys->dk_nentries == numentries) {
            memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry));
        }
        else {
            // ep指向旧键值对实体数组的首地址, 索引次序相对于原数组可能会发生变化
            PyDictKeyEntry *ep = oldentries;
            for (Py_ssize_t i = 0; i < numentries; i++) {
                // 忽略掉为值对象为NULL的键值对实体
                while (ep->me_value == NULL)
                    ep++;
                // 将地址指向的数据添加到新数组中的位置上
                newentries[i] = *ep++;
            }
        }

        assert(oldkeys->dk_kind != DICT_KEYS_SPLIT);
        assert(oldkeys->dk_refcnt == 1);
#ifdef Py_REF_DEBUG
        _Py_RefTotal--;
#endif
        struct _Py_dict_state *state = get_dict_state();
#ifdef Py_DEBUG
        // dictresize() must not be called after _PyDict_Fini()
        assert(state->keys_numfree != -1);
#endif  

        // 如果缩容后的大小为初始大小8,在空闲数组有余量的情况下,会缓存到空闲数组中, 反之直接回收内存资源。
        if (DK_SIZE(oldkeys) == PyDict_MINSIZE &&
            state->keys_numfree < PyDict_MAXFREELIST)
        {
            state->keys_free_list[state->keys_numfree++] = oldkeys;
        }
        else {
            PyObject_Free(oldkeys);
        }
    }

    // 针对新的键值对实体数组, 重新构建hash索引数组, 即重新计算每个对象的hash值, 匹配对应的槽位, 形成映射关系。
    build_indices(mp->ma_keys, newentries, numentries);
    mp->ma_keys->dk_usable -= numentries;
    mp->ma_keys->dk_nentries = numentries;
    return 0;
}

分析：

(1).计算预计扩(缩)容后的最小位数，根据最小位数，申请一个更大的字典结构体。如果申请内存失败，将导致扩(缩)容失败。

(2).将split类型的hash表转为combined的hash表，如果旧的hash表是split类型，不仅需要将键值对实体拷贝过去，同时也要将旧hash表中的键对象的引用计数都减1。

(3).如果旧的hash表是combined类型，又分两种情况。如果扩(缩)容后的大小和原数组大小一致, 采用memcpy拷贝过去, 意味着扩容前后,大小相等,不会对原数组进行复用；反之，遍历新的键值对实体数组，将旧的动态数组中对象依次赋值过去。

(4).扩(缩)容完成，需要考虑到内存空间的复用，如果缩容后的大小为初始大小8,在空闲数组有余量的情况下,会缓存到空闲数组中state->keys_free_list, 实现状态管理, 反之直接回收内存资源。

(5).由于是申请了新的内存空间，因此需要针对新的键值对实体数组,和新的hash索引数组, 调用build_indices函数重新构建映射关系。

(6).修改字典可用空间和键值对实体数组大小，至此，动态扩(缩)容的全貌已经展现。

总结：

1.字典是否需要扩缩容，在于字典中可用的个数是否大于等于0，即_dictkeysobject中的dk_usable 是否 >=0。

2.Python中的扩缩容并不会基于原对象实现，而是申请一块合适大小的新对象。并将原对象上的键值对对象依次拷贝过去。

3.扩缩容完成，如果缩容后变成了空字典，即容量为8，则需要加入到空闲数组中，减少频繁申请内存空间，实现字典复用。

4.字典的查询速度非常快，Python中并没有采用类似C++的map的红黑树结构，采用的是更为简单的两个数组—–hash索引数组，键值对实体数组，形成一种映射关系，两者都是动态数组。

5.Python字典的查找是首先根据hash & mask(掩码,mask是随着字典容量变化而变化的)，计算出在hash索引数组中的下标，然后得到下标对应的值，即键值对实体数组中的下标，最终得到键值对实体数组中对应槽位的键值对实体指针。根据指针找到具体的结构体对象。因此动态扩(缩)容后, mask发生变化，如果按照之前的映射关系，将无法正确定位到键，所以需要重新构建新hash索引数组和新键值对实体数组之间的映射关系。