楔子
两个对象的哈希值相等，那么映射出的索引肯定相同。而如果哈希值不相等，映射出的索引也有可能相同，因为与哈希值空间相比，哈希表的槽位是非常有限的。如果不同的对象在经过映射之后，生成的索引相同，或者说它们被映射到了同一个槽，那么便发生了索引冲突。
解决索引冲突的常用方法有两种：分离链接法和开放寻址法。
分离链接法比较简单，如果有多个键值对映射到同一槽位，那么就用链表将它们串起来。然后是开放寻址法，这也是 Python 使用的方法，我们详细介绍一下。
开放寻址法
首先将 key 映射成索引，如果发现该索引对应的哈希槽被占了，那么就尝试另一个。
new_key 被映射到了索引为 5 的槽，但是该槽已经存储了键值对数组的索引，即该槽被占了。如果是分离链接法，那么会使用链表将两个 entry 串起来，但开放寻址法则是选择一个新的槽，也就是重新找个坑。
那么问题来了，新的槽要怎么找呢？一般来说，会在首槽的基础上增加一个偏移量，得到新的槽，如果还冲突，那么继续增加偏移量，直到找到一个可用的槽。总的来说就是一个不断探测的过程，每一次探测都会尝试增加偏移量。
所以新的问题又产生了，每次增加的偏移量是多少呢？其实这个问题取决于具体实现，如果偏移量是线性增加的，我们称之为线性探测；如果偏移量是平方增加的，我们称之为平方探测。
但不管是线性探测，还是平方探测，其实都不够好。因为偏移量始终是以一种固定的模式增加，这就导致映射到同一槽位的两个 key 的探测序列是相同的。
比如这里的 key1 和 key2，它们的哈希值不同，但都映射到了索引为 2 的槽，这是完全正常的，因为哈希表的槽位有限。而由于偏移量的增加方式是固定的，比如这里每次都增加 2，再加上首槽相同，因此它们的探测序列也相同，显然这会导致后续出现多次冲突。
所以 Python 对此进行了优化，探测函数在发现索引冲突时，不会简单地增加一个偏移量，而是会参考对象的哈希值，计算下一个候选位置，这就大大降低了冲突的可能性。
Python 的这种做法被称为迭代探测，当然迭代探测也属于开放寻址法的一种。所以当出现索引冲突时，Python 并不是简简单单地加上一个偏移量，而是使用专门设计的探测函数进行二次探查，也就是之前说的改变规则、重新映射，然后在函数内部会参考对象的哈希值来计算出一个新的索引。
在 dictobject.c 文件开头有着大量的注释，对字典进行了全局性的概括，当然具体细节我们都会详细说明。
探测函数
当存储一个键值对时，要将 key 映射成一个索引，这个索引就是哈希索引数组的索引。那么具体是怎么映射的呢？这里先来回顾一下字典的结构。
字典有两种实现方式，一种是分离表，另一种是结合表。对于分离表而言，键由 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 便可得到一个索引。这个过程就是我们说的索引映射，映射出的索引便是哈希索引数组的索引，然后该索引对应的哈希槽又存储了一个索引，这个索引是键值对数组的索引。
哈希索引数组里面的一个位置我们称之为一个槽，如果映射出来的索引对应的哈希槽中存储的键值对数组的索引小于 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 在索引冲突时，并不像线性探测和平方探测那样，简单地加一个固定的偏移量，而是参考对象的哈希值计算出一个新的索引。
