起步

python中PyDictObject采用了散列表,平均状况是O(1)复杂度的搜索效率.

散列表是通过一定的函数将需搜索的键值映射为一个整数,将这个整数视为索引去访问某片连续的内存区域. 一般情况下,hash table会申请一块较大的连续内存通过映射函数f(n)得到所对应的索引.

在使用散列表过程中,随着需要存储的数据增多,hash冲突的概率就越高.会直接影响到hash的效率和性能.

在python中采用闭散列法来解决冲突,闭散列法也称为开放定址法.当产生冲突时,python会通过一个二次探测函数f,计算下一个候选索引, 如果索引不可用,就再次用f探测.直到找到一个可用的位置.

之所以叫做闭散列法，就是因为冲突的元素没有开辟额外的存储空间，还是在原先hash表的空间范围之内。

关联容器

假如我们将具有某种关系的两个数组成一组,例如(3, 6), (4, 8),他们具有2倍关系, 组成一组的好处就是找到3就能立马找到6.

因此关联容器常以(key, value)存在.Python中定义这样的关联容器Entry:

[dict-common.h]
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

在PyDictKeyEntry中,me_hash表示me_key的散列值, 保存这个值是为了避免重复计算. 在PyDictObject对象发生变化时, 其中的entry也会在不同的状态间切换.关联容器存在3中状态:

• Unused(未使用):index == DKIX_EMPTY
• Active(活动): index >= 0, me_key != NULL and me_value != NULL
• Dummy(删除状态): index == DKIX_DUMMY 之所以不能直接转成Unused状态是因为这要会导致冲突测链中断

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

关联容器的实现

[dictobject.h]
typedef struct {
    PyObject_HEAD

    // Active元素个数
    Py_ssize_t ma_used;

    // 全局唯一, 值会随着dict的修改而改变
    uint64_t ma_version_tag;

    PyDictKeysObject *ma_keys;

    // 如果ma_values == NULL 表示哈希表是结合的, 如果ma_values != NULL 则表被拆分
    PyObject **ma_values;
} PyDictObject;

PyDictKeysObject是这样定义的:

[dict-common.h]
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;

    // hash表允许容纳元素的个数 必定是2的指数
    Py_ssize_t dk_size;

    // 与hash table有关的函数
    dict_lookup_func dk_lookup;

    // 元素个数 Active + Dummy
    Py_ssize_t dk_usable;

    // 元素个数 Active
    Py_ssize_t dk_nentries;

    union {
        int8_t as_1[8];
        int16_t as_2[4];
        int32_t as_4[2];
    } dk_indices;
};

“PyDictKeyEntry dk_entries [dk_usable];” 数组如下,参阅DK_ENTRIES()宏:

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

从python3.6开始,借鉴 PyPy 字典设计，采用更紧凑的存储结构.内存效率更高, 更多信息可以查看https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html

key可以分布如下:

+---------------+
| dk_refcnt     |
| dk_size       |
| dk_lookup     |
| dk_usable     |
| dk_nentries   |
+---------------+
| dk_indices    |
|               |
+---------------+
| dk_entries    |
|               |
+---------------+

dk_indices 是实际的哈希表。它在条目中保存索引，或KIX_EMPTY（-1）或DKIX_DUMMY（-2）。哈希表能容纳元素的个数 dk_size .dk_entries是一个PyDictKeyEntr的数组。它的大小是USABLE_FRACTION（dk_size）。 可以使用DK_ENTRIES（dk）来获取指向条目的指针。注意：由于负值用于DKIX_EMPTY和DKIX_DUMMY，所以键入 dk_indices条目是有符号整数，int16用于表大小dk_size == 256。

为什么说更省空间呢?

比如需要一个字典d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'},那其结构在旧模式下是:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

而使用新的为:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

indices就是哈希表,改变的只是布局, 哈希表算法将不变.例子中节省了得58%的内存。据说能节省30%~95~的空间(取决表的完整程度). 除了节省空间, 新的布局迭代更快, keys() values() items(),直接在关联容器entries获取, 无需判断['--', '--', '--']空关联容器. 移动或者复制hash表,只需操作indices即可.

请注意，sizeof（index）可以小到单个小字节的字节，大字节的两个字节直到sizeof（Py_ssize_t）为巨大的dict。因此可以看到PyDictKeyObject中的dk_indices是个联合体.为了是更省内存. 作者很抠内存的, 巴不得一个字节当两个字节用.

