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