BloomFilter

概述

布隆过滤器（Bloom Filter）是布隆在1970年提出的，它实际上是由一个很长的bit数组和一系列hash函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询效率都远远超出一般的算法，缺点是存在误差和删除困难。

原理

数组的每个元素都只占1bit空间，并且每个元素只能为0或1。
布隆过滤器还拥有K个哈希函数，当一个元素加入到布隆过滤器时会使用k个hash函数对其进行k次计算，得到k个哈希值，并且根据得到的哈希值，在位数组中把对应下标的值置为1。

判断某个元素是否在布隆过滤器中，就对钙元素进行k次哈希计算，得到的值在位数组中判断每个元素是否都为1，如果每个元素都为1，就说明这个值在布隆过滤器中。

误差

假设 hash 函数以等概率条件选择并设置 Bit Array 中的某一位，m 是该位数组的大小，k 是 hash 函数的个数。

位数组中某一特定的位在进行元素插入时的hash操作中没有被置为1的概率：

那么在所有k次hash操作后该位都没有被置为1的概率：

插入n个元素后，某一位仍然为0的概率：

那么，任意一位为1的概率：

误差率即k个位置都为1的概率：

那么求误差最小时的k值，问题就转化为：

过程如下：

hash

不同的哈希函数对于随机字符的测试结果如下：

经过很多素材的测试，最终选择了MurmurHash2函数。

草稿