原理
用bit数组来代替数据信息。先分别对原始数据的集合里每个元素进行多次hash运算,然后进行数组长度取模,取模的值就是该数据在bit数组对应位置,且位置的bit值设为1。
图解
例如bit数组长度为9,hash函数有3个,添加了两个数据:
特性一:如果判断不存在,那就是肯定不存在
特性二:如果判断存在,实际不一定存在(误判)
使用场景
判断key是否存在、黑名单等
Java中可以使用Google Guava工具包提供的工具
用bit数组来代替数据信息。先分别对原始数据的集合里每个元素进行多次hash运算,然后进行数组长度取模,取模的值就是该数据在bit数组对应位置,且位置的bit值设为1。
例如bit数组长度为9,hash函数有3个,添加了两个数据:
判断key是否存在、黑名单等
Java中可以使用Google Guava工具包提供的工具