Bloom Filter(布隆过滤器)
是由 Bloom 再1970年提出的一种多哈希函数映射的快速查找算法。是一种空间效率很高的随机数据结构,可以看作是对 bit-map 的扩展。
#####原理是:
当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射为一个位阵列(Bit Array) 中的 K 个点,把他们置为 1**
。检索时,我们只要看看这些点是不是都是1就大概知道集合中有没有它了:
- 如果这些点有任何一个0,则被检索元素一定不在;
- 如果都是1,则被检索元素很可能在。
通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。通过极少的错误换取了存储空间的极大节省。
#####算法如下:
创建一个 m 位BitSet,现将所有位初始化为0,然后选择 K 各不同的哈希函数。第 i 个哈希函数对字符串 str 哈希的结果记为 h(i, str),且 h(i, str) 的范围是0到 m-1。
#####优点: 空间和时间都有巨大的优势。存储、插入和查询时间都是常数。
#####缺点:
- 误算率;
- 不能从布隆过滤器中删除元素,因为查找都不准确,因此删除也就是问题。