引子
哈希的本质是从一个较大空间映射到一个较小的空间,因此在插入数据足够多之后,根据鸽巢原理,一定会存在位置冲突。常见的哈希表(Hash Table 或者字典,dictionary)会通过链表、开放地址探测等方式来处理冲突。单桶多函数的布谷鸟哈希,便是开放地址法处理冲突的一种哈希表,只不过有冲突后,不是通过线性寻找新的位置,而是通过额外哈希函数来寻找。
作者:木鸟杂记 https://www.qtmuniao.com/2021/12/07/cuckoo-hash-and-cuckoo-filter, 转载请注明出处
原理
布谷鸟哈希最早是Rasmus Pagh 和 Flemming Friche Rodler 在 2001 年一次会议上公开的[1]。其基本思想为:
- 使用两个哈希函数 h1(x) 、 h2(x) 和两个哈希桶 T1、T2 。
- 插入元素 x:
- 如果 T1[h1(x)] 、T2[h2(x)] 有一个为空,则插入;两者都空,随便选一个插入。
- 如果 T1[h1(x)] 、T2[h2(x)] 都满,则随便选择其中一个(设为 y ),将其踢出,插入 x。
- 重复上述过程,插入元素 y。
- 如果插入时,踢出次数过多,则说明哈希桶满了。则进行扩容、ReHash 后,再次插入。
- 查询元素 x:
- 读取 T1[h1(x)] 、T2[h2(x)] 和 x 比对即可
布谷鸟(Cuckoo),即大杜鹃,喜欢在别的鸟窝里产蛋。布谷鸟幼鸟出生后,会将其他蛋踢出,借巢长大。布谷鸟哈希的关键设计正在于“踢出”(kicks out)这个动作,该设计和名字都堪称神来之笔。
变种
布谷鸟哈希可以有很多变种,比如:
- 使用两个哈希函数和一个哈希桶。
- 使用两个哈希函数和四路哈希桶。
可以证明,后者的桶的利用率会更高,感兴趣可以去看原论文[3]查看论证过程。
应用
cmu 大学的 Bin Fan 等人,在 2014 年发表了一篇名为:Cuckoo Filter: Practically Better Than Bloom [3] 的论文,基本思想是将布谷鸟哈希(key-value queries)的思想应用于集合(set membership)方向,可以替代工程中常用的 Bloom Filter,有以下优势:
- 支持删除元素
- 更高的查询效率,尤其在高负载因子时
- 相比其他支持删除的 Filter 更容易实现
- 如果期望误报率在 3% 以下,所用空间比 Bloom Filter 少
为了达到以上效果,Cuckoo Filter 对原 Cuckoo Hash 做了如下改变:
- 为了提高桶的利用率,使用多路哈希桶。
- 为了减少内存的使用,只存储 key 指纹。
此外,当某个值 x 被踢出时,需要找到另外一个位置。 Cuckoo Hash 是通过额外哈希函数作用于 x 计算而出:h2(x)
。但在 Cuckoo Filter 中为了节省内存,保存的是定长的指纹 finger(x)
而非原值 x。当 x 被踢出时,如何找到其另外一个位置?直观的,我有两种想法:
方法一:通过 h2(finger(x))
计算出另外一个位置。但这样在计算第二个位置时,相当于将原数据空间强行压缩到了指纹空间,会损失很多信息,加大碰撞概率。
方法二:在值中记下另外一个位置, pair(finger, the other position)
,但这样空间占用会大大增加。
Cuckoo Filter 用了一个巧妙地做法,将位置(h1(x)
)和对应值的哈希(hash(finger(x))
)进行异或得到另外一个位置。我们指导,异或运算满足性质:三值中的任意两值异或都能得到第三值。在另一个位置 x 被踢出时,也能通过同样的方法得到原位置,如下图所示。
为什么不直接和finger(x)
进行异或计算另外位置呢?因为 finger(x)
一般位数比较少,比如 8 bit。如果按照这种方法,从物理意义上理解,即是在原位置±2^8 = 256 的范围内找到另一个位置,因为异或只会改变低 8 bit 的值。这个范围太小了,不利于均衡散列。
另外有两点需要注意。一是不借助额外信息, Cuckoo Filter 是不能扩容的,因为我们已经丢失了原值 x,则无法计算扩容后新的位置 hash(x)
。当然,如果保存有相应的 key 集合,也可以扩容后,将原来的 key 集合重新插入一遍。二是,如果两个不同值 x 和 y,恰巧满足 hash(x) == hash(y) && finger(x) == finger(y)
则会出现假阳性。理解假阳性,我们可以从哈希的本质出发。如开篇所述,哈希本质是从大空间映射到小空间,则小空间中一定会出现碰撞,出现碰撞的两个原值一个存在,便会让人以为另一个也存在。回到 Cuckoo Filter 上,如果 x 和 y 都存在于 Cuckoo Filter 中,删除 x 或者 y 时,删除两个相同 finger 中的任何一个即可。
实现
布谷鸟过滤器的实现很简单, 论文中也给出了伪代码,贴在这里。
插入 Insert(x)
1 | f = fingerprint(x); |
查找 Lookup(x)
1 | f = fingerprint(x); |
删除 Delete(x)
1 | f = fingerprint(x); |
参考
布谷鸟哈希和布谷鸟过滤器
- 布谷鸟哈希:https://www.itu.dk/people/pagh/papers/cuckoo-jour.pdf
- 布谷鸟哈希维基百科:https://en.wikipedia.org/wiki/Cuckoo_hashing#cite_note-Cuckoo-1
- 布谷鸟过滤器 Cuckoo Filter: Practically Better Than Bloom https://www.cs.cmu.edu/~binfan/papers/conext14_cuckoofilter.pdf
- 布谷鸟过滤器实现:[https://coolshell.cn/articles/17225.html]