硬核 | Redis 布隆（Bloom Filter）过滤器原理与实战（redisson 布隆过滤器）

 

#一、简介布隆过滤器（Bloom Filter）是一种数据结构，用于快速检查一个元素是否属于某个集合中它可以快速判断一个元素是否在一个大型集合中，且判断速度很快且不占用太多内存空间布隆过滤器的主要原理是使用一组哈希函数，将元素映射成一组位数组中的索引位置。

当要检查一个元素是否在集合中时，将该元素进行哈希处理，然后查看哈希值对应的位数组的值是否为1如果哈希值对应的位数组的值都为1，那么这个元素可能在集合中，否则这个元素肯定不在集合中由于哈希函数的映射可能会发生冲突，因此布隆过滤器可能会出现误判，即把不在集合中的元素判断为在集合中。

但是，布隆过滤器不会漏判，即不会把在集合中的元素判断为不在集合中

如何添加数据？布隆过滤器的数据添加过程主要分为以下几个步骤：创建一个位数组，初始化所有位为0设定k个哈希函数对要添加的元素进行k次哈希操作，得到k个哈希值将位数组中这k个位置的值都设为1举个例子，假设要将字符串"hello world"添加到布隆过滤器中，该布隆过滤器使用3个哈希函数，位数组大小为10，步骤如下：。

创建一个大小为10的位数组，初始化所有位为0设定3个哈希函数，如下：哈希函数1：将字符串转化为一个整数，然后将整数对10取余哈希函数2：将字符串中的每个字符的ASCII码值相加，然后将和对10取余哈希函数3：将字符串翻转，然后将翻转后的字符串转化为一个整数，然后将整数对10取余。

对字符串"hello world"进行3次哈希操作，得到3个哈希值分别为2、5、8将位数组中2、5、8这3个位置的值都设为1添加完数据后，当检查某个元素是否在布隆过滤器中时，只需要进行和添加数据相同的哈希函数操作，检查对应的位数组的值是否为1即可。

如果所有哈希函数操作对应的位数组值都为1，那么该元素可能在集合中，如果其中任何一个位数组值为0，则该元素一定不在集合中

如何查询数据？布隆过滤器的数据查询过程主要分为以下几个步骤：1.对要查询的元素进行k次哈希操作，得到k个哈希值2.查位数组中这k个位置的值是否都为13.如果这k个位置的值都为1，则认为该元素可能在集合中；否则，认为该元素一定不在集合中。

举个例子，假设布隆过滤器中已经添加了字符串"hello world"，布隆过滤器使用3个哈希函数，位数组大小为10，查询字符串"hello"是否在布隆过滤器中，步骤如下：1.对字符串"hello"进行3次哈希操作，得到3个哈希值分别为2、5、8。

2.检查位数组中2、5、8这3个位置的值是否都为13.如果这3个位置的值都为1，则认为字符串"hello"可能在集合中由于布隆过滤器可能会出现误判，因此在实际应用中，需要根据具体的应用场景来确定误判率的可接受范围，并相应地设置哈希函数数量和位数组大小。

同时，需要注意，布隆过滤器无法删除已添加的数据#二、布隆过滤器优缺点布隆过滤器的优点包括：1.时间和空间效率高：布隆过滤器的时间复杂度和空间复杂度都是O(k)，其中k为哈希函数的数量因此，它可以在较小的空间内快速判断某个元素是否在集合中。

2.误判率低：布隆过滤器虽然可能出现误判，但是误判率可以通过调整哈希函数数量和位数组大小来控制，可以根据实际需求进行调整3.支持高并发：布隆过滤器支持并发查询和添加数据，可以在多线程环境下使用4.易于实现：布隆过滤器的实现比较简单，只需要实现几个哈希函数和一个位数组即可。

布隆过滤器的缺点包括：1.无法删除已添加的数据：由于布隆过滤器的哈希函数不具有逆向性，所以无法删除已添加的数据2.误判率无法避免：由于布隆过滤器的设计原理，误判率无法避免当哈希函数的数量不足或位数组的大小不够时，误判率可能会很高。

3.无法精确判断元素是否存在：由于布隆过滤器的设计原理，无法精确判断某个元素是否在集合中，只能判断它可能存在或一定不存在。

#三、减少布隆过滤器的误判布隆过滤器的误判率是根据哈希函数的数量和位数组大小来确定的如果哈希函数的数量太少或者位数组太小，那么误判率会增加反之，如果哈希函数的数量太多或者位数组太大，那么可能会导致空间浪费和查询效率降低。

因此，在实际使用中，需要根据具体的应用场景来确定哈希函数数量和位数组大小，以达到误判率和空间利用率的平衡除了调整哈希函数数量和位数组大小之外，还可以采用以下方法来减少布隆过滤器的误判率：1.使用多个布隆过滤器：将同一个元素添加到多个布隆过滤器中，查询时需要在所有布隆过滤器中查询。

这种方法可以显著降低误判率，但是会增加存储空间和查询时间2.使用加密哈希函数：加密哈希函数可以使哈希值更难以预测，从而减少哈希冲突的概率常见的加密哈希函数包括MD5、SHA-1等3.使用高质量的哈希函数：使用高质量的哈希函数可以减少哈希冲突的概率。

