楔子
两个对象的哈希值相等，那么映射出的索引肯定相同。而如果哈希值不相等，映射出的索引也有可能相同，因为与哈希值空间相比，哈希表的槽位是非常有限的。如果不同的对象在经过映射之后，生成的索引相同，或者说它们被映射到了同一个槽，那么便发生了索引冲突。
解决索引冲突的常用方法有两种：分离链接法和开放寻址法。
分离链接法比较简单，如果有多个键值对映射到同一槽位，那么就用链表将它们串起来。然后是开放寻址法，这也是 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 在索引冲突时，并不像线性探测和平方探测那样，简单地加一个固定的偏移量，而是参考对象的哈希值计算出一个新的索引。
