关联容器关注的主要内容是键的搜索效率

因为Python自身大量的使用了PyDictObject对象，所以对搜索的效率极其苛刻，没有采用平衡二叉树（时间复杂度为O(log₂N)），采用的是hashTable散列表（最优情况下时间复杂对为O(1)）

0x01 散列表简述

散列函数（hash function）

将一个数字A通过某种算法F得到一个数字B，我们称为散列。

实现算法F的函数就叫做散列函数，例如：f(n)=n%10，就是一个散列函数，将传入的数值映射到0-9上。

散列值（hash value）

上面提到的数值B就是散列值

散列冲突

装载率：装载率是指散列表中已使用空间和总空间的比值。研究表明，当装载率大于2/3的时候，散列冲突的概率就会大大增加（这不是废话吗？）

接上面的例子，12和22经过散列函数以后都映射到散列值2上面了，这个就产生冲突了。

更具体的一个例子，比如我使用键key1和key2去字典D中搜索对应的值，结果这两个key散列到同一个散列值上了，这显然就产生了冲突。

有问题就会有解决方案，下面介绍几个解决散列冲突的方法。

• 开链法
  • 当发生散列冲突时，将冲突的值在相同的散列值后面增加一个链表，来链接冲突的对象
• 开放定址法
  • 当发生散列冲突时，再使用一个二次探测函数f，再进行一次计算得到一个散列值，如果这个值上还是冲突，再使用一次二次探测函数f，直到找到不冲突的散列值（Python使用的就是这种方法）

0x02 PyDictObject

先说说关联容器的每一对键值对的结构：

typedef struct {
    /* Cached hash code of me_key.  Note that hash codes are C longs.
     * We have to use Py_ssize_t instead because dict_popitem() abuses
     * me_hash to hold a search finger.
     */
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

• PyDictObject对象中的键值对由PyDictEntry对象表示
• PyDictEntry中的me_value属性是PyObject对象，所以这就说明了PyDictObject对象可以存储所有Python中的对象
• me_hash存储的是me_key的散列值，这里的作用是用作缓存，避免每次查询都要重新计算散列值
• PyDictObject对象发生变化的过程中，entry会在三种状态中转换：Unused、Active、Dummy。刚刚初始化的entry都是Unused状态，正在使用的都是Active状态，被删除的entry都是Dummy状态（为了防止冲突探测链锻炼，实现的一种伪删除）
• entry状态转换图

再来说说真正的PyDictObject对象的结构

#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */

    /* The table contains ma_mask + 1 slots, and that's a power of 2.
     * We store the mask instead of the size because the mask is more
     * frequently needed.
     */
    Py_ssize_t ma_mask;

    /* ma_table points to ma_smalltable for small tables, else to
     * additional malloc'ed memory.  ma_table is never NULL!  This rule
     * saves repeated runtime null-tests in the workhorse getitem and
     * setitem calls.
     */
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

• ma_fill是Active和Dummy的entry数量
• ma_used是Active的entry数量
• ma_mask是所有entry的数量
• ma_smalltable为PyDictEntry的数组，数组大小默认为PyDict_MINSIZE（8），即在实例化一个PyDictObject对象的时候，至少有PyDict_MINSIZE个entry同时被创建
• ma_table是散列表的地址，是PyDictObject对象的关键。它指向一片作为PyDictEntry集合的内存开始位置。当PyDictObject是一个比较小的字典的时候，ma_table指向ma_smalltable的位置；否则就会申请额外的内部才能空间，将ma_table指向这片空间
• ma_table的两种状态
• ma_lookup是搜索时使用的函数地址

0x03 创建PyDictObject对象

#define INIT_NONZERO_SET_SLOTS(so) do {                         \
    (so)->table = (so)->smalltable;                             \
    (so)->mask = PySet_MINSIZE - 1;                             \
    (so)->hash = -1;                                            \
    } while(0)

#define EMPTY_TO_MINSIZE(so) do {                               \
    memset((so)->smalltable, 0, sizeof((so)->smalltable));      \
    (so)->used = (so)->fill = 0;                                \
    INIT_NONZERO_SET_SLOTS(so);                                 \
    } while(0)