PyDictObject 对象的创建

python内部通过PyDict_New来创建一个新的dict对象:

[dictobject.h]
PyObject * PyDict_New(void)
{
    PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
    if (keys == NULL)
        return NULL;
    return new_dict(keys, NULL);
}

PyDict_MINSIZE 值为8, 默认情况下, PyDict_New会创建8个entry

static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t es, usable;

    usable = USABLE_FRACTION(size);
    es = 4;

    if (size == PyDict_MINSIZE && numfreekeys > 0) {
        // 使用缓冲池
        dk = keys_free_list[--numfreekeys];
    }
    else {
        dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
                             + es * size
                             + sizeof(PyDictKeyEntry) * usable);
    }
    DK_DEBUG_INCREF dk->dk_refcnt = 1;
    dk->dk_size = size;
    dk->dk_usable = usable;
    dk->dk_lookup = lookdict_unicode_nodummy;
    dk->dk_nentries = 0;
    // hash table 初始化
    memset(&dk->dk_indices.as_1[0], 0xff, es * size);
    memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
    return dk;
}

keys.entries 和 values 用数组按添加顺序存储主键和值引用。实际哈希表由 keys.indices 数组承担，通过计算主键哈希值找到合适位置，然后在此存储主键在 keys.entries 的实际索引。如此，只要通过 indices 获取实际索引后，就可读取主键和值信息。

dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
                             + es * size    // hash索引表
                             + sizeof(PyDictKeyEntry) * usable);    // PyDictKeyEntry 的数组, 申请大小为表size的2/3

也就是说 PyDictKeysObject 中成员 dk_indices 有两个重要的成分, 一个是前半部分的hash table索引. 另一个是后半部分的关联容器数组

元素搜索

无论是字典的设置d["aaa"] = 3 还是获取 a = d["aaa"] 都需要对hash table进行搜索. python位hash表搜索提供了多种函数, 通用的lookdict, 针对字符串类型的lookdict_unicode, 针对数字的 lookdict_index. 但他们的算法是相同的. lookdict 是获取字典

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;    // mask是2的指数-1, 因此相当于取模

    for (;;) {
        Py_ssize_t ix = dk_get_index(dk, i);// dk->indecs[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) { // 同一个引用
                *value_addr = ep->me_value;
                return ix;
            }
            if (ep->me_hash == 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; // 哈希探测函数
    }
    assert(0);          /* NOT REACHED */
    return 0;
}

dk_get_index(dk, i) 简单理解为->dk_indices.as_1[i] 即可, 对于不同规模的hash表, 用as_1或as_2有所不同而已. 对于lookdict来说, 永远不会返回NULL, 如果搜索不到待查找的key, 同样会返回一个空的关联容器的索引.

在python的字典中,"相同"这个概念包含了两个含义:

1. 引用相同
2. 值相同 在lookdict中ep->me_key == key 就意味着他们的值相同, 在其判断体内加printf("key is same\n"); 可以看到:

>>> a = {}
>>> a[2] = "python"
>>> a[2]
key is same
'python'
>>> a[999] = "php"
>>> a[999]
'php'
>>>

小整数对象是共享的, 因此他们key都是指向同一个地址. 大整数对象并不是共享, 但是999明明在key中是存在的,因此"值相同"规则就有存在的意义.

总结搜索过程入下:

1. 根据PyObject *key 的哈希值获得entry索引, 这是冲突探测链上第一个entry索引.
2. 两种情况下,搜索结束:
   • entry处于Unuse状态,表示冲突弹窗搜索结束, 搜索失败
   • ep->me_key == key 表示entry的key与待搜索key是同一个PyObject对象, 搜索成功
3. 若当前的entry处于Dummy态, 设置为freeslot
4. 检查Active态中的entry中的key是否与待查找的key"值相同", 若找到, 搜索成功. 若不匹配, 则沿着探测链查找.探测链检测到DUMMY状态是,设置freeslot

当entry中的key与待查找的key不匹配时, 拦着探测链顺藤摸瓜.

探测链上的过程与前面的过程基本一致, 总之,lookdict 如果搜索成功, 返回一定是有效的entry索引.如果搜索失败,则返回一个Unused状态的entry索引.因为dummy状态的entry实际也是一个空闲的entry, 当遍历到Dummy状态的entry,便会设置freeslot,freeslot是下一个被inserted的索引.

