数据结构第二季 Day21 布隆过滤器

1、如果要判断一个元素是否存在，使用哈希表有什么优缺点？

• 优点：哈希表判断一个元素是否存在的时间复杂度是 O(1) 级别，效率特别高
• 缺点：哈希表为了减少哈希冲突，通常数组的长度会大于元素个数，所以哈希表的空间利用率不高，需要占用比较多的内存资源。

image.png

2、哈希表不是还有链表或者红黑树结构吗？那为什么还说查找是 O(1) 级别？

• 哈希表有一个较小的装填因子以及扩容方式，从而保证较少的哈希冲突。
• 在此前提下，可以忽略链表或者红黑树的查找时间，所以可以认为时间复杂度是 O(1) 级别。

3、既然哈希表有如上缺点，那么如果要经常判断元素是否存在于大批量数据中，有什么好办法吗？

• 既要保证查询效率，又要提高内存使用率。
• 当然是考虑布隆过滤器

4、布隆过滤器的英文名字是什么？优缺点是什么？

• Bloom Filter
• 优点：空间效率和查询时间都远远超过一般的算法
• 缺点：有一定的误判率、删除困难

5、使用布隆过滤器的三个前提条件时什么？

• ①经常要判断某个元素是否存在
• ②元素数量巨大，希望用比较小的内存空间
• ③允许有一定的误判率

6、简述布隆过滤器的原理？

image.png

7、布隆过滤器的误判率计算？

image.png

二、布隆过滤器代码实现细节

1、布隆过滤器的接口实现，主要有哪两个接口？

image.png

2、为什么布隆过滤器不提供删除功能？

• 因为布隆过滤器是为了保证查询和存储的高效性能，存储的是多个哈希函数的结果（二进制数据）
• 在进行删除操作的时候，很容易会影响到其他值的哈希结果值。

3、如果一定要布隆过滤器提供一个删除功能，有什么思路？（意义不大，但是扩展思路用）

• 可以把存储的二进制数据改成 整型（当成引用计数器使用），但是这样就让空间利用率降低了很多。
• 同一个位置，每增加一次，引用计数值+1
• 同一个位置，每删除一次，引用计数值-1

4、一个向上取整的小技巧（不使用自带函数 ceil）

image.png