本文源代码基于 commit: 73820a60cc3c990abb351540ca27bf7689bce8ac
哈希表：开放定址法
As we all know，在需要快速搜索的场景下，哈希表提供O(1)的检索复杂度。哈希就可能会产生冲突。对冲突的处理基本上分为两大类：链表法（又称拉链法），开放定址检测法。 链表法，就是说在每个哈希槽(slot)上其实都是一个链表表头，所有落入这个槽的元素都接入这个链表。
开放定址检测法，本质就是多试几次，万一可以呢，发现本key的哈希槽被占用的时候，使用一个算法算一算下一个槽的位置，可以就占掉，不可以就再试下去。
个人觉得，这两种方法在实现和使用的时候，各有不同。链表法实现较为直观，但可能造成空间浪费。想象申请了n块内存，结果哈希值比较稀疏，值都落到了几个大链表里，就不划算。另一方面，链表法什么时机重hash也是一个问题（个人感觉），毕竟单个槽过长，搜索会退化成O(n)。开放定址检测不存在内存浪费，申请多少用多少，在扩容之前只会用这些申请的内容。重hash的时机也比较好掌握；但是在设计检测算法的时候也要注意，首要是不能产生死循环（在有足够空位的情况下，要能最终找到至少一个空位），其次二次检索的效率也要注意。比如线性检测就不太好，在哈希槽较满的情况下容易产生近O(n)的效率。
cpython中解决字典的哈希冲突使用的是开放定址法。
开放定址法的删除
链表法中要删除一个元素很容易，把他从哈希槽的链表里拿掉就好了。但开放定址法不能简单地删掉。举个例子，用线性探测(虽然不好)时，搜索其实构成了一个搜索顺序。比如搜索key为13, hash值为3（比如hash函数就是n%10）的元素能插入哪个位置，3，4，5都已经有元素了，那么搜索顺序会有
3(have) --> 4(have) --> 5(have) --> 6(null)
ok, 找到了我的家（yeah），那么key 13就落户编号6的哈希槽。但是这个时候，用户删除了位置4的哈希槽元素，然后再去搜索key 13元素位置的时候会变成这样:
3(have) --> 4(null) --> 5(have) --> 6(have 13)
到位置4的时候发现没有了。可能有人会问，那算法继续搜索下去就好了嘛，总会找到key 13的，但这是在知道这个key存在的情况下才有意义；如果算法这么实现的话，所有搜索不存在key的情形都会把搜索算法变成O(n)，因此开放定址法的搜索止于找到该key或发现一个空位。如上，这个搜索空间就断裂了。（这个问题在cpython源码注释中也有说明）
所以开放定址法不能直接删除元素，而是应该标记删除，以确保搜索空间的完整连续性，构造出如下的搜索空间：
3(have) --> 4(dummy) --> 5(have) --> 6(have 13)
其中，dummy就是cpython中使用的标记删除，算法跑到4处会继续向下搜索直到6的位置
cpython的搜索例程
上代码
static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
cpython中关于在dict中搜索的代码位于dictobject.c，函数签名如上。参数中传入一个操作的字典对象mp，查找的key，该key的hash值(传入是因为之前算过，就不要重复算了)，最后一个参数是查找出来的值的引用，需要在函数内赋值（或者没找到置空）。返回值就是该key的位置，有三种可能：
DKIX_EMPTYDKIX_DUMMY- 某个大于等于0的数字。
DKIX_EMPTY就是说没找到，DKIX_DUMMY就是说找到了这个key的位置，但是已经被删除了，最后就是找到的哈希槽编号的数值了。
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;
初始了一坨变量，其中hash & mask这个操作比较特殊。其中hash就是哈希值，mask等于dk_size-1。这个操作让i落在哈希槽范围内。这个地方当时粗看的时候我觉得很诡异，为啥与操作能到达跟取余一样的效果呢。这里不是说与操作的结果值跟取余是一样的，而是说能达到同样的收敛值域的作用。然后我做了一个不加验证的假设: cpython中字典的容量都是2^n，然后取2^n-1，让n位二进制位都是1，这样与操作，x & (2^n-1)的结果必然小于等于2^n-1。此外这段代码设置了一个tag:top，目的是在有必要的时候goto回来重新开始。
注意，这里cpython的实现是for(;;)死循环，实现上要求必要有返回。下面分几段代码分析一个例程。
for (;;) {
Py_ssize_t ix = dk_get_index(dk, i);
if (ix == DKIX_EMPTY) {
*value_addr = NULL;
return ix;
}
if (ix >= 0) {
...
}
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
首先在每个循环例程最开始，都会用当前的i来找内存该位置的状态，如果发现这个位置是空，就直接返回了。如果发现有东西，就会进一步做一些操作来确认这块内容是不是我想要的。如果又不是DKIX_EMPTY，又不是大于等于0的某个数，按照上述的约定，就一定是DKIX_DUMMY，也就是找到了一个已删除的内容，继续做探测。
for (;;) {
Py_ssize_t ix = dk_get_index(dk, i);
if (ix == DKIX_EMPTY) {
...
}
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) {
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;
}
}
}
...
}
以上代码就是找到了一个非空的哈希槽之后该做什么。
首先比较了搜索的key与该哈希槽存储的key是不是根本同一个指针。因为cpython会复用很多小对象。
其次会比较这个槽存储元素的hash值。因为经过哈希碰撞之后，每个槽存储的hash值并不一定是一手取与得到的。如果不一样，for循环就会进入下一个例程。has值一样，然后要比较该元素的key是否deepEqual当前的key。因为都说了哈希碰撞嘛，这个key跟key也可能是不一样但是hash值一样的。（连SHA1都可以碰撞的说…）。经过hash值一样，key相等比较之后，这个元素位”基本”上就是我们要找的元素了。
但是，这里cpython做了”看似”比较多余的事情，他比较了在代码中使用的字典还是不是要搜索的字典，被搜索到的key还是不是之前比较的key。这里用局部变量跟外部变量引用相比较，是要确定外部变量有没有被修改。这个代码为什么可以生效，目前我还没有明确的证据，因为就算这个if (dk == mp->ma_keys && ep->me_key == startkey)能成立，进入if之后就能保证这个if依然成立吗；返回值依然有可能是脏的。还需要进一步阅读代码。
检测算法
上一节的代码里，其实我真正关心的只有下面这段做检测的代码。从函数关系来说，这个探测是一种平方探测。（突然想起了时间序列里的AR(1)…）。perturb初值就是hash值，每次循环右移PERTURB_SHIFT = 5位参与运算
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
怎么证明这个函数关系不会陷入死循环呢？恩，我也不知道…严格证明懒，留一个随缘未解之谜吧…
我写了一个go的小代码来看这个算法会”路过”那些哈希槽。
package main
import (
"fmt"
)
func main() {
hash := 9
perturb := hash
mask := 7
i := hash & mask
for j:=0;j<20;j++{
fmt.Println(i)
perturb >>= 5
i = cal(i, perturb, mask)
}
}
func cal(i int, perturb int, mask int) int {
return (i*5 + perturb + 1) & mask
}
输出的搜索空间如下：
1 -->6 --> 7 --> 4 --> 5 --> 2 --> 3 --> 0
可以看到，在这个hash:9 ,mask:7输入下，可以一次性探测到所有的8个位置。后面的输出就是重复这个序列了。（是不是很神奇呢…）
Ending
好了，本文到此为止，字典的CRUD就只介绍R的核心部分。（因为写文章很花时间的…）其他内容，有缘有心情再见。