- 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
针对这种情况我们可以添加更多的比特位,缓解这种情况的发生