布谷鸟筛选器

参考: https://www.cnblogs.com/zhaodongge/p/15067657.html

概述

布隆筛选器

可视化布隆过滤器

流程:

1. 插入值 item1
2. 经过几个不同的Hash算法，得到相应个数的索引序号
3. 将列表相应序号的位置置为1
4. 查询 item2
5. Hash后获取的索引序号，在列表中查询，是否都为1，如果有位置不为1，则 item2不存在，反之则存在

概要：

• 布隆过滤器说存在的元素，不一定存在。

  因为可能存储元素数量多了以后，查询不存在列表元素的值都为1了。

• 布隆过滤器说不存在的元素，就一定不存在

• 针对一定的假阳性概率\(\epsilon\), 需要 \(k = log_2{1/\epsilon}\)的hash方法，\(1.44*log_2{1/\epsilon}\)bits

布谷鸟哈希

布谷鸟哈希使用2个哈希列表（T1, T2），长度都为 r。对应的两个哈希函数(h1, h2)，每个元素只能存在于其中一个哈希列表中，不能两个都存在。

伪码：

# 查询
func lookup(x):
	return T1[h1(x)] == x or T2(h2(x)) == x
# 插入
func insert(x):
	if lookup(x) then return
	loop MaxLoop times
		if

布谷鸟筛选器

论文

布隆筛选器的不足：

1. 无法删除已经保存的item(除非rebuild)，一些布隆的扩展或者变种可以做到，但是所需空间或者效率都会大不如之前
2. 空间利用率大了之后，假阳性概率会增大。所以为了正确率，空间利用率会低

算法

支持的算法: - 插入insert - 查询lookup - 删除delete

def insert(x):
	f = fingerprint(x)
	i1 = hash(x)
        i2 = i1 xor hash(f)
	if bucket[i1] or bucket[i2] has en empty entry then
		add to that bucket
		return Done
	i = randomly pick i1 or i2
	for n=0; n < MaxNumKicks; n++ do
		randomly select an entry e from bucket[i]
		swap f and the fingerprint stored in entry e
		i = i xor hash(f)
		if bucket[i] has an empty entry then
			add f to bucket[i]
			return Done
	return Failue