PyObject *
PyDict_New(void)
{
    register PyDictObject *mp;
    if (dummy == NULL) { /* Auto-initialize dummy */
        dummy = PyString_FromString("<dummy key>");
        if (dummy == NULL)
            return NULL;
#ifdef SHOW_CONVERSION_COUNTS
        Py_AtExit(show_counts);
#endif
#ifdef SHOW_ALLOC_COUNT
        Py_AtExit(show_alloc);
#endif
#ifdef SHOW_TRACK_COUNT
        Py_AtExit(show_track);
#endif
    }
    if (numfree) {
        mp = free_list[--numfree];
        assert (mp != NULL);
        assert (Py_TYPE(mp) == &PyDict_Type);
        _Py_NewReference((PyObject *)mp);
        if (mp->ma_fill) {
            EMPTY_TO_MINSIZE(mp);
        } else {
            /* At least set ma_table and ma_mask; these are wrong
               if an empty but presized dict is added to freelist */
            INIT_NONZERO_DICT_SLOTS(mp);
        }
        assert (mp->ma_used == 0);
        assert (mp->ma_table == mp->ma_smalltable);
        assert (mp->ma_mask == PyDict_MINSIZE - 1);
#ifdef SHOW_ALLOC_COUNT
        count_reuse++;
#endif
    } else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL)
            return NULL;
        EMPTY_TO_MINSIZE(mp);
#ifdef SHOW_ALLOC_COUNT
        count_alloc++;
#endif
    }
    mp->ma_lookup = lookdict_string;
#ifdef SHOW_TRACK_COUNT
    count_untracked++;
#endif
#ifdef SHOW_CONVERSION_COUNTS
    ++created;
#endif
    return (PyObject *)mp;
}

• 第一次调用PyDict_New函数时，会先创建之前提到的dummy对象，其实他就是一个PyStringObject的对象，它仅仅作为一个标志，标志该entry被使用过，防止探测序列断裂
• 从numfree可以看出PyDictObject对象也使用了缓冲池的概念，后面我们再详细讨论。
• 如果缓冲池不可用，就需要创建一个PyDictObject对象了，通过两个宏来完成创建工作（初始化变量的值，然后将ma_table指向ma_smalltale）。

0x04 PyDictObject对象的元素搜索

Python为PyDictObject对象提供了两种搜索策略：lookdict和lockdict_string。

两种策略实际上使用的是相同的算法。lookdict_string只是lookdict的一种针对key为PyStringObject对象的特殊实现，因为以PyStringObject对象作为entry的key在Python中的使用非常广泛，所以为了效率的考虑，提供了专门的接口。

先来看看lookdict的实现

static PyDictEntry *
lookdict(PyDictObject *mp, PyObject *key, register long hash)
{
    register size_t i;
    register size_t perturb;
    register PyDictEntry *freeslot;
    register size_t mask = (size_t)mp->ma_mask;
    PyDictEntry *ep0 = mp->ma_table;
    register PyDictEntry *ep;
    register int cmp;
    PyObject *startkey;

    i = (size_t)hash & mask;
    ep = &ep0[i];
    if (ep->me_key == NULL || ep->me_key == key)
        return ep;

    if (ep->me_key == dummy)
        freeslot = ep;
    else {
        if (ep->me_hash == hash) {
            startkey = ep->me_key;
            Py_INCREF(startkey);
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
            Py_DECREF(startkey);
            if (cmp < 0)
                return NULL;
            if (ep0 == mp->ma_table && ep->me_key == startkey) {
                if (cmp > 0)
                    return ep;
            }
            else {
                /* The compare did major nasty stuff to the
                 * dict:  start over.
                 * XXX A clever adversary could prevent this
                 * XXX from terminating.
                 */
                return lookdict(mp, key, hash);
            }
        }
        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)
            return freeslot == NULL ? ep : freeslot;
        if (ep->me_key == key)
            return ep;
        if (ep->me_hash == hash && ep->me_key != dummy) {
            startkey = ep->me_key;
            Py_INCREF(startkey);
            cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
            Py_DECREF(startkey);
            if (cmp < 0)
                return NULL;
            if (ep0 == mp->ma_table && ep->me_key == startkey) {
                if (cmp > 0)
                    return ep;
            }
            else {
                /* The compare did major nasty stuff to the
                 * dict:  start over.
                 * XXX A clever adversary could prevent this
                 * XXX from terminating.
                 */
                return lookdict(mp, key, hash);
            }
        }
        else if (ep->me_key == dummy && freeslot == NULL)
            freeslot = ep;
    }
    assert(0);          /* NOT REACHED */
    return 0;
}

