字典的 key 是怎么映射成索引的,索引冲突了又该怎么办?

简介: 字典的 key 是怎么映射成索引的,索引冲突了又该怎么办?


楔子


两个对象的哈希值相等,那么映射出的索引肯定相同。而如果哈希值不相等,映射出的索引也有可能相同,因为与哈希值空间相比,哈希表的槽位是非常有限的。如果不同的对象在经过映射之后,生成的索引相同,或者说它们被映射到了同一个槽,那么便发生了索引冲突


解决索引冲突的常用方法有两种:分离链接法开放寻址法

分离链接法比较简单,如果有多个键值对映射到同一槽位,那么就用链表将它们串起来。然后是开放寻址法,这也是 Python 使用的方法,我们详细介绍一下。



开放寻址法


首先将 key 映射成索引,如果发现该索引对应的哈希槽被占了,那么就尝试另一个。


925321d1a8a39c2b4401af26e6f3d611.png

new_key 被映射到了索引为 5 的槽,但是该槽已经存储了键值对数组的索引,即该槽被占了。如果是分离链接法,那么会使用链表将两个 entry 串起来,但开放寻址法则是选择一个新的槽,也就是重新找个坑。


那么问题来了,新的槽要怎么找呢?一般来说,会在首槽的基础上增加一个偏移量,得到新的槽,如果还冲突,那么继续增加偏移量,直到找到一个可用的槽。总的来说就是一个不断探测的过程,每一次探测都会尝试增加偏移量。


所以新的问题又产生了,每次增加的偏移量是多少呢?其实这个问题取决于具体实现,如果偏移量是线性增加的,我们称之为线性探测;如果偏移量是平方增加的,我们称之为平方探测


但不管是线性探测,还是平方探测,其实都不够好。因为偏移量始终是以一种固定的模式增加,这就导致映射到同一槽位的两个 key 的探测序列是相同的。


f7412f0394ae4ef6b2b7fdc039497afa.png

比如这里的 key1 和 key2,它们的哈希值不同,但都映射到了索引为 2 的槽,这是完全正常的,因为哈希表的槽位有限。而由于偏移量的增加方式是固定的,比如这里每次都增加 2,再加上首槽相同,因此它们的探测序列也相同,显然这会导致后续出现多次冲突。


所以 Python 对此进行了优化,探测函数在发现索引冲突时,不会简单地增加一个偏移量,而是会参考对象的哈希值,计算下一个候选位置,这就大大降低了冲突的可能性。

Python 的这种做法被称为迭代探测,当然迭代探测也属于开放寻址法的一种。所以当出现索引冲突时,Python 并不是简简单单地加上一个偏移量,而是使用专门设计的探测函数进行二次探查,也就是之前说的改变规则、重新映射,然后在函数内部会参考对象的哈希值来计算出一个新的索引。


2d5ef4c4e411335b0bef18f4512c487c.png

在 dictobject.c 文件开头有着大量的注释,对字典进行了全局性的概括,当然具体细节我们都会详细说明。



探测函数


当存储一个键值对时,要将 key 映射成一个索引,这个索引就是哈希索引数组的索引。那么具体是怎么映射的呢?这里先来回顾一下字典的结构。


2fd038ce61f67d58f2d6d4daed65f4de.jpg

字典有两种实现方式,一种是分离表,另一种是结合表。对于分离表而言,键由 ma_keys 维护,值由 ma_values 维护,两者分开存储。对于结合表而言,键和值均由 ma_keys 维护,即键值对会一起存储在 PyDictKeysObject 结构体中,至于 ma_values 则为 NULL。

关于字典为什么要有两种结构,上一篇文章解释地很详细了。一开始只有结合表,而引入分离表是为了节省内存,通过 key 和 value 分开存储,可以让多组 value 共享同一组 key。比如实例对象的属性字典,采用分离表再合适不过了。

然后注意结构体里面的 dk_kind 字段,它表示键的种类,有以下三种选择。

typedef enum {
    DICT_KEYS_GENERAL = 0,
    DICT_KEYS_UNICODE = 1,
    DICT_KEYS_SPLIT = 2
} DictKeysKind;

