type
status
date
slug
summary
tags
category
icon
password

布隆过滤器缺点

  • 存在误判性
  • 不能删除元素

布谷鸟过滤器

最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希，得到桶中的两个位置，此时
  • 如果两个位置都为为空则将key随机存入其中一个位置
  • 如果只有一个位置为空则存入为空的位置
  • 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置
当然假如存在绝对的空间不足，那老是踢出也不是办法，所以一般会设置一个踢出阈值，如果在某次插入行为过程中连续踢出超过阈值，则进行扩容。
notion image

插入

根据公式，计算一个指纹fp=指纹(x)，p1=hash（x），p2=hash(指纹)异或p1
将指纹做hash目的是将p1和p2两个位置离的更远
指纹是每个位中有多个巢（图中为4个，类似二维数组），这种方法可以快速找到另一个位置

查找

布谷鸟过滤器的查找过程非常简单。给定一个项目x，算法首先根据上面的插入公式计算x和两个候选桶的指纹。然后读取这两个桶:如果两个桶中的任何现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。这个时候，只要没有桶溢出，就可以保证没有漏报。

删除

标准布隆过滤器无法删除，因此删除单个项目需要重建整个过滤器，而计算布隆过滤器需要更多空间。布谷鸟过滤器就像一个计数布隆过滤器。您可以通过从哈希表中删除相应的指纹来删除插入的项目。其他具有类似删除过程的过滤器比布谷鸟过滤器更复杂。 具体的删除过程也很简单。检查给定项目的两个候选存储桶；如果任何桶中的指纹匹配，则匹配指纹的副本将从桶中删除。

踢出操作

  1. 检查候选桶：
      2. 检查 h1(x)h1​(x) 和 h2(x)h2​(x) 是否有空槽。如果有，直接将 xx 的指纹插入空槽，操作完成。
  1. 踢出操作：
      2. 如果两个候选桶都已满，则随机选择一个桶（例如 h1(x)h1​(x)），踢出其中一个现有元素 yy 的指纹。
  1. 重新插入被踢出的元素：
      2. 被踢出的元素 yy 会被重新插入到它的另一个候选桶中（即备用位置）。具体来说：
      • 如果 yy 是从 h1(x)h1​(x) 中踢出的，则它的备用位置是 h2(y)h2​(y)。
      • 如果 yy 是从 h2(x)h2​(x) 中踢出的，则它的备用位置是 h1(y)h1​(y)。
  1. 递归踢出：
      2. 如果备用位置也已满，则重复上述踢出操作，直到找到一个空槽或达到最大踢出次数（通常设置为一个较小的值，如 500 次）。
  1. 插入失败处理：
      2. 如果达到最大踢出次数仍未找到空槽，则插入失败，可能需要扩容或重建过滤器。

缺点

  • 删除不完美，存在误删的概率。删除的时候知识删除了一份指纹副本，并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
  • 插入复杂度比较高。随着插入元素的增多，复杂度会越来越高，因为存在桶满，踢出的操作，所以需要重新计算，但综合来讲复杂度还是常数级别。
  • 存储空间的大小必须为2的指数的限制让空间效率打了折扣。
  • 同一个元素最多插入kb次，（k指哈希函数的个数，b指的桶中能装指纹的个数也可以说是桶的尺寸大小）如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器，其中重复插入会导致计数器溢出。