编程知识
布隆过滤器算法原理
  • By刘立博
  • 2020-03-07 20:45:34
  • 938人已阅读

假定我们需要添加两个元素KEY1和KEY2,比特位16个,无偏HASH函数3个

 

添加元素

(1)对KEY1进行3次HASH运算,得到HASH值3、8、D,并将对应的比特位置为1

(2)同理对KEY2进行3次HASH运算,得到HASH值2、8、F,并将对应比特位置1

判断是否存在

判断KEY是否存在的算法与添加类似,使用无偏HASH函数计算出HASH值,查找对应比特位是否均为1即可判断KEY是否存在

 

假定:

KEY1经过3个无偏HASH函数得出的HASH值为2、8、D

KEY3 HASH值为1、8、D

 

查找对应特比位可知:

KEY1存在、KEY3不存在

 

误差

 

HASH冲突

如果有一个未添加过的元素KEY4,他经过HASH计算得出的值为2、8、D

针对这种情况,我们可以增加无偏HASH函数,减少HASH冲突的概率

比特位满

如果添加了非常多的元素,使得所有比特位均被置为1,从而导致对任意元素的判断都返回true

针对这种情况我们可以添加更多的比特位,缓解这种情况的发生