CPython对象模型：Dict-白红宇

CPython对象模型：Dict

阅读量：5236 次

发布时间：2019-06-14

本文共 20705 字，大约阅读时间需要 69 分钟。

此系列前几篇：

除了list以外，dict也是python中十分常用的一种基本数据结构。而且，dict在python内部被大量应用， dict的效率会直接影响python的运行效率，因此python的作者们对dict进行了精心的设计和优化。本篇博客会从源码出发仔细分析一下python中的dict。

1 结构

由于对dict的效率有着严格要求， python中的dict采用了hash表来实现。众所周知，hash表可能存在有冲突，解决冲突也有若干种方法，典型的有开链法（即把冲突的元素排成一个链，它们放在同一个格子下）和开放地址法（即给冲突元素找一个新的地址，独占一个新的格子）。 python采用了开放地址法。

dict中用到了以下几个数据结构：

PyDictObject：对应python中的dict

PyDictKeysObject：对应dict中所有key的集合

PyDictKeyEntry：对应一个(key, value)对

1.1 PyDictObject

/* file:Include/dictobject.h */typedef struct {    PyObject_HEAD    Py_ssize_t ma_used;    PyDictKeysObject *ma_keys;    PyObject **ma_values;} PyDictObject;

ma_used：代表了当前dict中已用存储单元的个数

ma_keys：dict中key的集合（也可能会有值）

ma_values：可能存放dict中的value，也可能什么也没有。

这里需要说一下dict的特殊之处。

dict中把一个(key, value)对称为一个slot（严格来说一个slot是指一个PyDictEntry类型的变量）。 python中的slot存在4种不同的状态：

Unused

Active

Dummy

Pending

Unused表示此slot尚未使用，所有slot都会初始化成该状态； Active表示此slot正在使用中； Dummy表示此slot已被删除； Pending表示此slot尚未被插入到dict中或尚未被删除。

为什么会存在表示已删除的状态呢？之前提到过，dict采用了开放地址法，存在冲突时会依次寻找新的地址，直到找到空的slot（Unused状态）或者需要查找的key。这样的查找过程，实际上形成了一个查找链，查找链的结尾是一个Unused或Active状态的slot。发现问题了吧？如果查找链中间某一个slot被删除，并重新回到了Unused状态，那么这个查找链就会被截断，导致后面的部分不能被找到。因此Dummy存在的意义就在于维持查找链的完整。

为什么看起来像存储容器的ma_values可能啥也不存呢？因为python中的dict有两种，一种叫combined-table dict，一种叫split-table dict。 combined-talbe dict会把值以(key, value)的形式存储在ma_keys中，而split-table dict才会把值存放在ma_values中。

这两种dict有什么区别呢？用途上的区别暂且不提，内容上的区别除了之前提到的值存储位置的不同外，还有就是split-table dict中所有的key必须为string类型，且不能存在dummy状态的key。 combined-talbe dict中key可以为任意类型的对象，但是slot不能出现pending状态。

1.2 PyDictKeysObject

/* file:Objects/dictobject.c */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 _dictkeysobject PyDictKeysObject

dk_refcnt：引用数。PyDictKeysObject不是衍生自PyObject，所以需要额外加上这个

dk_size：hash表大小

dk_lookup：查找函数。python针对不同类型的dict做了若干查找优化，所以dict的查找函数可能不同

dk_usable：dict的剩余可用大小（对于空dict，dk_usable = (2*dk_size+1)/3）。研究发现，hash表中填充率超过2/3后冲突率会急剧上升，因此为了提高效率，python设定dict中使用dk_usable个slot时（即dk_usable ≤ 0时）会触发resize扩大dict以保持低冲突率。 dk_usable会减少当且仅当unused状态的slot数量减少。

dk_entries：实际的数据区。和之前的变长对象类似，分配空间时都会在dk_entries后分配多余空间以便使用。

1.3 PyDictKeyEntry

/* file:Objects/dictobject.c */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：此key的hash值。储存hash值可以避免重复计算，提高效率

me_value：若为split table，me_value无意义。

前面说过，slot有四种状态。这四种状态并未单独保存，而是由me_key和me_value决定：

Unused
- me_key == NULL
- me_value == NULL

Active
- me_key != NULL
- me_key != dummy
- me_value != NULL

Dummy
- me_key == dummy
- me_value == NULL