• 先找到冲突探测链上的第一个entry，通过hash&mask的操作，使hash落到散列表的某个位置上，这个位置就是索引，然后根据索引直接拿到entry对象的地址
• freeslot是一个重要的变量，它存储了在搜索过程中遇到的第一个Dummy态的entry。
• lookdict和lookdict_string在没有搜索成功的时候，不会返回NULL，而是会返回一个可以使用的entry，优先返回Dummy态的entry，否则返回Unused态的entry（因为搜索成功的标志是me_value!=NULL，它俩都能标志着不成功，所以不影响判断成功与否，而且还能立马得到一个可用的entry）。
• PyDictObject中的key相同有两个层面的含义：引用相同和值相同。
  • 引用相同指的是两个符号引用的是同一块内存，代码通过ep->me_key == key来检验
  • 值相同是指虽然两个对象不相同，但是对象里面存储的值是相同的。我们不能因为key不是同一个对象就否认值相同的两个对象不是同一个key了，所以代码通过PyObject_RichCompareBool(startkey, key, Py_EQ)来检验，Py_EQ表示判断是否是相等的关系。
• 搜索过程中首先会找Active态的entry，判断值是否相同，若成立，则搜索成功；否则还需要使用二次探测函数再查找冲突链上的下一个entry。
• 接下来的判断流程和第一个entry的差不多。

接下来看看默认搜索策略lookdict_string的实现

static PyDictEntry *
lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
{
    register size_t i;
    register size_t perturb;
    register PyDictEntry *freeslot;
    register size_t mask = (size_t)mp->ma_mask;
    PyDictEntry *ep0 = mp->ma_table;
    register PyDictEntry *ep;

    /* Make sure this function doesn't have to handle non-string keys,
       including subclasses of str; e.g., one reason to subclass
       strings is to override __eq__, and for speed we don't cater to
       that here. */
    if (!PyString_CheckExact(key)) {
#ifdef SHOW_CONVERSION_COUNTS
        ++converted;
#endif
        mp->ma_lookup = lookdict;
        return lookdict(mp, key, hash);
    }
    i = hash & mask;
    ep = &ep0[i];
    if (ep->me_key == NULL || ep->me_key == key)
        return ep;
    if (ep->me_key == dummy)
        freeslot = ep;
    else {
        if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
            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)
            return freeslot == NULL ? ep : freeslot;
        if (ep->me_key == key
            || (ep->me_hash == hash
            && ep->me_key != dummy
            && _PyString_Eq(ep->me_key, key)))
            return ep;
        if (ep->me_key == dummy && freeslot == NULL)
            freeslot = ep;
    }
    assert(0);          /* NOT REACHED */
    return 0;
}

• 使用这个搜索策略时有一个假设：假设需要搜索的key是PyStringObject对象。代码开始处会通过PyString_CheckExact函数check一下key是不是PyStringObject对象。需要注意的是，这里只是对需要搜索的key就行假设，没有对参与搜索的key就行假设。
• 比较值相等的时候，使用更加快捷的_PyString_Eq函数而不是通用的比较函数PyObject_RichCompareBool。等等一些列因素，导致lookdict_string的效率高一些。
• 为什么仅仅对PyStringObject类型的key实现了优化版本？
  • 因为Python自身大量使用了PyDictObject对象，这些对象的key都是PyStringObject对象。所以它对Python整体的运行效率都有着重要的影响。

0x05 元素的插入与删除

插入

static int
insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)
{
    register PyDictEntry *ep;

    assert(mp->ma_lookup != NULL);
    ep = mp->ma_lookup(mp, key, hash);
    if (ep == NULL) {
        Py_DECREF(key);
        Py_DECREF(value);
        return -1;
    }
    return insertdict_by_entry(mp, key, hash, ep, value);
}

static int
insertdict_by_entry(register PyDictObject *mp, PyObject *key, long hash,
                    PyDictEntry *ep, PyObject *value)
{
    PyObject *old_value;

    MAINTAIN_TRACKING(mp, key, value);
    if (ep->me_value != NULL) {
        old_value = ep->me_value;
        ep->me_value = value;
        Py_DECREF(old_value); /* which **CAN** re-enter */
        Py_DECREF(key);
    }
    else {
        if (ep->me_key == NULL)
            mp->ma_fill++;
        else {
            assert(ep->me_key == dummy);
            Py_DECREF(dummy);
        }
        ep->me_key = key;
        ep->me_hash = (Py_ssize_t)hash;
        ep->me_value = value;
        mp->ma_used++;
    }
    return 0;
}

