本文源代码基于 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_EMPTY
DKIX_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的核心部分。(因为写文章很花时间的…)其他内容,有缘有心情再见。