含义分别如下:

  • DICT_KEYS_UNICODE:字典使用结合表实现,并且所有的键全部是字符串,此时键值对的类型为 PyDictUnicodeEntry 结构体,大小为 16 字节。
  • DICT_KEYS_GENERAL:字典使用结合表实现,并且键不全是字符串,此时键值对的类型为 PyDictKeyEntry 结构体,大小为 24 字节。
  • DICT_KEYS_SPLIT:字典使用分离表实现,此处不做讨论,我们自己创建的字典使用的都是结合表。注意,如果是分离表,那么所有的键也必须都是字符串,因为对象的属性字典里面的属性名都是字符串。

我们来验证一下:

from ctypes import *
class PyDictKeysObject(Structure):
    _fields_ = [("dk_refcnt", c_ssize_t),
                ("dk_log2_size", c_uint8),
                ("dk_log2_index_bytes", c_uint8),
                ("dk_kind", c_uint8),
                ("dk_version", c_uint32),
                ("dk_usable", c_ssize_t),
                ("dk_nentries", c_ssize_t),
                ("dk_indices", c_char * 8)]
class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]
class PyDictObject(PyObject):
    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", POINTER(PyDictKeysObject)),
                ("ma_values", c_void_p)]
DICT_KEYS_GENERAL = 0
DICT_KEYS_UNICODE = 1
DICT_KEYS_SPLIT = 2
# 创建一个字典,里面只包含字符串
d = {"a": 1, "b": 2, "c": 3}
obj = PyDictObject.from_address(id(d))
# 此时 dk_kind 为 DICT_KEYS_UNICODE
print(
    obj.ma_keys.contents.dk_kind == DICT_KEYS_UNICODE
)  # True
# 往字典里面插入一个键值对,并且键不是字符串
d[1] = None
# 此时字典的结构发生改变,因为不再满足所有的键都是字符串
# dk_kind 会从 DICT_KEYS_UNICODE 变成 DICT_KEYS_GENERAL
# 键值对也会从 PyDictUnicodeEntry 实例变成 PyDictKeyEntry 实例
print(
    obj.ma_keys.contents.dk_kind == DICT_KEYS_GENERAL
)  # True
# 那么问题来了,如果我将 key = 1 这个键值对删掉
# dk 会从 DICT_KEYS_GENERAL 变成 DICT_KEYS_UNICODE 吗
d.pop(1)
# 很明显,答案是不会变的
print(
    obj.ma_keys.contents.dk_kind == DICT_KEYS_GENERAL
)  # True
# 不管 dk_kind 是 DICT_KEYS_GENERAL 还是 DICT_KEYS_UNICODE
# 都表示字典使用的是结合表,它的特点是每组 value 独占一组 key
# 但对于实例对象的属性字典来说,这么做就有点浪费内存了
# 比如某个类有 100 个实例,因为是同一个类的实例,所以它们的属性都是相同的
# 这也意味着属性字典里的 key 是相同的,那么这 100 个属性字典完全可以共享一组 key
class A:
    pass
a = A()
obj = PyDictObject.from_address(id(a.__dict__))
# 对象的属性字典,采用分离表实现
# 分离表同样要求,所有的 key 都必须是字符串
print(
    obj.ma_keys.contents.dk_kind == DICT_KEYS_SPLIT
)  # True
# 插入一个键值对,并且 key 不是字符串
a.__dict__[1] = None
# 字典的 PyDictKeysObject 发生重构,分离表会变成结合表
# dk_kind 从 DICT_KEYS_SPLIT 变成 DICT_KEYS_GENERAL
print(
    obj.ma_keys.contents.dk_kind == DICT_KEYS_GENERAL
)  # True

打印结果表明我们的分析没有问题,相信你已经明白了分离表和结合表的区别,以及 dk_kind 字段的作用。下面我们来看看 key 是怎么映射成索引的,这个过程由 _Py_dict_lookup 函数负责。

