Bloom Filter 介绍（Bloom Filters by Example）

基础

Bloom filter 是一个数据结构，它可以用来判断某个元素是否在集合内，具有运行快速，内存占用小的特点。
而高效插入和查询的代价就是 Bloom Filter 是一个概率数据结构: 它可以告诉我们一个元素绝对不在集合内或者可能在集合内。下面是一个简单的示例

高级话题

哈希函数

Bloom filter 里的哈希函数需要是彼此独立的，正规的，分布式的。同时，它们需要尽可能快的运行速度（例如 sha1 之类的密码学哈希就不是一个特别好的选择）。
快速简单的哈希函数有 murmur，fnv系列和 Jenkins 哈希。

Double Hashing

同时，你不需要同时选取两个或多个不同的哈希函数。而是使用 double Hashing 来创建无穷多的哈希函数。给定两个彼此独立的哈希函数 hash_a 和 hash_b，可以通过如下的哈希函数创建一个新的哈希函数：
hash_i(x, m) = (hash_a(x) + i * hash_b(x)) mod m

Bloom filter 应该设计为多大？

Bloom filter 的一个优良特性就是可以修改过滤器的错误率。一个大的过滤器会拥有比一个小的过滤器更低的错误率。
错误率会近似于(1 - e^-kn/m)^k，所以你只需要先确定可能插入的数据集的容量大小，然后再对k 和m进行参数调优。
而这带来了一个显而易见的问题。

应该使用多少个哈希函数？

Bloom filter 使用的哈希函数越多运行速度就会越慢。但是如果哈希函数过少，又会遇到误判率高的问题。
在创建一个 Bloom filter 的时候需要确定k的值，也就是说你需要提前圈定n的变动范围。而一旦你这样做了，你依然需要确定m（总比特数）和k（哈希函数的个数）的值。
似乎这是一个十分困难的优化问题，但幸运的是，对于给定的m和n，有一个函数可以帮我们确定最优的k值：(m/n)ln(2)
所以可以通过以下的步骤来确定 Bloom filter 的大小：
1. 确定n的变动范围
2. 确定m的值
3. 计算k的最优值
4. 对于给定的n, m, k计算错误率。如果这个错误率不能接收，那么回到第二步，否则结束

Bloom filter 的时间复杂度和空间复杂度

对于一个m和k值确定的 Bloom filter，插入和测试操作的时间复杂度都是 O(k)。这意味着每次你想要插入一个元素或者查询一个元素是否在集合中，只需要使用k个哈希函数对这个元素求值，然后将对应的比特位标记或者检查对应的比特位。
相比之下，Bloom filter 的空间复杂度更难以概述，它取决于你可以忍受的错误率。同时也取决于输入元素的范围，如果这个范围是有限的，那么一个确定的比特向量就可以很好的解决问题。如果你甚至不能很好的估计输入元素的范围，那么你最好选择一个哈希表或者一个可拓展的 Bloom filter。

更多链接

1. 中文版 Github 链接
2. Bloom Filters by Examples

最后

以上就是直率大碗为你收集整理的Bloom Filter 介绍（Bloom Filters by Example）的全部内容，希望文章能够帮你解决Bloom Filter 介绍（Bloom Filters by Example）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。