BloomFilter是用来判断,某元素是否曾经来访过的有状态数据结构。
优点:
1.写入、查询效率都非常高,得益于元素在写入、查询的寻址过程,采用的都是n个hash函数,其时间复杂度是O(1).
2.另外,底层用于存储状态的是bitArray结构,非常省空间。
缺点:
1.对于两个不同元素,由于hash碰撞无法避免,且底层用的bit表示状态,所以通过n个hash函数计算后可能落在相同的slot上。所以结果只是一个概率性的表征,不保证百分百的准确。
- 初始化时:底层bitArray每个slot的vavlue默认全为
0
。 - 插入时:将元素e,经过n个不同的hash函数计算,散落到bitArray上的n(若不同hash函数的计算结果发生重复,可能小于n)个slot上,对应slot上的value设为
1
。 - 查询时:将元素e,经过n个不同的hash函数计算,对应到bitArray上的slot,分别取出这些slot上的value,若全部value都为
1
,则返回true,否则返回false。