// Objects/dictobject.c
Py_ssize_t
_Py_dict_lookup(PyDictObject *mp, PyObject *key, 
                Py_hash_t hash, PyObject **value_addr)
{    
    // 将 key 映射成索引,这个索引就是哈希索引数组的索引
    /* 参数 mp:指向字典的指针
     * 参数 key:指向键的指针
     * 参数 hash:键的哈希值
     * 参数 value_addr:值的二级指针
     */
    // mp->ma_keys
    PyDictKeysObject *dk;
    // mp->ma_keys->dk_kind
    DictKeysKind kind;
    // 哈希索引数组中存储的键值对数组的索引
    Py_ssize_t ix;
start:
    dk = mp->ma_keys;
    kind = dk->dk_kind;
    // 如果 kind 不等于 DICT_KEYS_GENERAL
    // 说明要么是 DICT_KEYS_UNICODE,要么是 DICT_KEYS_SPLIT
    // 但不管哪一种,字典里面的 key 肯定都是字符串
    if (kind != DICT_KEYS_GENERAL) {
        // 如果 key 是字符串,那么调用 unicodekeys_lookup_unicode
        if (PyUnicode_CheckExact(key)) {
            ix = unicodekeys_lookup_unicode(dk, key, hash);
        }
        // 但如果在迭代的时候,key 的类型发生改变
        // 那么调用 unicodekeys_lookup_generic
        else {
            ix = unicodekeys_lookup_generic(mp, dk, key, hash);
            if (ix == DKIX_KEY_CHANGED) {
                goto start;
            }
        }
        // 如果 ix >= 0,说明找到了合法的键值对数组的索引
        // 但这里不光要返回索引,还要把 value 也返回,该怎么做呢?
        // 因为 C 是单返回值语言,所以外部在调用函数时一般会传一个指针
        // 然后在函数内部对指针指向的值进行修改,这是 C 的常用操作
        // 所以外部会定义一个 PyObject *value,然后将 &value 传给参数 value_addr
        // 因此 value_addr 是一个二级指针,通过 *value_addr 修改外部的 value
        if (ix >= 0) {
            // 如果 kind 是 DICT_KEYS_SPLIT,说明 value 存在 ma_values 里面
            if (kind == DICT_KEYS_SPLIT) {
                *value_addr = mp->ma_values->values[ix];
            }
            // 否则说明 kind 是 DICT_KEYS_UNICODE
            // key 和 value 会整体作为一个 entry 存在 dk_entries 里面
            else {
                *value_addr = DK_UNICODE_ENTRIES(dk)[ix].me_value;
            }
        }
        // 否则说明 ix < 0,即哈希槽尚未存储某个合法的键值对数组的索引
        else {
            *value_addr = NULL;
        }
    }
    // 如果执行到这里,说明 kind 为 DICT_KEYS_GENERAL
    // 此时通过 dictkeys_generic_lookup 函数进行查找
    else {
        ix = dictkeys_generic_lookup(mp, dk, key, hash);
        if (ix == DKIX_KEY_CHANGED) {
            goto start;
        }
        if (ix >= 0) {
            *value_addr = DK_ENTRIES(dk)[ix].me_value;
        }
        else {
            *value_addr = NULL;
        }
    }
    return ix;
}

所以该函数里面会调用三个辅助函数。

  • unicodekeys_lookup_unicode:在 unicode table 中查找字符串格式的 key
  • unicodekeys_lookup_generic:在 unicode table 中查找非字符串格式的 key
  • dictkeys_generic_lookup:在 generic table 中查找 key,格式不限。

我们以 unicodekeys_lookup_unicode 函数为例,看一下它的内部逻辑,不过在看之前,需要先了解几个其它函数。

