Skip to main content

BF过滤器

第02部分 BloomFliter​

一、集合 Sets​

现代实现集合有两种方法：

  • 一种是Hash tables，提供 O(1)O(1) 的时间复杂度（但是无法排序）
  • 一种是平衡的二叉树，提供 O(logN)O(log N) 的时间复杂度（支持排序）

因此，C++的Map使用的是后者。

二、位图BitMap​

  • 位图的应用非常广泛，甚至在图像处理领域也很常见
  • 位图可以理解为一个由Bit位组成的数组，数组里面的每一个元素只可以是0或者1
  • 要在C++中使用位图，需要添加头文件#include <bitset>
  • 我们C++之前场景的最小单位的数组是布尔数组，每一个元素一个字节，实际上位图是力度更小的数组，里面的每个元素都是一个位，按照位来存储数据，所有的数据都是0或者1。
  • 值得注意的是，位图实际是一个模板，我们使用之前需要指定参数，这个参数就是位图的大小（单位是位）。例如我指定一个std::bitset<10 * 8> bloomfliterData;，那么它占用的大小就是 10KB10KB。

关于位图，下面是他常见的API：

std::bitset<100> c;

c.size()      // 返回大小（位数）
c.count()     // 返回1的个数
c.any()       // 返回是否有1
c.none()      // 返回是否没有1
c.set()       // 全都变成1
c.set(p)      // 将第p + 1位变成1
c.set(p, x)   // 将第p + 1位变成x
c.reset()     // 全都变成0
c.reset(p)    // 将第p + 1位变成0
c.flip()      // 全都取反
c.flip(p)     // 将第p + 1位取反
c.to_ulong()  // 返回它转换为unsigned long的结果，如果超出范围则报错
c.to_ullong() // 返回它转换为unsigned long long的结果，如果超出范围则报错
c.to_string() // 返回它转换为string的结果

二、BloomFliter​

1）原理简介​

  • 首先在构造一个BF过滤器之前，我们需要准备好一组哈希函数 Hash1(x),Hash2(x)⋯Hashn(x)Hash_1(x), Hash_2(x)\cdots Hash_n(x)

  • 然后，BF过滤器是一个数据结构，用来快速判断是否一个元素出现在集合中的方法

  • 当一个元素插入进来的时候，我们会利用这个元素的关键字Key和所有的哈希函数计算他的一组Value。

    然后把Value在位图中对应的位置从0标记为1。当以后要判断这个元素是否存在的时候，只需要计算他的所有哈希值，然后判断位图中的值即可。

2）数学推导​

当 nn 个元素插入到到大小为 mm 位的BF过滤器的时候，某一个特定的位是0的概率是：(假设插入的时候所有位置插入的概率相等，假设有 kk 个哈希函数，nn 个插入的数据就要计算出 knkn 个值)

(1−1m)kn=e−knm(1-\frac{1}{m})^{kn} = e^{-\frac{kn}{m}}

所以某一个特定的位是1的概率是：

1−(1−1m)kn=1−e−knm1-(1-\frac{1}{m})^{kn} = 1-e^{-\frac{kn}{m}}

所以，出现误判的概率是，当插入的值计算的所有哈希值对应位置全部是1，概率是

f=(1−(1−1m)kn)k=(1−e−knm)kf=(1-(1-\frac{1}{m})^{kn})^{k} = (1-e^{-\frac{kn}{m}})^{k}

假设 p=−knmp = -\frac{kn}{m}，所以p=12p=\frac{1}{2}的时候 ff 最小。

3）如何支持删除​
  • 我们刚刚说的BF过滤器支持查找，支持插入数据，但是不支持删除！怎么处理呢？
info

显然不能直接删除，假如删除的时候，把某个Key对应的Hash值全部删除，而删除的值恰好被别的某个Key公用，那就导致数据丢失。

  • 所以要解决这个问题，我们可以布谷鸟哈希，参考下文

三、布谷鸟哈希​

布谷鸟过滤器用更低的空间开销解决了布隆过滤器不能删除元素的问题，做到了更好的效果，具体的

  • 支持动态的添加和删除元素
  • 提供了比传统布隆过滤器更高的查找性能，即使在接近满的情况下（比如空间利用率达到 95% 的时候）
  • 比起商过滤器它更容易实现
  • 如果要求误判率低于3%，它比布隆过滤器有更低的空间开销
算法描述​

  • 算法使用两个哈希函数hashA 和hashB 计算对应key的位置 i1,i2i_1, i_2。

    1. 当两个i1,i2i_1, i_2位置都为空，则选择一个位置插入
    2. 当两个i1,i2i_1, i_2位置只有一个为空时，则插入到空位置
    3. 当两个哈希位置均不为空时，随机选择两者之一的位置上keyx 踢出，计算踢出的keyx 另一个哈希值对应的位置进行插入，转至2执行（即当再次插入位置为空时插入，仍旧不为空时，踢出这个keyy）
    4. 如果出现死循环，或者连续踢了很多元素就考虑扩容

  • 具体的位点计算如下：

i1=Hash(key)i2=i1⊕Hash(fingerprint(x))i_1 = Hash(key) \\ i_2 = i_1 \oplus Hash(fingerprint(x)) \\
  • 为什么后面就是 fingerPrintfingerPrint 呢，因为这个过滤器只存储Key的指纹，不会完整的存储Key
  • 假如出现冲突，原来在 i1i_1 位置的就会拿自己的坐标 i1i_1 和自己那个地方存储的指纹亦或，得到 i2i_2
  • 此外，假如这个元素原来在 i1i_1 已经被移动了，再一次移动的时候会被移动到 i1i_1 说白了就是移动回来了。
i3=i2⊕Hash(fingerprint(x))=i1i_3 = i_2 \oplus Hash(fingerprint(x)) = i_1
  • 如果出现死循环，那就是说明空间已经不够了，就可以考虑扩容，比如我可以再增加一个哈希函数。