Java面试八股之什么是布隆过滤器
- 什么是布隆过滤器
布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，用于判断一个元素是否可能存在于一个集合中。布隆过滤器可以给出“可能存在”或“一定不存在”的答案，但不能保证“一定存在”。其主要特点是：
空间效率高：相比于其他数据结构（如哈希表），布隆过滤器使用较少的内存空间就能表示一个非常大的集合。
存在误判：由于其概率性特性，布隆过滤器有可能将实际上不在集合中的元素判断为“可能存在”，这就是所谓的假阳性（False Positive）。但它不会出现假阴性（False Negative），即如果布隆过滤器判断一个元素“一定不存在”，那么这个元素肯定不在集合中。
不可删除：一旦元素加入布隆过滤器，无法从过滤器中删除，因为删除可能导致其他元素的判断结果出错。
布隆过滤器的内部结构是一个固定大小的二进制位数组和一组哈希函数。当向布隆过滤器中添加元素时，使用哈希函数计算该元素的多个哈希值，然后将位数组中对应位置的比特位设置为1。查询元素是否存在时，再次使用同样的哈希函数计算哈希值，并检查位数组中相应位置的比特位是否全为1。如果存在任何一个位为0，则可以确定元素不在集合中；如果所有位均为1，则认为元素可能在集合中。
如何使用布隆过滤器防止Redis缓存穿透：
缓存穿透是指查询的数据在数据库中不存在，因此缓存中也没有相应数据。攻击者或异常请求持续查询这样的数据，会导致大量请求直接打到数据库，给数据库带来不必要的压力。布隆过滤器可以用来提前拦截那些数据库中必然不存在的数据查询，从而防止缓存穿透。
具体做法如下：
初始化布隆过滤器：根据预期数据规模和可接受的误判率，确定布隆过滤器的大小（位数组长度）和哈希函数数量。在Redis中，可以使用专门的布隆过滤器插件（如RedisBloom）或者使用Redis的基本数据结构（如Bitmaps）模拟实现。
填充布隆过滤器：将数据库中已有的所有数据通过哈希函数映射到布隆过滤器中，将对应位置的比特位设置为1。这样，对于数据库中存在的任何数据，布隆过滤器都应该返回“可能存在”。
查询前预过滤：在查询数据时，先通过布隆过滤器进行判断。如果布隆过滤器返回“一定不存在”，则直接返回空结果给客户端，不再访问数据库和缓存。如果返回“可能存在”，则继续查询缓存和数据库。
如果缓存中有数据，直接返回；
如果缓存中没有数据，查询数据库。如果数据库中存在数据，将其写入缓存；如果数据库中也不存在数据，则根据具体情况决定是否将一个特殊标记（如“NULL”或“NOT_FOUND”）写入缓存以短暂抵挡后续相同查询。
通过这种方式，布隆过滤器充当了数据库查询的前置屏障，对那些数据库中必然不存在的数据请求进行了有效拦截，大大减少了数据库的无效查询，从而防止了缓存穿透现象的发生。需要注意的是，由于布隆过滤器存在误判的可能，某些情况下可能会将实际存在的数据误判为不存在，因此在设计时应合理权衡误判率与空间效率。在大多数场景下，少量的误判是可以接受的，因为它通常不会影响业务逻辑，而且可以通过调整布隆过滤器参数（如增大位数组大小或增加哈希函数数量）来降低误判率。
如果大家需要视频版本的讲解，欢迎关注我的B站：
原文地址：https://blog.csdn.net/u012151345/article/details/140322755
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！