// Include/internal/pycore_dict.h
// 获取哈希表的长度,即内部哈希索引数组的长度
#define DK_LOG_SIZE(dk)  _Py_RVALUE((dk)->dk_log2_size)
#define DK_SIZE(dk)      (((int64_t)1)<<DK_LOG_SIZE(dk))
// 获取紧跟在 PyDictKeysObject 结构体后面的键值对数组
// 这个和前面介绍字符串时,获取 PyASCIIObject 结构体后面的字符数组是类似的
// 主要是利用 C 语言指针的技巧(甚至都不能算技巧),这里再来详细介绍一下
// 假设有一个 int *a,那么 a + 3 和 a[3] 是等价的,都会向后偏移 3 个 int
// 那么问题来了,对于任意类型的指针 T *p,如果我想向后偏移 n 个字节,该怎么做呢?
// 很简单,可以将指针转成 int8_t *,然后加上 n 即可,会偏移 sizeof(int8_t) * n 个字节
// 比如 ((int8_t *)p) + n 或者 ((int8_t *)p)[n]
staticinlinevoid* _DK_ENTRIES(PyDictKeysObject *dk) {
    // 获取哈希索引数组,转成 int8_t * 类型
    int8_t *indices = (int8_t*)(dk->dk_indices);
    // 1 << dk->dk_log2_index_bytes 表示哈希索引数组的大小
    size_t index = (size_t)1 << dk->dk_log2_index_bytes;
    // 向后偏移 index 个字节,定位到键值对数组的首字节
    return (&indices[index]);
}
static inline PyDictKeyEntry* DK_ENTRIES(PyDictKeysObject *dk) {
    assert(dk->dk_kind == DICT_KEYS_GENERAL);
    // 获取键值对数组之后,转成 PyDictKeyEntry * 类型
    // 这样指针加 1,才会偏移 sizeof(PyDictKeyEntry) 个字节,跳到下一个元素
    return (PyDictKeyEntry*)_DK_ENTRIES(dk);
}
static inline PyDictUnicodeEntry* DK_UNICODE_ENTRIES(PyDictKeysObject *dk) {
    assert(dk->dk_kind != DICT_KEYS_GENERAL);
    // 获取键值对数组之后,转成 PyDictUnicodeEntry * 类型
    // 这样指针加 1,才会偏移 sizeof(PyDictUnicodeEntry) 个字节,跳到下一个元素
    return (PyDictUnicodeEntry*)_DK_ENTRIES(dk);
}
// 字典的 key 是否都是字符串,只需判断 dk_kind 是否不等于 DICT_KEYS_GENERAL 即可
#define DK_IS_UNICODE(dk) ((dk)->dk_kind != DICT_KEYS_GENERAL)
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2) 
#define DKIX_ERROR (-3)
#define DKIX_KEY_CHANGED (-4)

这些应该都是比较简单的内容了,下面来看一下 unicodekeys_lookup_unicode 函数。