常见的高质量哈希函数包括MurmurHash、CityHash等4.对于数据量较小的情况，可以使用简单的线性查找代替布隆过滤器，这样可以避免误判率过高的问题需要注意的是，误判率是布隆过滤器的本质限制，无法完全避免。

因此，在使用布隆过滤器时，需要根据实际需求来平衡误判率和空间利用率，同时采用多个布隆过滤器、使用高质量的哈希函数等方法来尽量减少误判率#四、使用场景1.缓存系统缓存系统是一个常用的场景，布隆过滤器可以用来判断某个数据是否在缓存中。

在实际操作中，可以先将缓存中的所有数据放入布隆过滤器中，然后查询时先查询布隆过滤器如果查询结果表明该数据不存在，就说明该数据不在缓存中，需要从磁盘或者数据库中获取如果查询结果表明该数据存在，就可以直接从缓存中获取，无需进行磁盘或数据库的访问。

下面是一个使用布隆过滤器进行缓存判断的Java代码示例：import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels;

// 创建一个布隆过滤器BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(), 1000000, 0.001); // 将缓存中的所有数据加入布隆过滤器

for (String key : cache.keys()) { bf.put(key); } // 查询缓存中是否存在某个数据if (bf.mightContain(key)) { value = cache.

get(key); } else { value = getFromDiskOrDatabase(key); } 2.网络爬虫网络爬虫是另一个常用的场景，布隆过滤器可以用来去重已经爬取过的URL。

在实际操作中，可以将已经访问过的URL放入布隆过滤器中每当需要访问一个新的URL时，先查询布隆过滤器如果查询结果表明该URL已经存在，就说明该页面已经被爬取过，可以忽略如果查询结果表明该URL不存在，就说明该页面尚未被爬取过，需要进行访问。

下面是一个使用布隆过滤器进行网络爬虫去重的Java代码示例：import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels;

// 创建一个布隆过滤器 BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(), 1000000, 0.001); // 将已经访问过的URL加入布隆过滤器

for (String url : visitedUrls) { bf.put(url); } // 访问新的URL时先查询布隆过滤器if (bf.mightContain(url)) { skipVisit(url); }

else { visit(url); } 3.数据库系统数据库系统是另一个常用的场景，布隆过滤器可以用来加速数据库查询在实际操作中，可以将数据库中的所有关键字放入布隆过滤器中每当需要查询某个关键字时，先查询布隆过滤器。

如果查询结果表明该关键字不存在，就可以直接返回查询结果为空，无需进行数据库的访问如果查询结果表明该关键字存在，就需要进行数据库的访问，查询具体的数据下面是一个使用布隆过滤器进行数据库查询加速的Java代码示例：。

javaCopy codeimport com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; // 创建一个布隆过滤器

BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(), 1000000, 0.001); // 将数据库中的所有关键字加入布隆过滤器

for (String keyword : database.keywords()) { bf.put(keyword); } // 查询关键字时先查询布隆过滤器if (bf.mightContain(keyword)) { results = database.query(keyword); }

else { results = new ArrayList<>(); } 4.分布式系统分布式系统是另一个常用的场景，布隆过滤器可以用来快速地判断某个元素是否在分布式系统中在实际操作中，每个节点都可以维护一个布隆过滤器。

当需要查询某个元素是否在分布式系统中时，可以将查询请求发送到所有节点，并在每个节点上查询布隆过滤器如果查询结果表明该元素存在于任意一个节点中，就可以直接返回查询结果为真，无需进行进一步的操作如果查询结果表明该元素不存在于任何一个节点中，就可以直接返回查询结果为假，无需进行进一步的操作。

下面是一个使用布隆过滤器进行分布式系统元素查询的Java代码示例：javaCopy codeimport com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels;

// 每个节点维护一个布隆过滤器 BloomFilter bf = BloomFilter.create(Funnels.stringFunnel(), 1000000, 0.001);

for (String element : elements) { bf.put(element); } // 查询元素时将查询请求发送到所有节点for (Node node : nodes) {

if (node.bf.mightContain(element)) { returntrue; } } returnfalse; 5.Redisson组件Redis实现布隆过滤器的底层就是通过bitmap这种数据结构，在Java中提供了一个客户端工具Redisson组件，它内置了布隆过滤器，可以让程序员非常简单直接地去设置布隆过滤器。

Config config = new Config(); config.useSingleServer().setAddress("redis://192.168.x.x:6379"); config

.useSingleServer().setPassword("xxx"); RedissonClient redisson = Redisson.create(config); RBloomFilter bloomFilter = redisson.getBloomFilter(

"nameBloom"); bloomFilter.tryInit(100000000L,0.01); bloomFilter.add("zzx"); System.out.println(bloomFilter.contains(

"fj")); System.out.println(bloomFilter.contains("zzx")); guava工具包BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),

10000000,0.03); bloomFilter.put("zzx"); System.out.println(bloomFilter.mightContain("fj")); System.

out.println(bloomFilter.mightContain("zzx"));