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

简介: 如何在十亿个单词表中查找某个单词是否出现呢?答案已经给出来了,那就是使用布隆过滤器。那这个布隆过滤器是什么呢?下面就好好讲讲,方便在面试中提高你的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和字典的区别?
53 0
|
存储 NoSQL 算法
阿里面试官:HashMap 熟悉吧?好的,那就来聊聊 Redis 字典吧!
最近,阿粉的一个朋友出去面试,回来跟阿粉抱怨,面试官不按套路出牌,直接打乱了他的节奏。 事情是这样的,前面面试问了几个 Java 的相关问题,我朋友回答还不错,接下来面试官就问了一句:看来 Java 基础还不错,Java HashMap 你熟悉吧? 我朋友回答。工作经常用,有看过源码。 我朋友本来想着,你随便来吧,这个问题之前已经准备好了,随便问吧。
阿里面试官:HashMap 熟悉吧?好的,那就来聊聊 Redis 字典吧!
|
自然语言处理 搜索推荐
[leetcode/lintcode 题解] 国内大厂面试真题详解:外星人字典
[leetcode/lintcode 题解] 国内大厂面试真题详解:外星人字典
[leetcode/lintcode 题解]  国内大厂面试真题详解:外星人字典
|
自然语言处理 算法 搜索推荐
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
[leetcode/lintcode 题解]算法面试真题详解:外星人字典
|
11天前
|
存储 算法 Java
JAVA后端开发面试题库
JAVA后端开发面试题库
19 1
|
15天前
|
缓存 安全 Java
【Java面试——并发基础、并发关键字】
随着硬件指令集的发展,我们可以使用基于冲突检测的乐观并发策略: 先进行操作,如果没有其它线程争用共享数据,那操作就成功了,否则采取补偿措施(不断地重试,直到成功为止)。这种乐观的并发策略的许多实现都不需要将线程阻塞,因此这种同步操作称为非阻塞同步。 乐观锁需要操作和冲突检测这两个步骤具备原子性,这里就不能再使用互斥同步来保证了,只能靠硬件来完成。硬件支持的原子性操作最典型的是: 比较并交换(Compare-and-Swap,CAS)。CAS 指令需要有 3 个操作数,分别是内存地址 V、旧的预期值 A 和新值 B。当执行操作时,只有当 V 的值等于 A,才将 V 的值更新为 B。
|
23天前
|
SQL 存储 Java
致远互联java实习生面试
致远互联java实习生面试
34 0
|
23天前
|
Java
java面试基础 -- 普通类 & 抽象类 & 接口
java面试基础 -- 普通类 & 抽象类 & 接口
26 0
|
23天前
|
存储 安全 Java
java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?
java面试基础 -- ArrayList 和 LinkedList有什么区别, ArrayList和Vector呢?
28 0
|
23天前
|
Java
java面试基础 -- 方法重载 & 方法重写
java面试基础 -- 方法重载 & 方法重写
13 0