// Objects/dictobject.c
// 哈希表的长度减 1
// 将 key 的哈希值和它按位与,便可将 key 映射成索引
#define DK_MASK(dk) (DK_SIZE(dk)-1)
#define PERTURB_SHIFT 5
// 基于哈希索引数组的索引,获取指定的哈希槽里面存储的键值对数组的索引
static inline Py_ssize_t
dictkeys_get_index(const PyDictKeysObject *keys, Py_ssize_t i)
{
    // 获取 dk_log2_size
    int log2size = DK_LOG_SIZE(keys);
    // 键值对数组的索引
    Py_ssize_t ix;
    // 如果哈希表的长度小于 1 << 8,哈希索引数组的每个元素占 1 字节
    if (log2size < 8) {
        const int8_t *indices = (const int8_t*)(keys->dk_indices);
        ix = indices[i];
    }
    // 如果哈希表的长度小于 1 << 16,哈希索引数组的每个元素占 2 字节
    // 指针类型要转成 int16_t *,这样获取元素时会获取两个字节
    else if (log2size < 16) {
        const int16_t *indices = (const int16_t*)(keys->dk_indices);
        ix = indices[i];
    }
    // 如果哈希表的长度大于等于 1 << 32,哈希索引数组的每个元素占 8 字节
    else if (log2size >= 32) {
        const int64_t *indices = (const int64_t*)(keys->dk_indices);
        ix = indices[i];
    }
    // 否则哈希索引数组的每个元素占 4 字节
    else {
        const int32_t *indices = (const int32_t*)(keys->dk_indices);
        ix = indices[i];
    }
    assert(ix >= DKIX_DUMMY);
    // 返回键值对数组的索引
    return ix;
}
static Py_ssize_t _Py_HOT_FUNCTION
unicodekeys_lookup_unicode(PyDictKeysObject* dk, PyObject *key, Py_hash_t hash)
{   
    // 键值对数组
    PyDictUnicodeEntry *ep0 = DK_UNICODE_ENTRIES(dk);
    // 哈希表的长度减 1
    size_t mask = DK_MASK(dk);
    // perturb,初始值等于参数 hash,即 key 的哈希值
    size_t perturb = hash;
    // 将哈希值和 mask 按位与,计算出哈希索引数组的索引
    size_t i = (size_t)hash & mask;
    Py_ssize_t ix;
    for (;;) {
        // 基于哈希索引数组的索引,从指定的哈希槽中获取键值对数组的索引
        ix = dictkeys_get_index(dk, i);
        // 如果 ix >= 0,说明确实存储了一个合法的键值对数组的索引
        if (ix >= 0) {
            // 基于索引 ix 获取键值对
            PyDictUnicodeEntry *ep = &ep0[ix];
            assert(ep->me_key != NULL);
            assert(PyUnicode_CheckExact(ep->me_key));
            // ep->me_key 和变量 key 都是指针
            // 如果这两者相等,说明指向了同一个对象(字符串),显然查找的 key 已在字典中
            // 如果 ep->me_key != key,说明两者指向的不是同一个对象
            // 那么就比较两个字符串本身以及哈希值是否相等,如果相等,也表示 key 已存在
            if (ep->me_key == key || (unicode_get_hash(ep->me_key) == hash && 
                                      unicode_eq(ep->me_key, key))) {
                // 此时直接返回 ix 即可
                return ix;
            }
        }
        // 哈希索引数组里面的元素初始为 -1,如果 ix == -1
        // 证明当前 key 映射出的哈希槽,还没有存储键值对数组的某个索引
        // 这就意味着当前要查找的 key 不存在,此时直接返回 -1 即可
        else if (ix == DKIX_EMPTY) {
            return DKIX_EMPTY;
        }
        // 走到这里说明 ix 是合法的,但是对应的 entry->me_key 和当前要查找的 key 不相等
        // 显然出现了索引冲突,于是将哈希值右移 5 位
        perturb >>= PERTURB_SHIFT;
        // 然后加上 i*5 + 1,并重新和 mask 按位与,得到新的哈希索引数组的索引
        // 也就是之前说的,改变规则、重新映射
        i = mask & (i*5 + perturb + 1);
        // 基于新的哈希索引数组的索引 i,从哈希槽中获取存储的键值对数组的索引 ix
        ix = dictkeys_get_index(dk, i);
        // 基于 ix 获取键值对,然后重复之前的比较逻辑
        if (ix >= 0) {
            PyDictUnicodeEntry *ep = &ep0[ix];
            assert(ep->me_key != NULL);
            assert(PyUnicode_CheckExact(ep->me_key));
            if (ep->me_key == key || (unicode_get_hash(ep->me_key) == hash && 
                                      unicode_eq(ep->me_key, key))) {
                return ix;
            }
        }
        else if (ix == DKIX_EMPTY) {
            return DKIX_EMPTY;
        }
        // 如果映射出来的索引还不行,那么继续重复相同的步骤
        // 哈希值右移 5 位,然后加上 i*5 + 1,再按位与 mask,进行下一轮循环
        // 所以我们发现上面几行逻辑其实有点冗余,直接进行下一轮循环不就好了吗
        // 其实 Python 这么做的目的是希望能够在一次循环中就把索引返回
        // 毕竟连续冲突两次的概率还是不高的,但如果真的连续冲突两次,那么只能下一轮循环了
        perturb >>= PERTURB_SHIFT;
        i = mask & (i*5 + perturb + 1);
    }
    Py_UNREACHABLE();
}

以上就是 unicodekeys_lookup_unicode 的具体逻辑,至于 unicodekeys_lookup_generic 函数和 dictkeys_generic_lookup 函数与之是类似的。

我们将逻辑再描述一遍,首先 perturb 初始等于 key 的哈希值,mask 等于哈希表的长度减一,然后执行 perturb & mask 便可得到一个索引。这个过程就是我们说的索引映射,映射出的索引便是哈希索引数组的索引,然后该索引对应的哈希槽又存储了一个索引,这个索引是键值对数组的索引