Pending
- me_key != NULL
- me_key !=dummy
- me_value == NULL

这里频频出现的dummy到底是何方神圣？ dummy的定义如下：

/* file:Objects/dictobject.c */static PyObject _dummy_struct;#define dummy (&_dummy_struct)

dummy就是一个独一无二的PyObject而已。

2 dict的创建

2.1 创建dict

/* file:Objects/dictobject.c */PyObject *PyDict_New(void){    PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE_COMBINED);    if (keys == NULL)        return NULL;    return new_dict(keys, NULL);}

可以使用PyDict_New函数来新建一个dict。这个函数的定义十分简单，先新建一个大小为PyDict_MINSIZE_COMBINED的keys，然后新建dict即可。

这里我们会发现PyDict_MINSIZE_COMBINED这个常量。这个常量是combined table的默认最小大小，它的值为8。

需要注意，通过该函数会新建一个combine-table dict。 split-table dict更多的应用于python内部，我们使用的dict普遍是combined-table dict。

2.1.1 新建keys

/* file:Objects/dictobject.c */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));    dk = PyMem_MALLOC(sizeof(PyDictKeysObject) +                      sizeof(PyDictKeyEntry) * (size-1));    if (dk == NULL) {        PyErr_NoMemory();        return NULL;    }    DK_DEBUG_INCREF dk->dk_refcnt = 1;    dk->dk_size = size;    dk->dk_usable = USABLE_FRACTION(size);    ep0 = &dk->dk_entries[0];    /* Hash value of slot 0 is used by popitem, so it must be initialized */    ep0->me_hash = 0;    for (i = 0; i < size; i++) {        ep0[i].me_key = NULL;        ep0[i].me_value = NULL;    }    dk->dk_lookup = lookdict_unicode_nodummy;    return dk;}

这个函数的作用很简单，就是根据给定的大小分配足够的空间并初始化而已。这里值得注意的是函数开始的两句断言：

size >= PyDict_MINSIZE_SPLIT

IS_POWER_OF_2(size)

也就是说，keys最小大小为PyDict_MINSIZE_SPLIT，且这个大小必须是2的n次方。

2.1.2 新建dict

/* file:Objects/dictobject.c */static PyObject *new_dict(PyDictKeysObject *keys, PyObject **values){    PyDictObject *mp;    assert(keys != NULL);    if (numfree) {        mp = free_list[--numfree];        assert (mp != NULL);        assert (Py_TYPE(mp) == &PyDict_Type);        _Py_NewReference((PyObject *)mp);    }    else {        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);        if (mp == NULL) {            DK_DECREF(keys);            free_values(values);            return NULL;        }    }    mp->ma_keys = keys;    mp->ma_values = values;    mp->ma_used = 0;    return (PyObject *)mp;}

实际用来生成新的dict对象的函数为new_dict。在new_dict的实现中，又看到了和list中一样的对象池机制。

实际上，该对象池的实现和list的几乎一模一样，填充对象池都是在dealloc操作中完成。类似的，dict对象池中的对象不会保留具体的数据区（ma_keys和ma_values）。

2.2 Key-sharing Dict

查看dictobject.c文件，会发现除了new_dict系列，还有new_dict_with_shared_keys系列。这个系列的函数是用于处理Key-sharing dict的。

Key-sharing dict是啥呢？其实就是key共享的dict。这里只介绍一些大概的内容，具体的说明见。

Key-sharing dict的主要用作对象的__dict__属性。使用这种dict可以把使同一类型的对象实例采用共享的key，从而节约空间。由于需要共享key，所以Key-sharing dict需要把值和key分离，因此此类dict是split-table dict。

新建一个Key-sharing dict关键在于需要新建shared keys，需要调用如下函数：

