布隆过滤器揭秘 让URL黑名单存储从640GB增加到35.88GB！

1.引言

大家好，我是小米，一个热爱分享技术的小同伴。当天我们来聊一聊在实践上班中如何经常使用布隆过滤器（Bloom Filter）来处置大规模URL黑名单的存储和查征询题。

2.疑问背景

假定我们有一个规模到达100亿的黑名单URL汇合，每个URL的长度为64字节。如何高效地存储和查问这个黑名单呢？

3.散列表方法

我们先思考一下惯例的散列表方法。假设经常使用HashMap来存储这些URL：

显然，这样的存储需求是无法行的，由于它对内存的要求太高。

4.布隆过滤器引见

这时刻，我们可以引入布隆过滤器，它是一种高效的概率型数据结构，用于检测一个元素能否属于一个汇合。布隆过滤用具备以下特点：

5.布隆过滤器原理

布隆过滤器由一个很长的二进制位数组和一系列随机映射函数（哈希函数）组成。

拔出元素

当一个元素参与布隆过滤器时，口头以下步骤：

查问元素

查问一个元素能否在布隆过滤器中时，口头以下步骤：

6.计算布隆过滤器参数

为了更好地理解布隆过滤器的存储效率，我们须要计算以下参数：

假定我们准许的误判率为0.01%，我们可以经常使用以下公式来计算m和K：

其中，n是汇合中的元素数量，p是准许的误判率。

详细计算如下：

代入公式：

经过计算，我们得出位数组的长度为287亿bit（约合35.88GB），须要20个哈希函数。这样，布隆过滤器的内存占用从原来的640GB大幅增加到了35.88GB，且具备较高的查问效率。

7.布隆过滤器的成功

上方是布隆过滤器的Java成功，包含初始化、参与元素和查问元素的代码。

代码说明

这个成功经常使用了MD5哈希函数，可以依据需求选用其余哈希函数。经过调整位数组大小和哈希函数数量，可以在存储效率和误判率之间取得平衡。

布隆过滤器作为一种高效的概率型数据结构，能够在大规模数据集上成功高效的存储和查问，特意实用于URL黑名单这样的场景。经过正当地选用位数组长度和哈希函数数量，我们可以在保障较低误判率的前提下，大幅增加内存经常使用。