概述

布隆过滤器(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

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

草稿