/* file:Objects/dictobject.c */static PyDictKeysObject *make_keys_shared(PyObject *op){    Py_ssize_t i;    Py_ssize_t size;    PyDictObject *mp = (PyDictObject *)op;    if (!PyDict_CheckExact(op))        return NULL;    if (!_PyDict_HasSplitTable(mp)) {        /* 若不是Split Table，将其转换为split table */        PyDictKeyEntry *ep0;        PyObject **values;        assert(mp->ma_keys->dk_refcnt == 1);        if (mp->ma_keys->dk_lookup == lookdict) {            return NULL;        }        else if (mp->ma_keys->dk_lookup == lookdict_unicode) {            /* Remove dummy keys */            if (dictresize(mp, DK_SIZE(mp->ma_keys)))                return NULL;        }        assert(mp->ma_keys->dk_lookup == lookdict_unicode_nodummy);        /* Copy values into a new array */        ep0 = &mp->ma_keys->dk_entries[0];        size = DK_SIZE(mp->ma_keys);        values = new_values(size);        if (values == NULL) {            PyErr_SetString(PyExc_MemoryError,                "Not enough memory to allocate new values array");            return NULL;        }        for (i = 0; i < size; i++) {            values[i] = ep0[i].me_value;            ep0[i].me_value = NULL;        }        mp->ma_keys->dk_lookup = lookdict_split;        mp->ma_values = values;    }    /* 增加ma_keys的引用并返回它 */    DK_INCREF(mp->ma_keys);    return mp->ma_keys;}

这个函数的参数是一个dict类型的对象。对于split-table dict，它直接返回ma_keys；对于combined-table dict，它会尝试把该dict新建一个split table 并把值从ma_keys中移动到split table中。转换过程中进行了严格的检查以确保转换后可以满足split table的条件。如果转换失败，则返回NULL。

之后再调用new_dict_with_shared_keys即可产生一个新的Key-sharing dict。

3 dict的查找

python中提供了两类默认搜索方法，一类针对combined-table dict，另一类针对split-table dict。

针对combined-table dict的查找中，有通用的lookdict，还有针对key只为string这种特例的lookdict_unicode，也有限制更严格的lookdict_unicode_nodummy。总的来说，它们的算法类似，区别只在于后两个对于输入数据的限制更严且做了一些针对性的优化。

3.1 lookdict

lookdict函数定义如下：

1 /* file:Objects/dictobject.c */ 2 static PyDictKeyEntry * 3 lookdict(PyDictObject *mp, PyObject *key, 4          Py_hash_t hash, PyObject ***value_addr) 5 { 6     size_t i; 7     size_t perturb; 8     PyDictKeyEntry *freeslot; 9     size_t mask;10     PyDictKeyEntry *ep0;11     PyDictKeyEntry *ep;12     int cmp;13     PyObject *startkey;14 15 top:16     mask = DK_MASK(mp->ma_keys);17     ep0 = &mp->ma_keys->dk_entries[0];18     i = (size_t)hash & mask;19     ep = &ep0[i];20     if (ep->me_key == NULL || ep->me_key == key) {21         *value_addr = &ep->me_value;22         return ep;23     }24     if (ep->me_key == dummy)25         freeslot = ep;26     else {27         if (ep->me_hash == hash) {28             startkey = ep->me_key;29             Py_INCREF(startkey);30             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);31             Py_DECREF(startkey);32             if (cmp < 0)33                 return NULL;34             if (ep0 == mp->ma_keys->dk_entries && ep->me_key == startkey) {35                 if (cmp > 0) {36                     *value_addr = &ep->me_value;37                     return ep;38                 }39             }40             else {41                 /* The dict was mutated, restart */42                 goto top;43             }44         }45         freeslot = NULL;46     }47 48     /* In the loop, me_key == dummy is by far (factor of 100s) the49        least likely outcome, so test for that last. */50     for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {51         i = (i << 2) + i + perturb + 1;52         ep = &ep0[i & mask];53         if (ep->me_key == NULL) {54             if (freeslot == NULL) {55                 *value_addr = &ep->me_value;56                 return ep;57             } else {58                 *value_addr = &freeslot->me_value;59                 return freeslot;60             }61         }62         if (ep->me_key == key) {63             *value_addr = &ep->me_value;64             return ep;65         }66         if (ep->me_hash == hash && ep->me_key != dummy) {67             startkey = ep->me_key;68             Py_INCREF(startkey);69             cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);70             Py_DECREF(startkey);71             if (cmp < 0) {72                 *value_addr = NULL;73                 return NULL;74             }75             if (ep0 == mp->ma_keys->dk_entries && ep->me_key == startkey) {76                 if (cmp > 0) {77                     *value_addr = &ep->me_value;78                     return ep;79                 }80             }81             else {82                 /* The dict was mutated, restart */83                 goto top;84             }85         }86         else if (ep->me_key == dummy && freeslot == NULL)87             freeslot = ep;88     }89     assert(0);          /* NOT REACHED */90     return 0;91 }

