详细介绍 Python 字典使用的哈希表

我们在上一篇文章中分析了 CPython 中是如何实现 dict 的。由于涉及内容较多,我可能并没有描述清楚 dict 所用的哈希表的具体结构。

如果你也对此有疑问,不妨来看一下本文对哈希表结构的进一步分析。


【dict 哈希表】

先看一张重新制作的图。

这张图描述的就是 CPython 中 PyDictKeysObject 结构中的成员变量 dk_indices。它的数据类型是 char[],表明它是一块连续分配的内存。

dk_indices 在使用中被分割为两部分。

第一部分是图中的 Slots 数组,也就是我们之前文章中提到的哈希表索引内存块;第二部分是 KeyValues 数组,我们之前称之为哈希表键值对内存块。这两部分都是连续的内存,都可以当做数组来处理,从而能充分利用数组随机访问的特性,提高 dict 的访问效率。


Slots 数组有两个作用:

  1. 根据字典中元素 key 的哈希值为元素提供一个槽位(slot)。这是哈希表最一般的用途。
  2. Slots 中存储的并非元素本身,而是元素在 KeyValues 数组中的索引。由于 Slots 本身就是一个数组,通过 Slots[KeySlot] 就可以直接获取元素在 KeyValues 数组中的位置,效率很高。

图中的 slot 有 3 种取值:-1、-2 和自然数。分别代表着 slot 的三种状态:

  1. 未曾使用(UnUsed)这是每个 slot 的初始状态,表示 slot 从未被 key 命中过,从未存储过任何元素的索引。
  2. 回收备用(Dummy)这类 slot 已存储过元素的索引,但元素已被删除,被标记为可再次使用。从这里也可以看到,执行删除操作时,哈希表并不会真正删除元素。这既能提高内存的使用效率,又可以避免物理删除导致的其他元素访问失效。
  3. 活动的(Active)slot 中存储的是一个有效的元素的索引。

哈希表的 hash 算法和冲突算法都是运行在这个 Slots 数组上的。

计算 slot 的基本方法为:

slot = hash(key) & (dk_size - 1)

当发生 key 冲突时,会采用如下算法在 Slots 中查找下一个合适的 slot:

    const size_t mask = DK_MASK(keys);
    // 计算初始 slot
    size_t i = hash & mask;
    //获取 slot 中的索引值
    Py_ssize_t ix = dictkeys_get_index(keys, i);     
    //循环检查索引值是否有效
    for (size_t perturb = hash; ix >= 0;) {
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask;
        ix = dictkeys_get_index(keys, i);
    }

KeyValues 数组用来存储键值对。键值对是以追加的方式添加到数组的尾部的,添加完成之后,将其位置索引保存在 key 对应的 slot 中。

dict.items()、dict.keys() 和 dict.values() 这三个方法就是直接访问 KeyValues 数组的,因而元素的输出顺序和插入顺序是一致的。

dict_keys(PyDictObject *mp)
{
    PyObject *v;
    Py_ssize_t i, j;
    PyDictKeyEntry *ep;
    Py_ssize_t n, offset;
    PyObject **value_ptr;
  again:
    n = mp->ma_used;
    v = PyList_New(n);
    if (v == NULL)
        return NULL;
    if (n != mp->ma_used) {
        /* Durnit.  The allocations caused the dict to resize.
         * Just start over, this shouldn’t normally happen.
         */
        Py_DECREF(v);
        goto again;
    }
    ep = DK_ENTRIES(mp->ma_keys);
    if (mp->ma_values) {
        value_ptr = mp->ma_values;
        offset = sizeof(PyObject *);
    }
    else {
        value_ptr = &ep[0].me_value;
        offset = sizeof(PyDictKeyEntry);
    }
    for (i = 0, j = 0; j < n; i++) {
        if (*value_ptr != NULL) {
            PyObject *key = ep[i].me_key;
            Py_INCREF(key);
            PyList_SET_ITEM(v, j, key);
            j++;
        }
        value_ptr = (PyObject **)(((char *)value_ptr) + offset);
    }
    assert(j == n);
    return v;
}

【使用这种结构的好处】

首先,使用连续的内存可充分利用数组随机访问的特性,保证了 dict 的访问效率。

其次,Slots 数组只保存元素的索引,每个 slot 只占用少量固定长度的内存,可大大节省内存空间。

我们可以想象,当 dict 比较大时,如果其中只包含少量有效的(Active) slot,此时的 Slots 就是一个稀疏的数组。如果 Slots 中存储的是元素对象,每个元素对象的 size 要远大于一个 int 索引值占用的空间,这个稀疏数组会造成比较严重的内存浪费。

因此,CPython 所采用的这种哈希表内存结构的确是一种高效紧凑的数据存储方式,具有很高的时间和空间效率。


流畅的python


欢迎转载,请注明出处。谢绝搬运,抄袭必究!

欢迎关注本站公众号【python学与思】

python 学与思