如何快速判断某 URL 是否在 20 亿的网址 URL 集合中？

浅浅的花香味﹌ 2021-11-02 17:54 238阅读 0赞

点击上方“芋道源码”，选择“[设为星标][Link 1]”

做积极的人，而不是积极废人！

源码精品专栏

*  [中文详细注释的开源项目][Link 2]
 *  [RPC 框架 Dubbo 源码解析][RPC _ Dubbo]
 *  [网络应用框架 Netty 源码解析][Netty]
 *  [消息中间件 RocketMQ 源码解析][RocketMQ]
 *  [数据库中间件 Sharding-JDBC 和 MyCAT 源码解析][Sharding-JDBC _ MyCAT]
 *  [作业调度中间件 Elastic-Job 源码解析][Elastic-Job]
 *  [分布式事务中间件 TCC-Transaction 源码解析][TCC-Transaction]
 *  [Eureka 和 Hystrix 源码解析][Eureka _ Hystrix]
 *  [Java 并发源码][Java]

来源：http://rrd.me/ekN8q

*  何为布隆过滤器
    
     *  还是以上面的例子为例：
     *  判断逻辑：
     *  多次哈希：
 *  Guava的BloomFilter
 *  创建BloomFilter
    
     *  最终还是调用：
     *  使用:
 *  算法特点
 *  使用场景

--------------------

假设遇到这样一个问题：**一个网站有 20 亿 url 存在一个黑名单中，这个黑名单要怎么存？若此时随便输入一个 url，你如何快速判断该 url 是否在这个黑名单中？并且需在给定内存空间（比如：500M）内快速判断出**。

可能很多人首先想到的会是使用 `HashSet`，因为 `HashSet`基于 `HashMap`，理论上时间复杂度为：`O(1)`。达到了快速的目的，但是空间复杂度呢？URL字符串通过Hash得到一个Integer的值，Integer占4个字节，那20亿个URL理论上需要：`20亿*4/1024/1024/1024=7.45G`的内存，不满足空间复杂度的要求。

这里就引出本文要介绍的“布隆过滤器”。

# 何为布隆过滤器 #

百科上对布隆过滤器的介绍是这样的：

> 布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

是不是描述的比较抽象？那就直接了解其原理吧！

## 还是以上面的例子为例： ##

哈希算法得出的Integer的哈希值最大为：`Integer.MAX_VALUE=2147483647`，意思就是任何一个URL的哈希都会在0~2147483647之间。

那么可以定义一个2147483647长度的byte数组，用来存储集合所有可能的值。为了存储这个byte数组，系统只需要：`2147483647/8/1024/1024=256M`。

比如：某个URL（X）的哈希是2，那么落到这个byte数组在第二位上就是1，这个byte数组将是：000….00000010，重复的，将这20亿个数全部哈希并落到byte数组中。

## 判断逻辑： ##

如果byte数组上的第二位是1，那么这个URL（X）可能存在。为什么是可能？因为有可能其它URL因哈希碰撞哈希出来的也是2，这就是误判。

但是如果这个byte数组上的第二位是0，那么这个URL（X）就一定不存在集合中。

## 多次哈希： ##

为了减少因哈希碰撞导致的误判概率，可以对这个URL（X）用不同的哈希算法进行N次哈希，得出N个哈希值，落到这个byte数组上，如果这N个位置没有都为1，那么这个URL（X）就一定不存在集合中。

# Guava的BloomFilter #

Guava框架提供了布隆过滤器的具体实现：BloomFilter，使得开发不用再自己写一套算法的实现。

# 创建BloomFilter #

BloomFilter提供了几个重载的静态 `create`方法来创建实例：

public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions, double fpp);
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp);
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions);
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions);

## 最终还是调用： ##

static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy);
    // 参数含义：
    // funnel 指定布隆过滤器中存的是什么类型的数据，有：IntegerFunnel，LongFunnel，StringCharsetFunnel。
    // expectedInsertions 预期需要存储的数据量
    // fpp 误判率，默认是0.03。

BloomFilter里byte数组的空间大小由 `expectedInsertions`， `fpp`参数决定，见方法：

static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

真正的byte数组维护在类：`BitArray`中。

## 使用: ##

最后通过：`put`和 `mightContain`方法，添加元素和判断元素是否存在。

# 算法特点 #