函数的参数中，*value_addr是指向匹配slot中值的指针。这个函数在正确的情况下一定会返回一个指向slot的指针，出错则会返回NULL。如果成功找到了匹配的slot，则返回对应的slot；如果没有匹配的slot，则返回查找链上第一个未被使用的slot。该slot可以是unused状态，也可以是dummy状态。

在函数的16~19行，计算了slot的初始位置，把hash值映射到slot table的下标范围内。初始位置=hash&mask，mask=dk_size-1。

20~22行，如果找到了匹配的key或unused slot，返回该结果即可。

24~45行进行了进一步的比较。若该slot状态为dummy，则用freeslot记录该slot并继续搜索；如果该slot的hash值与待搜索key的hash相同，那么对两个key进行比较。这里的PyObject_RichCompareBool是一个比较函数，其第三个参数为比较的操作。如果操作结果为true，返回1；为false，返回0；比较出错，返回-1。比较出错的情况下会返回NULL，比较成功（在这里为相等）返回该slot，比较不成功则继续进行搜索。这一部分进行了第一次的搜索；在dict容量不太满时，一般在这里就可以找到合适的结果。

在50~88行则进行了接下来的搜索。这里需要计算下一个查找元素的下标：对当前下标i，新的下标i=5*i+1+perturb，perturb是一个和hash值相关的数。这样计算的原因可以参考Objects/dictobject.c开头的那段注释。

53~61行是找到了unused slot的情况。如果freeslot是NULL，那么返回该slot即可；若freeslot不是NULL，那么返回freeslot。

62~65行则是找到了匹配的key。此情况返回对应slot即可。

66~85行是该slot hash值与给定hash值相同时进一步比较的情况。这里和前面的比较一样，所以不再说明了。

86~87行是在dummy情况下设置freeslot。

在搜索过程中，原则是找到和key相等的对象即可。那么什么是和key相等呢？一种情况是它们的引用相等，自然的值也相等。这类比较只需要直接比较对应指针是否相等呢该即可。而另一种情况是引用不相等，但值还相等。如果没有对这种情况的处理，那么对于非共享的对象来说搜索几乎不会得到正确的结果。搜索中的进一步比较就是对这种情况的处理。进一步比较发生的前提是hash值相等，因为值相等必然有hash相等，但hash相等值却可能不等，因此不能直接比较hash值，还需要更进一步的比较值才可以。

3.2 lookdict_unicode

这个函数和lookdict的区别除了在于dict中key的类型有限制外，还在于返回值不同。 lookdict可能会在比较失败时返回NULL，可此函数比较不会失败，因此永远不会返回NULL。

其定义如下：

/* file:Objects/dictobject.c */static PyDictKeyEntry *lookdict_unicode(PyDictObject *mp, PyObject *key,                 Py_hash_t hash, PyObject ***value_addr){    size_t i;    size_t perturb;    PyDictKeyEntry *freeslot;    size_t mask = DK_MASK(mp->ma_keys);    PyDictKeyEntry *ep0 = &mp->ma_keys->dk_entries[0];    PyDictKeyEntry *ep;    /* Make sure this function doesn't have to handle non-unicode keys,       including subclasses of str; e.g., one reason to subclass       unicodes is to override __eq__, and for speed we don't cater to       that here. */    if (!PyUnicode_CheckExact(key)) {        mp->ma_keys->dk_lookup = lookdict;        return lookdict(mp, key, hash, value_addr);    }    i = (size_t)hash & mask;    ep = &ep0[i];    if (ep->me_key == NULL || ep->me_key == key) {        *value_addr = &ep->me_value;        return ep;    }    if (ep->me_key == dummy)        freeslot = ep;    else {        if (ep->me_hash == hash && unicode_eq(ep->me_key, key)) {            *value_addr = &ep->me_value;            return ep;        }        freeslot = NULL;    }    /* In the loop, me_key == dummy is by far (factor of 100s) the       least likely outcome, so test for that last. */    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {        i = (i << 2) + i + perturb + 1;        ep = &ep0[i & mask];        if (ep->me_key == NULL) {            if (freeslot == NULL) {                *value_addr = &ep->me_value;                return ep;            } else {                *value_addr = &freeslot->me_value;                return freeslot;            }        }        if (ep->me_key == key            || (ep->me_hash == hash            && ep->me_key != dummy            && unicode_eq(ep->me_key, key))) {            *value_addr = &ep->me_value;            return ep;        }        if (ep->me_key == dummy && freeslot == NULL)            freeslot = ep;    }    assert(0);          /* NOT REACHED */    return 0;}

