布隆过滤器与哈希

1.布隆过滤器

什么是布隆过滤器呢？它是一种类似哈希的数据结构，通过这个数据结构，可以快速的插入和查询，确定某个事件一定不存在或可能存在。特点是占用空间少，缺点是返回的结果是概率性，有一定误差，在方案选型时，需要注意这些特点。

2.布隆过滤器数据结构

布隆过滤器是一个bit向量或bit数组，如下图所示，bit的存储是耗内存，但是key的增加，反而不耗内存，因为不存储key。

当一个元素加入集合时，就通过K个hash函数将这个映射成一个位数组中的K个点，把它们置为1。当查询时，只要检查这些点是否全为1，就能判断集合中是否可能存在。

如果k个点有任何一个0，则被检元素一定不在。如果都是1，则很可能存在，这个期望概率是可以设置。

加入"baidu"，通过三个不同的哈希函数分别生成了哈希值1、4、7，则图如下所示:

类似上面，再存在一个值为"tencent"，如果三个不同哈希函数返回3、4、8，则如下图所示:

在第4个bit位时，被覆盖了。如果要查询"aaa"这个值是否存在，哈希函数返回了1、5、8三个值，结果第5个bit位上的值为0，则没有被映射，表面这个值不存在。而查询"baidu"，"tencent"就返回相应的bit位置均为1，就说明是存在。在海量数据时，也有可能一个不存在的值，结果相应的bit位返回1，这时不能判断这个值一定存在，这个就是误判率。

3.布隆过滤器误判概率

如果hash函数满足简单一致散列，每个元素都等概率地hash到m个slot中的任何一个，每个元素相互独立。若m为bit数，某一特定bit位在一个元素由某特定hash函数插入时没有被置位为1的概率为：

那相互独立的，k个hash函数中没有一个对其置位的概率为：

如果有n个元素，都没有将其其置位的概率为:

若对应某个待查询元素的k bits全部置位为1，则可判定其在集合中。将某元素误判的概率p为:

怎样把误判率减小呢？下图是一个数学推导。

当m增大或n减小时，误判率减小，实际是一般的m和n都是同时增大。k为何值时，误判率最低，下面是误判率的推导。当k=0.7*m/n，误判率最低，此时误判率如下图:


如果要想保持误判率不变。则应该满足这种关系，就是bit数m与被增加的元素n应该是线性同步增加。

4.使用布隆过滤器

设计布隆过滤器，就需要用户增加元素个数n，期望误差率p，hash种子，后面的所有参数，都由系统计算，并由此建立布隆过滤器。

根据传入的n和p，所需的内存大小m bit为:

再由m,n得到哈希函数的个数:

接下来再增加n个元素到布隆过滤器，再进行查询。根据前面的公式，当K最优时，如果设置p=%1时，存储每个元素需要9.6bit。m，n，p的三者的关系。

如果每次想将误判率降低为原来的1/10，则存储每个元素就需要增加4.8bits:

如果想通过表格查询，降低错误概率，则直接查询。布隆过滤器误判率表。

通过计算，对于5000万数量级，布隆过滤器，大概只占用200M的空间。

注意，在布隆过滤器算法中，如果发生了碰撞，不能删除该元素。当添加一个元素后，设置k个bit为1，且某个bit位碰撞后，如果删除元素时，恰恰设置该bit位为0，则碰撞的元素就无法判断，那么即不能在布隆过滤器中删除元素。

4.哈希表

哈希表主要是利用了数组的快速访问的特点，当存储的关键字比对应容量小时，这时哈希表会更加有效。哈希表是一种动态集合数据结构，在哈希表中查找一个元素的期望时间是o(1)。哈希表主要的问题就是如何解决冲突，如何设计更高效的哈希。

5.开放寻址法

当两个元素同时插入，因为哈希值一样，就有可能发生冲突，冲突就会增加误判率，所以设计的目的就需要尽可能降低冲突。

通常采用的冲突解决策略为开放寻址法，将所有的元素都存放在哈希表内的数组，不采用额外的数据结构。开发寻址法的最简单实现就是线性探查，步骤如下：

1.当插入新元素，使用哈希函数在映射在哈希表中的位置。

2.检查哈希表中，是否已经存在元素，如果该位置内容为空，则插入并返回，否则冲突，就需要解决冲突

3.如果当前的位置冲突了，那就检查下一个位置是否为空，如果被占用，那就检查下下个位置，一次类推，直到找到下一个内容为空的位置，然后插入。

线性探测方式虽然简单，但并不是最好的解决冲突的办法，会导致同类哈希的聚集。这导致搜索哈希表时，冲突依然存在。也就是搜索效率会降低。

针对线性探测，设计了一种改进的办法，就是二次探测。每次设置步长为平方倍数。如果位置i被占用，则首先检查i+12，然后依次检查i-12，i+22，i-22，依次类推，而不是像线性探测那样，以s+1，s+2…方式增长，虽然有所改进，但是二次探测同样也会导致同类哈希聚集的问题。