• 插入也是依赖于查找的，先根据需要插入的key在PyDictObject对象中查找是否已存在该entry。如果存在就更新em_value就可以，否则需要更新em_key、em_hash、em_value。

int
PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
{
    register long hash;

    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    if (PyString_CheckExact(key)) {
        hash = ((PyStringObject *)key)->ob_shash;
        if (hash == -1)
            hash = PyObject_Hash(key);
    }
    else {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }
    return dict_set_item_by_hash_or_entry(op, key, hash, NULL, value);
}
static int
dict_set_item_by_hash_or_entry(register PyObject *op, PyObject *key,
                               long hash, PyDictEntry *ep, PyObject *value)
{
    register PyDictObject *mp;
    register Py_ssize_t n_used;

    mp = (PyDictObject *)op;
    assert(mp->ma_fill <= mp->ma_mask);  /* at least one empty slot */
    n_used = mp->ma_used;
    Py_INCREF(value);
    Py_INCREF(key);
    if (ep == NULL) {
        if (insertdict(mp, key, hash, value) != 0)
            return -1;
    }
    else {
        if (insertdict_by_entry(mp, key, hash, ep, value) != 0)
            return -1;
    }
    /* If we added a key, we can safely resize.  Otherwise just return!
     * If fill >= 2/3 size, adjust size.  Normally, this doubles or
     * quaduples the size, but it's also possible for the dict to shrink
     * (if ma_fill is much larger than ma_used, meaning a lot of dict
     * keys have been * deleted).
     *
     * Quadrupling the size improves average dictionary sparseness
     * (reducing collisions) at the cost of some memory and iteration
     * speed (which loops over every possible entry).  It also halves
     * the number of expensive resize operations in a growing dictionary.
     *
     * Very large dictionaries (over 50K items) use doubling instead.
     * This may help applications with severe memory constraints.
     */
    if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
        return 0;
    return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
}

• Python代码中设置字段元素时，直接调用的是PyDict_SetItem接口，PyDict_SetItem内部调用的是insertdict函数
• PyDict_SetItem在设置完元素后，会检查是否需要改变PyDictObject对象内部ma_table所维护的内存区域的大小。
  • 什么时候需要改变ma_table的大小呢？前面我们说过装载率大于2/3的时候，散列冲突的概率会非常大。所以装载率是否大于2/3是判断是否需要改变ma_table大小的一个准则
  • 还有一个准则是：在insertdict过程中，是否使用了一个处于Unused态或Dummy态的entry
  • 所以，当使用了一个处于Unused态或Dummy态的entry并且装载率大于2/3的时候，才会调整ma_table的大小。代码为：mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2)
• 然而，改变ma_table的大小，并不一定是增加，也可能是减小ma_table的大小。
• 新ma_table的大小为(mp->ma_used > 50000 ? 2 : 4) * mp->ma_used，当处于Active态的entry大于5000的时候，新ma_table的大小是现在处于Active态的entry数量的2倍，否则是4倍。

