在软件中，您经常需要检查集合中是否包含某些对象。例如，您可能有一个禁止的Web地址列表。当有人输入新的网址时，您可能要检查它是否属于您的黑名单。或者，也许您有大量已使用的密码，并且想要检查建议的新密码是否属于此泄露密码列表的一部分。
解决此问题的标准方法是创建一些键值数据结构。如果您有足够的内存，则可以创建一个哈希表。或者您可能是一个很好的旧数据库。
但是，此类方法可能会使用过多的内存或速度太慢。因此，您想使用可以快速过滤请求的小型数据结构。例如，如果您有一个很小的数据结构可以可靠地告诉您您的密码肯定不在泄露的密码列表中，该怎么办？
实现这种过滤器的一种方法是计算所有对象的哈希值。散列值是您从对象生成的随机数，即相同的对象始终生成相同的随机数，而其他对象很可能生成其他数。因此，密码“Toronto”可能会映射到哈希值32。然后，您可以将这些小数字存储到键值存储中，例如哈希表。因此，您不需要存储所有对象。例如，您可以为每个可能的密码存储32位数字。如果您给我一个潜在的密码，我会检查其对应的32位值是否在列表中，如果不是，则告诉您它是安全的。因此，如果您给我“ Toronto”，我会检查表中是否有32。否则，我会将您的请求发送到更大的数据库，进行全面查找。我徒劳地发送给您以进行全面查找的概率称为“误报概率”。
尽管此哈希表方法可能很实用，但最终每个值可能使用4个字节。也许这太多了？Bloom过滤器可以解救。布隆过滤器的工作原理类似，不同之处在于您可以从对象中计算多个哈希值。您可以将这些哈希值用作位数组中的索引。将对象添加到集合中时，将与对象对应的所有位都设置为1。当您收到一个新对象并想要检查它是否属于该集合时，您只需检查是否所有位都已被设置。实际上，每个值将使用少于4个字节，并且仍然能够实现小于1％的下降正率。
尽管布隆过滤器是一种教科书算法，但它也有一些明显的缺点。一个主要的问题是它需要许多数据访问和许多散列值来检查对象是否是集合的一部分。简而言之，它并不是最理想的。
你能做得更好吗？是。除其他选择外，Fan等推出了布谷鸟Cuckoo过滤器，该过滤器比布隆过滤器占用的空间小，速度快。尽管实现Bloom过滤器是一个相对简单的练习，但是Cuckoo过滤器需要更多的工程设计。
在将代码限制为您可以掌握的东西的同时，我们还能做得更好吗？
事实证明，您可以使用Xor过滤器。我们刚刚发表了一篇名为“ Xor过滤器：比Bloom和Cuckoo过滤器更快，更小”的论文，该论文将发表在《实验算法学报》上。
我们还有一个优化的C版本，因为它是一个单头文件，所以可以轻松地集成到您的项目中。它大于300行，但是包含不同的替代方法，包括构建速度稍快的方法。我用C语言编写了一个小型示例，其中涉及到了密码检测问题。xor过滤器的构建时间要长一点，但是一旦构建，它会使用更少的内存，并且在某些演示测试中大约快25％。
我们也有Java和C ++实现。