698f4d23df3f803db0bce94650ae62b3.png

哈希索引数组里面的一个位置我们称之为一个,如果映射出来的索引对应的哈希槽中存储的键值对数组的索引小于 0,说明该 key 对应的键值对还没有被存储过,那么直接返回初始值 -1 即可。

如果存储的键值对数组的索引(源码中的 ix)大于等于 0,说明已经存储了一个键值对,它的 key 和查找的 key 映射出的索引是相同的。然后比较 key 是否相等,如果相等,说明已经找到了,那么直接返回 ix 即可。如果 key 不相等,说明出现索引冲突了,那么要改变策略,重新映射。

perturb >>= PERTURB_SHIFT;
i = mask & (i*5 + perturb + 1);

变量 i 便是映射出的哈希索引数组的索引,但发生冲突了,于是将 perturb 右移 5 位,然后加上 perturb + i * 5 + 1,再和 mask 按位与计算出新的 i。至于为什么要选择这种做法,这是 Python 官方经过多次实践得出来的结论。

unicodekeys_lookup_unicode 函数执行完之后,_Py_dict_lookup 函数就拿到了指定的 key 对应的键值对数组的索引,并且也能拿到 key 对应的 value(key 若不存在就是 NULL)。


以上就是 _Py_dict_lookup 函数的逻辑,它内部调用了 unicodekeys_lookup_unicode 函数。不过还没结束,我们看到 _Py_dict_lookup 返回的是变量 ix,而变量 i 才是我们需要的。


变量 i 表示的索引,变量 ix 表示该存储的键值对数组的索引。由于我们是要寻找指定的槽,那么返回的应该是的位置、也就是变量 i 才对啊,为啥要返回变量 ix 呢?别急,往下看。

#define DKIX_EMPTY (-1)

初始状态下,槽存储的都是 -1,表示当前槽是可用的。如果存储的索引大于等于 0,则表示该槽已经被占用了,当 key 不相等时会改变规则重新映射。总之最终的结果是:

  • 如果 key 存在,那么返回的 ix 就是该 key 对应的键值对在键值对数组中的索引,此时 ix 大于等于 0;
  • 如果 key 不存在,那么返回的 ix 就是哈希槽的初始值 -1。


所以 _Py_dict_lookup 函数只是告诉我们当前 key 在哈希表中是否存在,如果要获取槽的索引,即 _Py_dict_lookup 里面的变量 i,那么还需要另外两个函数。

  • find_empty_slot:如果 _Py_dict_lookup 返回的 ix 小于 0,说明 key 不存在,那么调用该函数返回槽的索引。
  • lookdict_index:如果 _Py_dict_lookup 返回的 ix 大于等于 0,说明 key 存在,那么调用该函数返回槽的索引。

所以这两个函数做的事情是一样的,都是返回槽的索引,我们看一下具体实现。

// Objects/dictobject.c
static Py_ssize_t
find_empty_slot(PyDictKeysObject *keys, Py_hash_t hash)
{
    assert(keys != NULL);
    const size_t mask = DK_MASK(keys);
    // 获取槽的索引 i
    size_t i = hash & mask;
    // 获取槽存储的索引 ix
    Py_ssize_t ix = dictkeys_get_index(keys, i);
    // 不停映射,直到 ix 小于 0
    // 因为调用该函数已经说明 key 不存在了
    // 所以最终一定会映射到一个空槽
    for (size_t perturb = hash; ix >= 0;) {
        perturb >>= PERTURB_SHIFT;
        // 映射的逻辑是相同的
        i = (i*5 + perturb + 1) & mask;
        ix = dictkeys_get_index(keys, i);
    }
    // 当 ix 小于 0 时,便找到了槽的索引
    return i;
}
static Py_ssize_t
lookdict_index(PyDictKeysObject *k, Py_hash_t hash, Py_ssize_t index)
{
    size_t mask = DK_MASK(k);
    size_t perturb = (size_t)hash;
    size_t i = (size_t)hash & mask;
    for (;;) {
        // 基于槽的索引 i,获取槽存储的索引 ix
        Py_ssize_t ix = dictkeys_get_index(k, i);
        // 参数 index 就是 _Py_dict_lookup 函数返回的 ix
        // 如果 ix 和 index 是相等的,说明此时的 i 就是要获取的槽的索引
        if (ix == index) {
            return i;
        }
        if (ix == DKIX_EMPTY) {
            return DKIX_EMPTY;
        }
        // 整个映射逻辑都是一样的
        // 因为在 _Py_dict_lookup 函数中只返回了 ix,即参数 index
        // 所以要按照相同的规则再映射一次,如果映射出的 ix 和 index 相等
        // 那么我们就找到了槽的索引 i,并且索引为 i 的槽存储的就是 index
        perturb >>= PERTURB_SHIFT;
        i = mask & (i*5 + perturb + 1);
    }
    Py_UNREACHABLE();
}