static int
dictresize(PyDictObject *mp, Py_ssize_t minused)
{
    Py_ssize_t newsize;
    PyDictEntry *oldtable, *newtable, *ep;
    Py_ssize_t i;
    int is_oldtable_malloced;
    PyDictEntry small_copy[PyDict_MINSIZE];

    assert(minused >= 0);

    /* Find the smallest table size > minused. */
    for (newsize = PyDict_MINSIZE;
         newsize <= minused && newsize > 0;
         newsize <<= 1)
        ;
    if (newsize <= 0) {
        PyErr_NoMemory();
        return -1;
    }

    /* Get space for a new table. */
    oldtable = mp->ma_table;
    assert(oldtable != NULL);
    is_oldtable_malloced = oldtable != mp->ma_smalltable;

    if (newsize == PyDict_MINSIZE) {
        /* A large table is shrinking, or we can't get any smaller. */
        newtable = mp->ma_smalltable;
        if (newtable == oldtable) {
            if (mp->ma_fill == mp->ma_used) {
                /* No dummies, so no point doing anything. */
                return 0;
            }
            /* We're not going to resize it, but rebuild the
               table anyway to purge old dummy entries.
               Subtle:  This is *necessary* if fill==size,
               as lookdict needs at least one virgin slot to
               terminate failing searches.  If fill < size, it's
               merely desirable, as dummies slow searches. */
            assert(mp->ma_fill > mp->ma_used);
            memcpy(small_copy, oldtable, sizeof(small_copy));
            oldtable = small_copy;
        }
    }
    else {
        newtable = PyMem_NEW(PyDictEntry, newsize);
        if (newtable == NULL) {
            PyErr_NoMemory();
            return -1;
        }
    }

    /* Make the dict empty, using the new table. */
    assert(newtable != oldtable);
    mp->ma_table = newtable;
    mp->ma_mask = newsize - 1;
    memset(newtable, 0, sizeof(PyDictEntry) * newsize);
    mp->ma_used = 0;
    i = mp->ma_fill;
    mp->ma_fill = 0;

    /* Copy the data over; this is refcount-neutral for active entries;
       dummy entries aren't copied over, of course */
    for (ep = oldtable; i > 0; ep++) {
        if (ep->me_value != NULL) {             /* active entry */
            --i;
            insertdict_clean(mp, ep->me_key, (long)ep->me_hash,
                             ep->me_value);
        }
        else if (ep->me_key != NULL) {          /* dummy entry */
            --i;
            assert(ep->me_key == dummy);
            Py_DECREF(ep->me_key);
        }
        /* else key == value == NULL:  nothing to do */
    }

    if (is_oldtable_malloced)
        PyMem_DEL(oldtable);
    return 0;
}

• 首先会确认table的大小，如果新的大小为8，则不需要在堆上申请额外的内存大小，直接使用ma_smalltable，否则需要在堆上申请额外的内粗怒
• 对PyDictObject对象内部变量进行调整，对于之前table中的非Unused态的entry进行处理。Dummy态的entry直接丢弃；Active态的需要调用insertdict_clean函数，将entry插入到新table中。
• 释放之前table的内存，防止内存泄漏。

删除

int
PyDict_DelItem(PyObject *op, PyObject *key)
{
    register PyDictObject *mp;
    register long hash;
    register PyDictEntry *ep;

    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    if (!PyString_CheckExact(key) ||
        (hash = ((PyStringObject *) key)->ob_shash) == -1) {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }
    mp = (PyDictObject *)op;
    ep = (mp->ma_lookup)(mp, key, hash);
    if (ep == NULL)
        return -1;
    if (ep->me_value == NULL) {
        set_key_error(key);
        return -1;
    }

    return delitem_common(mp, ep);
}

• 先计算hash值，然后搜索相应的entry，最后删除entry中维护的元素，这里使用伪删除，将entry的状态从Active变成Dummy。

0x06 PyDictObject对象缓冲池

#define PyDict_MAXFREELIST 80
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;

static void
dict_dealloc(register PyDictObject *mp)
{
    register PyDictEntry *ep;
    Py_ssize_t fill = mp->ma_fill;
    /* bpo-31095: UnTrack is needed before calling any callbacks */
    PyObject_GC_UnTrack(mp);
    Py_TRASHCAN_SAFE_BEGIN(mp)
    for (ep = mp->ma_table; fill > 0; ep++) {
        if (ep->me_key) {
            --fill;
            Py_DECREF(ep->me_key);
            Py_XDECREF(ep->me_value);
        }
    }
    if (mp->ma_table != mp->ma_smalltable)
        PyMem_DEL(mp->ma_table);
    if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
        free_list[numfree++] = mp;
    else
        Py_TYPE(mp)->tp_free((PyObject *)mp);
    Py_TRASHCAN_SAFE_END(mp)
}

• PyDictObject对象的缓冲机制和PyListObject对象是一模一样的
• 开始并没有PyDictObject对象被缓存，只有当对象被销毁时，不进行真正的销毁，而是将PyDictObject对象缓存到free_list数组中，数组大小和PyListObject对象中的一样，都是80。
• 而且和PyListObject对象一样，PyDictObject对象也只缓存PyDictObject对象本身，如果ma_table指向的是额外的内存空间，这些空间是会被释放给系统。

欢迎关注微信公众号（coder0x00）或扫描下方二维码关注，我们将持续搜寻程序员必备基础技能包提供给大家。