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的概率：
$$
1 - \frac{1}{m} \
$$
那么在所有k次hash操作后该位都没有被置为1的概率：
$$
(1 - \frac{1}{m})^k \
$$
插入n个元素后，某一位仍然为0的概率：
$$
(1 - \frac{1}{m})^{k \times n} \
$$
那么，任意一位为1的概率：
$$
1 - (1 - \frac{1}{m})^{k \times n} \
$$
误差率即k个位置都为1的概率：
$$
[1 - (1 - \frac{1}{m})^{k \times n}]^k \
= (1 - e^{-\frac{k \times n}{m}})^k \
$$

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

$$
对于 f(k) = (1 - e^{-\frac{m}{n}})，求其值最小时的k值。 \
$$
过程如下：

$$
令e^{\frac{n}{m}}=b，则f(k) = (1-b^{-k})^k \
$$

$$
等式两边取对数，\ln f(k) = k \times \ln (1-b^{-k}) \
$$

$$
等式两边求导数，\frac{1}{f(k)} \times {f^{‘}(k)} = \ln(1-b^{-k}) + k \times {\frac{1}{1-b^{-k}} \times (-b^{-k}) \times \ln (b) \times (-1)} \
$$

$$
简化，\frac{f^{‘}(k)}{f(k)} = \ln(1-b^{-k}) + k \times {\frac{b^{-k} \ln b}{1-b^{-k}}} \
$$

$$
令f^{‘}(k) = 0，则\ln(1-b^{-k}) + k \times {\frac{b^{-k} \ln b}{1-b^{-k}}} = 0 \
$$

$$
令1-b^{-k}=a，则b=-\frac{\ln (1-a)}{k} \
$$

$$
上式转化为，\ln a + {k} \times {\frac{(1-a) \times ({-\frac{1}{k}}) \times {\ln (1-a)}}{a}} = 0 \
$$

$$
简化，a \ln a = (1 - a) \ln (1-a) \
$$

$$
根据g(x) = xlnx的特性，a = 1 - a => a = \frac{1}{2} \
$$

$$
从而，1 - b^{-k} = \frac{1}{2} => b^{-k} = \frac{1}{2} \
$$

$$
所以，k = \frac{m}{n} \ln 2 \
$$

hash

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

哈希函数	时间(ns)	冲突个数	总个数
SDBMHash	158062897	180	1000000
SimMurMurHash	144356292	108	1000000
JSHash	160829523	230	1000000
PJW	169142421	3901	1000000
MurMurHash2	144678973	129	1000000
ELFHash	173966075	3901	1000000
BKDRHash	160517055	258	1000000
CalcNrHash	180425843	124	1000000
APHash	166644369	245	1000000
BPHash	144647091	920005	1000000
FNVHash	160584860	109	1000000
RSHash	160316468	240	1000000
DJB	185411123	97	1000000
DJB2Hash	151799803	97	1000000
DEKHash	145856752	119	1000000
SipHashNoCase	205930199	126	1000000
SipHash	187972639	126	1000000