基于上面两种办法的缺点，设计了一种办法叫，二度哈希。其原理是，由多个哈希函数H1…Hn的集合，当需要从哈希表中添加或获取元素时，如果发生冲突，首先使用H1，在尝试使用H2，依次类推，直到不发生冲突为止。H1到Hn的哈希函数都是类似的，不同的可能是相应的函数系数可能不一样。

二度哈希，保证探测后，哈希表中的每个位置都有且只有一次被访问到。意思就是，对于给定
的key，哈希表的同一个位置不会同时使用Hi和Hj，保证所算的哈希值没有共同的因子。二度哈希使用了O(m2)种探测序列，而线性和二次探查使用了O(m)种探查序列，探测序列更多了，故二度哈希提供了更好的避免冲突的策略。

向哈希表中添加新元素时，需要检查以保证插入元素与空间大小的比例合理，如果超过太多，哈希表将会被扩容。扩容的步骤如下:

1.哈希表的位置空间几乎被翻倍，位置空间可能从当前的素数值增加到下⼀个最⼤的素数值。

2.当扩容了，由于元素将依赖于哈希表的位置空间，所以表中所有值也需要重新二度哈希，这样会带来性能损耗。

由此可见，二度哈希解决了搜索的冲突，但是如果发生扩容，性能会降低。所以在设计时，最好能够预估可能容纳的元素数量(实际生产环境是很难预估计)，在初始化哈希表时，给予合适的值进行构造，避免性能下降。

6.连接技术

使用连接法，把冲突后的元素，放到同一个链表中。

链接技术是采用了额外的数据结构来处理冲突，解决了二度哈希的缺点，扩容导致所有的哈希值被重新计算。当发生冲突时，冲突的元素(哈希值一样)将被添加到链表中。

这种模式有两个缺点，一是海量数据时，内存占用空间大。二是当大量冲突发生时，有可能会退回为链表，遍历会带来比较大的开销。

在设计时，元素的总数最好不要超过数组的总数，这样可以保证遍历数组时间保证在O(1)。

7.哈希函数设计

除法哈希用一个特定的质数(m)来除所给的关键字(key)，所得余数就是该关键字的哈希值。前提是保证质数与关键字分布的任何模式都是无关的。

除法哈希函数可表示为:

hash(key) = key mod m

乘法哈希用哈希表的大小m(一般选择m为2的指数幂次)，[A * key mod 1] 表示将 key 乘上某个在 0~1 之间的数并取乘积的⼩数部分，该表达式等价于[A*key - floor(A * key)]。

表达式为:

hash(key) = floor( m * ( A * key mod 1) )

有些论文中，认为A的值选择黄金分割点，(√5-1)/2 = 0.618 033 988比较好。实际的设计中，以自己的需求去设计调整这个A值。

全域哈希防止退化为链表，随机选择哈希函数，保证对于任何一个元素，都有一个平均运行的情况。

hasha,b(key) = ((a*key + b) mod p) mod m，p为一个足够大的质数，关键字key都落在0到p-1的范围内，m为哈希表的大小，a∈{1,2,3,…,p-1}，b∈{0,1,2,…,p-1}。

完美哈希的基本思想是利用两级的哈希策略，而每一级上都是用全域哈希。

如图所示，第一级与使用链接技术的哈希表基本一样，第二级不使用链表的结构，而采用二次哈希表S 和相关的哈希函数h，随机的选取哈希函数h，可以确保在第二级上不出现哈希冲突。如果利⽤从⼀个全域哈希函数族中随机选择的哈希函数 h，将 n 个关键字存储在⼀个⼤⼩为 m = n 2的哈希表中，那么出现碰撞的概率⼩于 1/2 。

为了防止第二级上不出现哈希冲突，需要让哈希表S的大小m为哈希到槽j中的关键字数n的平方。这种也有可能会占用比较大的存储空间。如果关键字的数量n等于槽的数量m，则该哈希函数称为最小完美哈希函数。

8.布隆过滤器与HashMap

hashmap主要存在的问题，就是存储容量占比高，而且通常空间是不能被用满，利用率不高。而布隆过滤器是占用空间少，这在海量数据时，优点尤为突出。布隆过滤器在误差万分之一的情景下，1000万数据量时，布隆过滤器仅仅为23M。

9.布隆过滤器与HashTable

哈希表的存储效率一般只有50%（为了避免高碰撞，一般哈希存到一半时都翻倍或采取其他策略），所以很费内存。面临的最大问题就是冲突，假设哈希函数良好，如果哈希表长度为M，如果想将冲突率降低到1%，则这个散列表就只能容纳M/100个元素。这时候可以用k>1的布隆过滤器，k个函数将每个元素置为k个bits，如果参数选型合适，冲突和误判会大大降低。

今天就分享到这里，如果这篇文章对你有帮助，欢迎转发，点赞，关注。