所以我们说的探测函数应该是 _Py_dict_lookup 和 find_empty_slot、lookdict_index 的组合。

  • _Py_dict_lookup 负责返回槽存储的索引,用于判断 key 是否存在。
  • find_empty_slot、lookdict_index 则负责返回槽的索引,即 key 最终被映射到了哪一个


另外还有一点,我们之前说索引冲突时,会执行探测函数计算新的存储位置。其实不管有没有发生冲突,即使存储键值对的时候哈希表是空的,也要执行探测函数,毕竟探测函数的目的就是基于哈希值映射出一个合适的槽。如果探测函数执行的时候发现索引冲突了,也就是槽里的索引 ix >= 0,并且 key 还不相等,那么会改变规则重新映射。


因此在存储某个键值对时,无论索引冲突多少次,探测函数只会执行一次。在探测函数里面,会不断尝试解决冲突,直到映射出一个可用的索引。




小结


以上就是索引映射的具体逻辑,以及出现冲突是怎么解决的。就是先用哈希函数计算出 key 的哈希值,然后作为参数传递到探测函数中。在探测函数里面,会将哈希值和 mask 按位与,得到索引。如果索引冲突了,那么会改变规则,这里的规则如下:

// 将当前哈希值右移 PERTURB_SHIFT 个位
perturb >>= PERTURB_SHIFT;
// 然后将哈希值加上 i*5 + 1,这个 i 就是当前冲突的索引
// 运算之后的结果再和 mask 按位与,得到一个新的 i
// 然后判断变量 i 对应的槽是否可用,不可用则重复当前逻辑,直到出现一个可用的槽
i = (i*5 + perturb + 1) & mask;

所以 Python 在索引冲突时,并不像线性探测和平方探测那样,简单地加一个固定的偏移量,而是参考对象的哈希值计算出一个新的索引。

相关文章
|
6月前
|
存储 C++ 索引
哈希表、集合、映射
哈希表、集合、映射
|
3月前
|
数据库 数据库管理 索引
主键和唯一键有什么区别?
【8月更文挑战第1天】
237 6
主键和唯一键有什么区别?
|
4月前
|
存储 Java
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
Redis08命令-Hash类型,也叫散列,其中value是一个无序字典,类似于java的HashMap结构,Hash结构可以将对象中的每个字段独立存储,可以针对每字段做CRUD
集合、哈希表、字典
集合、哈希表、字典
72 0
SWUSTOJ 1013: 哈希表(开放定址法处理冲突)
SWUSTOJ 1013: 哈希表(开放定址法处理冲突)
104 0
【LeetCode677】键值映射
方法一: 暴力扫描。对哈希表进行增删查改,就是注意找到prefix开头的键key的操作就行。
91 0
【LeetCode677】键值映射
|
索引
索引分类、创建索引、删除索引
索引分类、创建索引、删除索引
137 0
索引分类、创建索引、删除索引
|
关系型数据库 MySQL 数据库
创建索引,这些知识应该了解
在 MySQL 中,基本上每个表都会有索引,有时候也需要根据不同的业务场景添加不同的索引。索引的建立对于数据库高效运行是很重要的,本篇文章将介绍下创建索引相关知识及注意事项。
144 0