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
