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

转载自  算法面试，如何在100 亿URL中判断某个URL是否存在java

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

对于第一个问题，若是把黑名单当作一个集合，将其存在 hashmap 中，貌似太大了，须要 640G，明显不科学。算法

那该怎么办？ok，如今该介绍今天的主角了 —— 布隆过滤器就能够解决这样的问题。数组

首先，布隆过滤器是什么？维基百科是这样解释的：函数

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它其实是一个很长的二进制矢量和一系列随机映射函数。布隆过滤器能够用于检索一个元素是否在一个集合中。它的优势是空间效率和查询时间都远远超过通常的算法，缺点是有必定的误识别率和删除困难。网站

官方说法看下就好，若是不理解不要紧，其实不会难，下面咱们讲人话慢慢来。url

2. 具体介绍code

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

「很长的二进制矢量」：这是一个长度很长的数组，什么类型的数组呢？bit 类型的数组，也是咱们说的「位」，（1Byte = 8bit，1KB = 1024Byte）。ci

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

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

这个不就能够解决咱们最开始的问题吗？那它是怎么解决的呢？

3. 解决过程

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

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

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

那么如何判断一个 url 在黑名单里面呢？输入一条 url，它通过上述处理以后，会获得多个数组的下标位置。若是这些下标的元素值都已经为 1 了，说明该在黑名单里面，不然不在。

整体就是这样的流程，下面说下你们可能存在的疑问：

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

二、获得 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 也可能会被认为在黑名单中，存在必定的失误率。

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