1、因使用哈希判断，时间效率很高。空间效率也是其一大优势。2、有误判的可能，需针对具体场景使用。3、因为无法分辨哈希碰撞，所以不是很好做删除操作。

# 使用场景 #

1、黑名单 2、URL去重 3、单词拼写检查 4、Key-Value缓存系统的Key校验 5、ID校验，比如订单系统查询某个订单ID是否存在，如果不存在就直接返回。

--------------------

欢迎加入我的知识星球，一起探讨架构，交流源码。加入方式，**长按下方二维码噢**：

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

已在知识星球更新源码解析如下：

![640?wx\_fmt=png][640_wx_fmt_png]

![640?wx\_fmt=png][640_wx_fmt_png 1]

![640?wx\_fmt=png][640_wx_fmt_png 2]

**如果你喜欢这篇文章，喜欢，转发。**

**生活很美好，明天见(｡･ω･｡)ﾉ♡**

[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486188&idx=3&sn=f160d91ea23e5113e6077c500a2e30c4&chksm=fa49755dcd3efc4bf4f566fbbbf74c191d0b79f2d3222fd211bc52d80b5ef127f52b1158ed71&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486264&idx=1&sn=475ac3f1ef253a33daacf50477203c80&chksm=fa497489cd3efd9f7298f5da6aad0c443ae15f398436aff57cb2b734d6689e62ab43ae7857ac&scene=21#wechat_redirect
[RPC _ Dubbo]: https://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247484647&idx=1&sn=9eb7e47d06faca20d530c70eec3b8d5c&chksm=fa497b56cd3ef2408f807e66e0903a5d16fbed149ef7374021302901d6e0260ad717d903e8d4&scene=21#wechat_redirect
[Netty]: https://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247485054&idx=2&sn=9f3b85f7b8454634da6c5c2ded9b4dba&chksm=fa4979cfcd3ef0d9d2dd92d8d1bd8f1553abc6e2095a5d743e0b2c2afe4955ea2bbbd7a4b79d&token=55862109&lang=zh_CN&scene=21#wechat_redirect
[RocketMQ]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486256&idx=1&sn=81daccd3fcd2953456c917630636fb26&chksm=fa497481cd3efd97d9239f5eab060e49dea9876a6046eadba0effb878d2fb51f3ba5733e4c0b&scene=21#wechat_redirect
[Sharding-JDBC _ MyCAT]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486257&idx=1&sn=4d3c9c675f8833157641a2e0b48e498c&chksm=fa497480cd3efd96fe17975b0b8b141e87fd0a62673e6a30b501460de80b3eb997056f09de08&scene=21#wechat_redirect
[Elastic-Job]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486258&idx=1&sn=ae5665ae9c3002b53f87cab44948a096&chksm=fa497483cd3efd950514da5a37160e7fd07f0a96f39265cf7ba3721985e5aadbdcbe7aafc34a&scene=21#wechat_redirect
[TCC-Transaction]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486259&idx=1&sn=b023cf3dbf97e5da59db2f4ee632f5a6&chksm=fa497482cd3efd9402d71469f71863f71a6998b27e12ca2e00446b8178d79dcef0721d8e570a&scene=21#wechat_redirect
[Eureka _ Hystrix]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486260&idx=1&sn=8f14c0c191d6f8df6eb34202f4ad9708&chksm=fa497485cd3efd93937143a648bc1b530bc7d1f6f8ad4bf2ec112ffe34dee80b474605c22db0&scene=21#wechat_redirect
[Java]: http://mp.weixin.qq.com/s?__biz=MzUzMTA2NTU2Ng==&mid=2247486261&idx=1&sn=bd69f26aadfc826f6313ffbb95e44ee5&chksm=fa497484cd3efd92352d6fb3d05ccbaebca2fafed6f18edbe5be70c99ba088db5c8a7a8080c1&scene=21#wechat_redirect
[640_wx_fmt_jpeg]: /images/20211102/505245f5e07044ba9e6268724693d9f3.png
[640_wx_fmt_png]: /images/20211102/8752ac71bedd47b5aabf9a9027a78bc2.png
[640_wx_fmt_png 1]: /images/20211102/62e6ee61ac3244ca861982d8169fed14.png
[640_wx_fmt_png 2]: /images/20211102/b22ec718803c4459b95814a5c319812b.png