如何判断 URL 是否存在于有 100 亿个 URL 的黑名单中

题目描述

有 100 亿个黑名单 URL,每个 URL 的空间占用 64 B。想要实现一个判断 URL 是否在黑名单上的功能。

思路分析

有一定算法的基础的朋友,可能会很快的想到使用哈希表来存储 URL,因其可以实现快速查找。

但是仔细想想你心中一惊,这可不是一个易事的任务。

100 亿 * 64 B 约等于 600 GB,所以整个黑名单占据了巨大的存储空间。

但是你并没有被吓倒,因为你知道这是一个绝佳的机会展现自己的能力和智慧。

下面让我们一起探讨如何应对这个巨大的挑战!

其实像这种需要对大的容量进行 判重,且该场景不需要保证百分之百的准确率,一般都可以使用布隆过滤器来进行实现。

布隆过滤器

布隆过滤器是一种数据结构,旨在快速判断一个元素是否存在于一个集合中。它基于哈希函数的原理,可以高效地判断一个元素是否可能存在于集合中,但并不保证 100% 的准确性。

为什么会不能保证 100% 的准确性,我们来研究它的原理就知道了。

布隆过滤器的结构由 一个 bit 数组多个哈希函数 组成。bit 数组的每一位都只有两种状态:0 或 1。

元素怎么加入到布隆过滤器中?

当一个元素被加入到布隆过滤器中时,会经过多个哈希函数产生多个哈希值,如果生成的哈希值超过了 bit 数组的大小,这里进行取模就可以了,然后将 bit 数组对应的位置置为 1。如下图:

怎么查询一个元素是否存在?

当查询一个元素是否存在时,同样会经过多个哈希函数得到多个哈希值,再去检查对应的位数组位置,只有当所有位数组位置为 1 时,才会判断该元素可能存在于集合中。如果有任意一个位数组位置为 0,则可以确定该元素不存在于集合中。

布隆过滤器在判断元素是否存在时非常迅速,并且占用的内存空间相对较小。但是它也有一些限制,其中之一就是可能存在误判的情况。

假设 aaa.com 经过多个哈希函数计算之后,得到了 0 2 3 的位置,而 bbb.com 经过计算之后同样得到了 0 2 3 的位置,会出现这种情况是由于哈希函数的性质——不同的输入有可能得到相同的输出。从而导致误判。

虽然说有可能元素不在,但是布隆过滤器判断其存在;但是如果元素确实存在于集合中,布隆过滤器一定能判断出来。

看到这里,有朋友可能已经看出来了,为了降低误判率,可以通过以下几个办法:

  • 使用均匀性比较好的哈希函数。一个好的哈希函数应该具有均匀性,即对于输入的不同值,哈希函数计算得到的哈希值应该尽可能均匀地分布在 bit 数组的各个位置上。这样可以避免哈希冲突的发生,提高准确性。如 MD5,SHA 等算法。
  • 可以通过增加哈希函数的数量。
  • 增大位数组的大小来提高准确性。

当然后两点的调优也与实际的数据大小情况有关。需要权衡准确性和内存占用,并根据具体场景调整参数以达到最佳的性能表现。

即使能通过以上的方式,降低误判率,但依然可能出现误判,那应该怎么避免误判呢?

其实首先应该思考的是我们的业务到底能不能容忍出现误判?

布隆过滤器主要适用于那些不需要绝对准确性,但需要高效判断元素是否存在的场景。

其次,对于布隆过滤器可能出现的误判情况,可以考虑一些补偿机制来减少误判率,例如:

  • 确认机制:当布隆过滤器判断某个元素存在于集合中时,可以在实际查询该元素时,再进行一次确认操作。如果实际查询结果与布隆过滤器的结果不符,则确认该元素不存在,从而避免误判。
  • 隔离机制:对于那些可能引起误判的特定情况,可以将这些元素从布隆过滤器中单独处理或加以标记,也就是使用白名单的方式。

通过合理的补偿机制,可以有效避免使用布隆过滤器所带来的误判,提高查询结果的准确性,从而更好地发挥其在实际应用中的作用。

发表回复

后才能评论