面试官:如何在十亿个单词字典中,判断某个单词是否存在?(布隆过滤器)

简介: 如何在十亿个单词表中查找某个单词是否出现呢?答案已经给出来了,那就是使用布隆过滤器。那这个布隆过滤器是什么呢?下面就好好讲讲,方便在面试中提高你的zhuangbility。

一、认识布隆过滤器


1、概念


布隆过滤器其实就是加快判定一个元素是否在集合中出现的方法。比如说在一个大字典中,要查找某个单词是否存在,于是我们就可以使用布隆过滤器,快速高效省时省力。


2、原理


既然布隆过滤器这么优秀,他是如何实现的呢?我们知道在我们身边充斥着各种各样的网站,为了不毒害我们祖国的花朵,于是国家网警就开始对这些网站进行割除过滤,然后关闭。关闭的时候呢就是关闭他的地址。现在问题来了。


这些网站的地址其实是不停的更换的,这些垃圾网站和正常网站加起来全世界据统计也有几十亿个。这些网警拿到一个地址之后总不能到数据库里面一个一个去比较吧,这就带来了一系列问题。


(1)网站数量太多,存储起来比较麻烦。一个地址最起码有32个字节,一亿个地址就需要1.6G的内存。

(2)一个一个比较,太费时间了。

布隆过滤器是如何高效的呢?他的底层其实是一个特比长的二进制向量和一系列随机映射函数。我们存储一亿个垃圾网站地址。

(1)第一步:建立一个32亿二进制(比特),也就是4亿字节的向量。全部置0。

v2-eb71b3d6d440083aa153cea57739a729_1440w.jpg

(2)第二步:网警用八个不同的随机数产生器(F1,F2, ...,F8) 产生八个信息指纹(f1, f2, ..., f8)。

(3)第三步:用一个随机数产生器 G 把这八个信息指纹映射到 1 到32亿中的八个自然数 g1, g2, ...,g8。

(4)第四步:把这八个位置的二进制全部设置为一。

v2-13c9e09a87436e4a9e20f749c9b5a46e_1440w.jpg

OK,这就是其原理,现在网警把所有的垃圾网站地址全部存储下来了,有一天网警查到了一个可疑的网站,想判断一下是否是XX网站,于是就开始检查了。查询可疑网站是否存在集合中的时候,通过同样的方法将可疑网站通过哈希映射到32亿个比特位数组上的8个点。如果8个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。

注意:如果8个点全部是1,也不能判断钙元素一定存在集合中,有一定的误差率。


二、代码实现布隆过滤器


上面只是给出了其原理,下面我们代码实现一下

v2-fd5c4cd8a8f94ebcdab7161b586af857_1440w.jpg

v2-8b3cd269e47606aa1058f7c21788ca2c_1440w.jpg

还有一个SimpleHash,我们看一下

v2-e6838c985ef8903af80f26bc35ce5f94_1440w.jpg

这就是布隆过滤器的实现。

相关文章
|
JSON 测试技术 数据格式
软件测试面试题:json和字典的区别?
软件测试面试题:json和字典的区别?
55 0
|
存储 NoSQL 算法
阿里面试官:HashMap 熟悉吧?好的,那就来聊聊 Redis 字典吧!
最近,阿粉的一个朋友出去面试,回来跟阿粉抱怨,面试官不按套路出牌,直接打乱了他的节奏。 事情是这样的,前面面试问了几个 Java 的相关问题,我朋友回答还不错,接下来面试官就问了一句:看来 Java 基础还不错,Java HashMap 你熟悉吧? 我朋友回答。工作经常用,有看过源码。 我朋友本来想着,你随便来吧,这个问题之前已经准备好了,随便问吧。
阿里面试官:HashMap 熟悉吧?好的,那就来聊聊 Redis 字典吧!
|
自然语言处理 搜索推荐
[leetcode/lintcode 题解] 国内大厂面试真题详解:外星人字典
[leetcode/lintcode 题解] 国内大厂面试真题详解:外星人字典
[leetcode/lintcode 题解]  国内大厂面试真题详解:外星人字典
|
自然语言处理 算法 搜索推荐
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
|
3天前
|
设计模式 SQL JavaScript
java面试宝典全套含答案
java面试宝典全套含答案
18 3
|
3天前
|
存储 Java
java面试题大全带答案_面试题库_java面试宝典2018
java面试题大全带答案_面试题库_java面试宝典2018
17 3
|
3天前
|
SQL 前端开发 Java
2019史上最全java面试题题库大全800题含答案(面试宝典)(4)
2019史上最全java面试题题库大全800题含答案(面试宝典)
17 3
|
3天前
|
SQL Java 数据库连接
2019史上最全java面试题题库大全800题含答案(面试宝典)(2)
2019史上最全java面试题题库大全800题含答案(面试宝典)
12 2
|
3天前
|
存储 设计模式 Java
java实习生面试题_java基础面试_java面试题2018及答案_java面试题库
java实习生面试题_java基础面试_java面试题2018及答案_java面试题库
19 1
|
3天前
|
SQL 算法 安全
java面试宝典_java基础面试_2018java面试题_2019java最新面试题
java面试宝典_java基础面试_2018java面试题_2019java最新面试题
11 1