在我的记忆中布谷鸟过滤器一直是说比bloom好,那么我博客便以一个diss布谷鸟过滤器的角度来探究

学前须知:本篇立足于读者了解bloomfilter底层实现上

布谷鸟相较于bloom的优点

支持删除操作

如何支持呢?因为bloom的话是不能支持的,他的一个bit可能代表了多个key存在的情况,所以这个bit位是不能随便乱动的!

那么布谷鸟呢?下面这段便是布谷鸟过滤器的原理啦

布谷鸟交配后，雌性
布谷鸟
就准备产蛋了，但它却不会自己筑巢。它会来到像知更
鸟
、刺嘴莺等那些比它小的
鸟
类的巢中，移走原来的那窝蛋中的一个，用自己的蛋来取而代之。相对于它的体形来说，它的蛋是偏小的，而且蛋上的斑纹同它混入的其他
鸟
的蛋也非常相似，所以不易被分辨出来。如果不是这样，它的蛋肯定会被扔出去。

更具体地说是

最原始的布谷鸟
哈希方法是使用两个哈希函数对一个
key
进行哈希，得到桶中的两个位置，此时

  • 如果两个位置都为为空则将
    key
    随机存入其中一个位置
  • 如果只有一个位置为空则存入为空的位置
  • 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置

当然假如存在绝对的空间不足，那老是踢出也不是办法，所以一般会设置一个
踢出阈值
，如果在某次插入行为过程中连续踢出超过阈值，则进行扩容。

更现代化的布谷鸟过滤器:

由两个或者多个哈希函数构成，布谷鸟过滤器的布谷鸟哈希表的基本单位称为
条目（entry,说起条目感觉很陌生,其实就是java中map的一个单位）
。 每个条目存储一个
指纹（fingerprint）(指纹这个概念大家应该会比较陌生,下文会给出更具体的描述)
，指纹指的是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置，例如使用8bits的指纹大小。

插入

以最简单的两个hash函数为例来进行说明

首先插入值为x,

  1. 我们需要先计算出指纹

$$
f=fingerprint(x)
$$

  1. 计算出两个候选位置

使用两个不同的哈希函数
h1
和
h2
计算两个候选存储位置
i1
和
i2
。注意这里计算
i2
时会用到指纹
f
。
$$
i1=h1(x)
$$

$$
i2=h2(f)=i1⊕h(f)
$$
其中，
h(f)
是对指纹
f
进行哈希运算得到的值。

尝试插入
：首先尝试将指纹
f
插入到位置
i1
对应的桶中。如果桶中有空位，则直接插入。如果
i1
的桶满了，再尝试将
f
插入到位置
i2
的桶中。如果
i2
的桶有空位，则直接插入。

踢出和重插入
：如果两个候选位置的桶都满了，就需要“踢出”其中一个桶中的已有指纹，并将被踢出的指纹重新插入。具体步骤如下：

  • 从
    i1
    或
    i2
    中随机选择一个桶，将该桶中的一个现有指纹
    f'
    踢出。

  • 将原始指纹
    f
    插入到踢出的指纹
    f'
    的位置。

  • 对于被踢出的指纹
    f'
    ，计算它的另一个候选位置
    i2'
    ，即：
    $$
    i2′=i1′⊕h(f′)
    $$

  • 将被踢出的指纹
    f'
    重新插入到
    i2'
    的桶中。

  • 如果
    i2'
    的桶也满了，重复踢出和重插入的过程，直到成功插入或者达到最大重插入次数。

相信大家看下来可能有点模糊模糊,下面便一一解答
具体的指纹是怎么取的?这个指纹算出来是什么样子的?

指纹是通过hash函数来获得,如果说我们hash函数算出的值过长那么就截断

例如:
$$
f=h(x)&0xFF
$$
通常会选用8位和16位

为什么第二个hash函数需要是i1⊕h(f)?以及为什么他的传参要是f?

先给出结论主要是为了实现
搬家

首先回到上面的重插入!当位置冲突后我们最终会算出里面那个value最终放的是指纹对吧?然后对应的哈希函数我们都知道对吧?假如说原本这个位置添加的选择的是i1,那么他接下来要选择的是i2对吧?那么i2=i1⊕h(f),这里面什么我们都有没错吧?那么我们自然可以实现让它去搬家的操作,(
同时这里也有印证了那么一句名言,软件上有问题那么再加一层就没有问题!伟大无需多言
)

查找

布谷鸟过滤器的查找过程很简单，给定一个项x，算法首先根据上述插入公式，计算x的指纹和两个候选桶。然后读取这两个桶：如果两个桶中的任何现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。此时，只要不发生桶溢出，就可以确保没有假阴性。(这句话的意思是:我们在插入的时候可能会有踢出的操作嘛,那么在桶不够的情况下,再踢出后你的指纹就被踢出了呀,然后我们在判断的时候会出现我们原本添加了但是现在结果是找不到)

仍然存在假阳性哦,基本上跟hash有关都有一定的假阳性,我们可能出现hash映射到同样两个桶对吧,那么在他的指纹计算也相同时,不就是假阳性了吗?

删除

很容易啦,我们关键就是在对应x的槽上放了个x对应的指纹,指纹删掉就ok了

支持扩容(普通布谷鸟是不行的,普通bloom也是不行的)

这里基本上要涉及论文了,我懒得看了..,讲述我个人的猜测,不过别人的应该不会这么简单

我的猜测就是把原先能得出hash函数的得出的指纹来当做新的要设置的值,因为我们通过得出指纹的hash得到的值应该是与原本的空间是无关的,那么也就是说这里可以当做不变量,且上文的查询操作也指出其实关键是验证指纹是否相同在这两个坑中,所以这个指纹也本身具有一定的特性,有点类似责任链的思想,弄了个hash链,不过碰撞的概率应该也不会提升太大

缺点

  • 删除不完美，存在误删的概率。
    删除的时候知识删除了一份指纹副本，并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
  • 插入次数可能会有多次

参考

https://www.cnblogs.com/zhaodongge/p/15067657.html
https://github.com/CGCL-codes/DCF

标签: none

添加新评论