安基网 首页 编程 软件学院 查看内容

算法面试,如何在100 亿URL中判断某个URL是否存在?

2019-1-26 11:37| 投稿: xiaotiger |来自: 互联网


免责声明:本站系公益性非盈利IT技术普及网,本文由投稿者转载自互联网的公开文章,文末均已注明出处,其内容和图片版权归原网站或作者所有,文中所述不代表本站观点,若有无意侵权或转载不当之处请从网站右下角联系我们处理,谢谢合作!

摘要: 如果面试官问你,一个网站有 100 亿 url 存在一个黑名单中,每条 url 平均 64 字节。问这个黑名单要怎么存?若此时随便输入一个 url,如何判断该 url 是否在这个黑名单中?对于第一个问题,如果把黑名单看成一个集合 ...
作者:七淅
来源:公众号不只Java

如果面试官问你,一个网站有 100 亿 url 存在一个黑名单中,每条 url 平均 64 字节。问这个黑名单要怎么存?若此时随便输入一个 url,如何判断该 url 是否在这个黑名单中?

对于第一个问题,如果把黑名单看成一个集合,将其存在 hashmap 中,貌似太大了,需要 640G,明显不科学。

那该怎么办?ok,现在该介绍今天的主角了 —— 布隆过滤器就可以解决这样的问题。

首先,布隆过滤器是什么?维基百科是这样解释的:

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


官方说法看下就好,如果不理解没关系,其实不会难,下面我们讲人话慢慢来。

2. 具体介绍

布隆过滤器实际上是一个很长的二进制矢量和一系列随机映射函数。


「很长的二进制矢量」:这是一个长度很长的数组,什么类型的数组呢?bit 类型的数组,也是我们说的「位」,(1Byte = 8bit,1KB = 1024Byte)。

「一系列随机映射函数」:有多个哈希函数。那什么是哈希函数呢?JDK 里面有计算得到哈希值的方法,那就是一个哈希函数。

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难


这个不就可以解决我们最开始的问题吗?那它是怎么解决的呢?

3. 解决过程

下面我说下大体的过程,细节部分可先不理解,重要的是明白流程,细节我后面补充。

假设,bit 类型数组的长度为 m,每个元素值为 0,有 k 个哈希函数。

首先,当输入一个 url 的时候,此时这个 url 会经过 k 个哈希函数处理,得到多个哈希值(v1,v2,...,vk)。之后分别将这些哈希值除以数组的长度 m,和对 m 取模,得到这些哈希值对应在数组的下标位置,最后将这些下标的元素都置为 1。


那么如何判断一个 url 在黑名单里面呢?输入一条 url,它经过上述处理之后,会得到多个数组的下标位置。如果这些下标的元素值都已经为 1 了,说明该在黑名单里面,否则不在。

总体就是这样的流程,下面说下大家可能存在的疑问:

1、bit 类型的数组如何构建

2、得到 v1,v2,...,vk 这些哈希值后,如何得到其在数组的下标位置,并将其设置为 1 呢?

两个问题我一起说下,Java 里面没有 bit 这样的类型,怎么构建呢?—— 不难,我们可以使用 int,一个 int 是 32 位。

//创建了一个 100 * 32bit 的数组
int[] arr = new int[100]; 
// 代表 bit 数组 0-31 位的元素
arr[0];


因此上面再会说「分别将这些哈希值除以数组的长度 m,和对 m 取模,得到这些哈希值对应在数组的下标位置」。

具体我们可以拿一个哈希值 data 来举个栗子,假设 int 数组长度为 100。

void Set(int data) {
 // ByteNO 是表示在 table 数组中那个元素
 int ByteNo = data / 100;
 // bitNo 是表示在 32 位 bit 中哪个 bit 位。
 int BitNo = data % 32;
 // 置 1
 _table[ByteNo] |= (1 << BitNo); 
 }


4. 使用效果

最开始我们提到,如果将 100 亿 url 放到 HashMap 中需要 640GB,那么使用布隆过滤器后又需要多少空间呢?答案是约等于 23 GB。相比之下,这个空间大小是不是就可以接受很多了。

5. 缺点

布隆过滤器有宁可错杀一百,也不能放过一个的性质。讲人话就是属于黑名单的 url 一定能够正确判断它在黑名单中,但不属于黑名单中的 url 也可能会被认为在黑名单中,存在一定的失误率。

至于失误率要保持在多少,数组长度,哈希函数的个数分别要设置多少就需要根据实际情况来选择了,网上有对应的数学公式计算,这里就不展开讲了。



小编推荐:欲学习电脑技术、系统维护、网络管理、编程开发和安全攻防等高端IT技术,请 点击这里 注册账号,公开课频道价值万元IT培训教程免费学,让您少走弯路、事半功倍,好工作升职加薪!

本文出自:https://www.toutiao.com/i6650274200068047374/

免责声明:本站系公益性非盈利IT技术普及网,本文由投稿者转载自互联网的公开文章,文末均已注明出处,其内容和图片版权归原网站或作者所有,文中所述不代表本站观点,若有无意侵权或转载不当之处请从网站右下角联系我们处理,谢谢合作!


鲜花

握手

雷人

路过

鸡蛋

相关阅读

最新评论

 最新
返回顶部