这个函数和lookdict几乎一模一样，比较中唯一的区别在于比较时用了unicode_eq这个针对str对象的比较。类似的，lookdict_unicode_nodummy和lookdict也是几乎一样的，这里就不再细说了。

3.3 lookdict_split

1 /* file:Objects/dictobject.c */ 2 static PyDictKeyEntry * 3 lookdict_split(PyDictObject *mp, PyObject *key, 4                Py_hash_t hash, PyObject ***value_addr) 5 { 6     size_t i; 7     size_t perturb; 8     size_t mask = DK_MASK(mp->ma_keys); 9     PyDictKeyEntry *ep0 = &mp->ma_keys->dk_entries[0];10     PyDictKeyEntry *ep;11 12     if (!PyUnicode_CheckExact(key)) {13         ep = lookdict(mp, key, hash, value_addr);14         /* lookdict expects a combined-table, so fix value_addr */15         i = ep - ep0;16         *value_addr = &mp->ma_values[i];17         return ep;18     }19     i = (size_t)hash & mask;20     ep = &ep0[i];21     assert(ep->me_key == NULL || PyUnicode_CheckExact(ep->me_key));22     if (ep->me_key == NULL || ep->me_key == key ||23         (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {24         *value_addr = &mp->ma_values[i];25         return ep;26     }27     for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {28         i = (i << 2) + i + perturb + 1;29         ep = &ep0[i & mask];30         assert(ep->me_key == NULL || PyUnicode_CheckExact(ep->me_key));31         if (ep->me_key == NULL || ep->me_key == key ||32             (ep->me_hash == hash && unicode_eq(ep->me_key, key))) {33             *value_addr = &mp->ma_values[i & mask];34             return ep;35         }36     }37     assert(0);          /* NOT REACHED */38     return 0;39 }

这个函数是专门用在split-table dict上的。它的算法和lookdict_unicode_nodummy一样，区别就在于key对应的值的位置不同。

有一点需要注意的是，在12~18行中，对于不符合条件的dict调用了lookdict。因为lookdict设置的value_addr会指向slot内部的值，所以之后还修改了value_addr指向的位置。

4 dict的维护

4.1 调整dict大小

在dict中插入元素可能导致dict大小的改变。改变dict大小会使用dictresize函数。它的定义如下：

1 /* file:Objects/dictobject.c */ 2 static int 3 dictresize(PyDictObject *mp, Py_ssize_t minused) 4 { 5     Py_ssize_t newsize; 6     PyDictKeysObject *oldkeys; 7     PyObject **oldvalues; 8     Py_ssize_t i, oldsize; 9 10 /* Find the smallest table size > minused. */11     for (newsize = PyDict_MINSIZE_COMBINED;12          newsize <= minused && newsize > 0;13          newsize <<= 1)14         ;15     if (newsize <= 0) {16         PyErr_NoMemory();17         return -1;18     }19     oldkeys = mp->ma_keys;20     oldvalues = mp->ma_values;21     /* Allocate a new table. */22     mp->ma_keys = new_keys_object(newsize);23     if (mp->ma_keys == NULL) {24         mp->ma_keys = oldkeys;25         return -1;26     }27     if (oldkeys->dk_lookup == lookdict)28         mp->ma_keys->dk_lookup = lookdict;29     oldsize = DK_SIZE(oldkeys);30     mp->ma_values = NULL;31     /* If empty then nothing to copy so just return */32     if (oldsize == 1) {33         assert(oldkeys == Py_EMPTY_KEYS);34         DK_DECREF(oldkeys);35         return 0;36     }37     /* Main loop below assumes we can transfer refcount to new keys38      * and that value is stored in me_value.39      * Increment ref-counts and copy values here to compensate40      * This (resizing a split table) should be relatively rare */41     if (oldvalues != NULL) {42         for (i = 0; i < oldsize; i++) {43             if (oldvalues[i] != NULL) {44                 Py_INCREF(oldkeys->dk_entries[i].me_key);45                 oldkeys->dk_entries[i].me_value = oldvalues[i];46             }47         }48     }49     /* Main loop */50     for (i = 0; i < oldsize; i++) {51         PyDictKeyEntry *ep = &oldkeys->dk_entries[i];52         if (ep->me_value != NULL) {53             assert(ep->me_key != dummy);54             insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);55         }56     }57     mp->ma_keys->dk_usable -= mp->ma_used;58     if (oldvalues != NULL) {59         /* NULL out me_value slot in oldkeys, in case it was shared */60         for (i = 0; i < oldsize; i++)61             oldkeys->dk_entries[i].me_value = NULL;62         assert(oldvalues != empty_values);63         free_values(oldvalues);64         DK_DECREF(oldkeys);65     }66     else {67         assert(oldkeys->dk_lookup != lookdict_split);68         if (oldkeys->dk_lookup != lookdict_unicode_nodummy) {69             PyDictKeyEntry *ep0 = &oldkeys->dk_entries[0];70             for (i = 0; i < oldsize; i++) {71                 if (ep0[i].me_key == dummy)72                     Py_DECREF(dummy);73             }74         }75         assert(oldkeys->dk_refcnt == 1);76         DK_DEBUG_DECREF PyMem_FREE(oldkeys);77     }78     return 0;79 }

此函数的输入参数为待操作的dict和新的最小大小。无论是combined-table dict还是split-table dict，调用此函数后都会变成combined-table dict。如果需要再恢复为split-table dict，只需要调用make_keys_shared即可。

在11~18行，寻找一个合适的新大小并进行内存检查。这里需再次注意，dict所占的空间都是2的n次幂。

41~47行，把split table中的值转义到combined table中。

50~55行，把所有处于active状态的slot插入到新的combine table中。为什么不把dummy slot也插入呢？这样查找链不就断了？在执行insertdict_clean过程中，会找到新的Unused slot，这个过程中会重建查找链，所以不必插入dummy slot。

57行维护了dk_usable值，减去了新dict已用的slot数。

58~65行，释放了split table所占空间。

66~77行则释放了旧dict中ma_keys所占据的空间，同时维护dummy的引用数。

4.2 插入元素

1 /* file:Objects/dictobject.c */ 2 static int 3 insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) 4 { 5     PyObject *old_value; 6     PyObject **value_addr; 7     PyDictKeyEntry *ep; 8     assert(key != dummy); 9 10     if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {11         if (insertion_resize(mp) < 0)12             return -1;13     }14 15     ep = mp->ma_keys->dk_lookup(mp, key, hash, &value_addr);16     if (ep == NULL) {17         return -1;18     }19     Py_INCREF(value);20     MAINTAIN_TRACKING(mp, key, value);21     old_value = *value_addr;22     if (old_value != NULL) {23         assert(ep->me_key != NULL && ep->me_key != dummy);24         *value_addr = value;25         Py_DECREF(old_value); /* which **CAN** re-enter */26     }27     else {28         if (ep->me_key == NULL) {29             Py_INCREF(key);30             if (mp->ma_keys->dk_usable <= 0) {31                 /* Need to resize. */32                 if (insertion_resize(mp) < 0) {33                     Py_DECREF(key);34                     Py_DECREF(value);35                     return -1;36                 }37                 ep = find_empty_slot(mp, key, hash, &value_addr);38             }39             mp->ma_keys->dk_usable--;40             assert(mp->ma_keys->dk_usable >= 0);41             ep->me_key = key;42             ep->me_hash = hash;43         }44         else {45             if (ep->me_key == dummy) {46                 Py_INCREF(key);47                 ep->me_key = key;48                 ep->me_hash = hash;49                 Py_DECREF(dummy);50             } else {51                 assert(_PyDict_HasSplitTable(mp));52             }53         }54         mp->ma_used++;55         *value_addr = value;56     }57     assert(ep->me_key != NULL && ep->me_key != dummy);58     assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);59     return 0;60 }

insert操作的原理很简单，通过lookdict函数找到合适的位置，把需要插入的值填充进去并维护相关数值即可。

10~13行，对于不合条件的split-table dict调用resize使之变成combined table。

15~18行则在dict中查找出待插入元素的位置。

22~26行处理了替换元素的情况，减少旧value的引用数。

27~56行则处理了非替换元素的插入。在key不是dummy时，需要先检查dk_usable以确保有效空间足够； key是dummy时，插入元素即可。