布隆过滤器 ## 布隆过滤器的原理介绍 ###当一个元素加入布隆过滤器中的时候,会进行如下操作: 1. 使用布隆过滤器中的哈希函数对元素值进行计算,得到哈希值(有几个哈希函数得到几个哈希值)。 2. 根据得到的哈希值,在位数组中把对应下标的值置为1。 ### 当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作: 1. 对给定元素再次进行相同的哈希计算; 2. 得到值之后判断位数组中的每个元素是否都为 1,如果值都为 1,那么说明这个值可能在布隆过滤器中,如果存在一个值不为 1,说明该元素肯定不在布隆过滤器中。这句话需要解释一下,因为他是通过哈希计算的,不同的值通过哈希计算,得到的哈希值有可能是一样的,比如说a,b通过计算,得到的哈希索引都为10,一开始库里有a,但是没有b,然后索引10这个位置就有数据,但是我查b的的时候,在布隆过滤器中就能找到值,就出现问题了,所以上面那句话,只能说明查询的值可能在布隆过滤器中,那么这个问题要怎么解决呢,那我们就多次不同哈希计算,这样两个值重复的可能性就小很多了,那后面查询的值多次哈希之后,只要在布隆过滤器中有一个为0,那就肯定不存在,这就是后面的那句话的意思了