其他搜索策略都差不多. 哦对了, 默认的搜索策略是 lookdict_unicode_nodummy 介绍说比lookdict_unicode快,不清楚为什么搜索出来的entry不含dummy的.

python内部也大量使用的PyDictObject对象, 如维护一个名字空间的变量名与值的关系, 函数传递参数时参数名与参数值的关系.

hash冲突时采用 i = ((i << 2) + i + perturb + 1) & mask; 即 i = (i * 5 + i) % dk_size; 因为dk_size是2的指数, 所以这个探测正好能遍历所有元素.

插入

关于dict的操作基本都是建立在搜索的基础上的.

static int insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyObject *old_value;
    PyDictKeyEntry *ep;

    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 = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
    if (ix == DKIX_ERROR)
        goto Fail;

    // 检查...

    // 检查共享key, 必要时进行hash表扩容
    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];
        dk_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++;  // 使用数+1
        mp->ma_version_tag = DICT_NEXT_VERSION();// 版本号+1
        mp->ma_keys->dk_usable--;       // 可用数-1
        mp->ma_keys->dk_nentries++;     // 关联容器数量+1
        assert(mp->ma_keys->dk_usable >= 0);
        assert(_PyDict_CheckConsistency(mp));
        return 0;
    }
    // ...
    DK_ENTRIES(mp->ma_keys)[ix].me_value = value;

    mp->ma_version_tag = DICT_NEXT_VERSION();// 版本号+1
    Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
    assert(_PyDict_CheckConsistency(mp));
    Py_DECREF(key);
    return 0;

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

在搜索的lookup函数中, 返回的关联容器状态有两个结果:搜索成功是,返回的是Active的entry,这种情况下直接替换即可*value_addr = value;. 搜索不成功是, 返回的是Unuse或Dummy状态的关联容器,需要完整设置me_key,me_hash,me_value. python代码中 d["aaa"] = 4 其实是调用 PyDict_SetItem 的:

int PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    PyDictObject *mp;
    Py_hash_t hash;

    mp = (PyDictObject *)op;
    if (!PyUnicode_CheckExact(key) ||
        (hash = ((PyASCIIObject *) key)->hash) == -1)
    {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }

    /* insertdict() handles any resizing that might be necessary */
    return insertdict(mp, key, hash, value);
}

如果key只是替换现有的值,也就是当搜索成功时. 是不改变hash table大小的. 这就意味着 PyDict_Next() 循环使用字典是安全的了.

insertdict中会重新resize哈希表:

// 增长率
#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))

static int insertion_resize(PyDictObject *mp)
{
    return dictresize(mp, GROWTH_RATE(mp));
}

改变table的大小交到了dictresize身上.

static int dictresize(PyDictObject *mp, Py_ssize_t minsize)
{
    Py_ssize_t i, newsize;
    PyDictKeysObject *oldkeys;
    PyObject **oldvalues;
    PyDictKeyEntry *ep0;

    /* Find the smallest table size > minused. */
    for (newsize = PyDict_MINSIZE;
         newsize < minsize && newsize > 0;
         newsize <<= 1)
        ;

    oldkeys = mp->ma_keys;
    oldvalues = mp->ma_values;
    // 申请新空间
    mp->ma_keys = new_keys_object(newsize);

    if (oldkeys->dk_lookup == lookdict)
        mp->ma_keys->dk_lookup = lookdict;
    mp->ma_values = NULL;
    ep0 = DK_ENTRIES(oldkeys);
    /* Main loop below assumes we can transfer refcount to new keys
     * and that value is stored in me_value.
     * Increment ref-counts and copy values here to compensate
     * This (resizing a split table) should be relatively rare */
    if (oldvalues != NULL) {
        // 搬迁list
        for (i = 0; i < oldkeys->dk_nentries; i++) {
            if (oldvalues[i] != NULL) {
                Py_INCREF(ep0[i].me_key);
                ep0[i].me_value = oldvalues[i];
            }
        }
    }
    // 旧hash表到新hash表搬迁, hash值不会重新计算, 但关联容器索引会重新计算
    for (i = 0; i < oldkeys->dk_nentries; i++) {
        PyDictKeyEntry *ep = &ep0[i];
        if (ep->me_value != NULL) {
            insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
        }
    }
    ...
    return 0;
}

resize将hash表容量扩大两倍, 然后搬迁数据, 表hash索引不需要重新计算.