如何判断一个元素在亿级数据中是否存在?

前言

最近有朋友问我这么一个面试题目:

现在有一个非常庞大的数据,假设全是 int 类型。现在我给你一个数,你需要告诉我它是否存在其中(尽量高效)。

需求其实很清晰,只是要判断一个数据是否存在即可。

但这里有一个比较重要的前提:非常庞大的数据

常规实现

先不考虑这个条件,我们脑海中出现的第一种方案是什么?

我想大多数想到的都是用HashMap来存放数据,因为它的写入查询的效率都比较高。

写入和判断元素是否存在都有对应的API,所以实现起来也比较简单。

为此我写了一个单测,利用HashSet来存数据(底层也是HashMap);同时为了后面的对比将堆内存写死:

当我只写入 100 条数据时自然是没有问题的。

还是在这个基础上,写入 1000W 数据试试:


执行后马上就内存溢出。


可见在内存有限的情况下我们不能使用这种方式。

实际情况也是如此;既然要判断一个数据是否存在于集合中,考虑的算法的效率以及准确性肯定是要把数据全部load到内存中的。

Bloom Filter

基于上面分析的条件,要实现这个需求最需要解决的是如何将庞大的数据 load 到内存中。

而我们是否可以换种思路,因为只是需要判断数据是否存在,也不是需要把数据查询出来,所以完全没有必要将真正的数据存放进去。

伟大的科学家们已经帮我们想到了这样的需求。

Burton Howard Bloom在 1970 年提出了一个叫做Bloom Filter(中文翻译:布隆过滤)的算法。

它主要就是用于解决判断一个元素是否在一个集合中,但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。

所以在这个场景下在合适不过了。

Bloom Filter 原理

下面来分析下它的实现原理。

官方的说法是:它是一个保存了很长的二级制向量,同时结合 Hash 函数实现的。

听起来比较绕,但是通过一个图就比较容易理解了。


如图所示:

首先需要初始化一个二进制的数组,长度设为 L(图中为 8),同时初始值全为 0 。

当写入一个A1=1000的数据时,需要进行 H 次hash函数的运算(这里为 2 次);与 HashMap 有点类似,通过算出的HashCode与 L 取模后定位到 0、2 处,将该处的值设为 1。

A2=2000也是同理计算后将4、7位置设为 1。

当有一个B1=1000需要判断是否存在时,也是做两次 Hash 运算,定位到 0、2 处,此时他们的值都为 1 ,所以认为B1=1000存在于集合中。

当有一个B2=3000时,也是同理。第一次 Hash 定位到index=4时,数组中的值为 1,所以再进行第二次 Hash 运算,结果定位到index=5的值为 0,所以认为B2=3000不存在于集合中。

整个的写入、查询的流程就是这样,汇总起来就是:

对写入的数据做 H 次 hash 运算定位到数组中的位置,同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。 一旦其中的有一位为0则认为数据肯定不存在于集合,否则数据可能存在于集合中

所以布隆过滤有以下几个特点:

只要返回数据不存在,则肯定不存在。

返回数据存在,但只能是大概率存在。

同时不能清除其中的数据。

第一点应该都能理解,重点解释下 2、3 点。

为什么返回存在的数据却是可能存在呢,这其实也和HashMap类似。

在有限的数组长度中存放大量的数据,即便是再完美的 Hash 算法也会有冲突,所以有可能两个完全不同的A、B两个数据最后定位到的位置是一模一样的。

这时拿 B 进行查询时那自然就是误报了。

删除数据也是同理,当我把 B 的数据删除时,其实也相当于是把 A 的数据删掉了,这样也会造成后续的误报。

基于以上的Hash冲突的前提,所以Bloom Filter有一定的误报率,这个误报率和Hash算法的次数 H,以及数组长度 L 都是有关的。

自己实现一个布隆过滤

算法其实很简单不难理解,于是利用Java实现了一个简单的雏形。


首先初始化了一个 int 数组。

写入数据的时候进行三次hash运算,同时把对应的位置置为 1。

查询时同样的三次hash运算,取到对应的值,一旦值为 0 ,则认为数据不存在。

实现逻辑其实就和上文描述的一样。

下面来测试一下,同样的参数:


只花了 3 秒钟就写入了 1000W 的数据同时做出来准确的判断。


当让我把数组长度缩小到了 100W 时就出现了一个误报,400230340这个数明明没在集合里,却返回了存在。

这也体现了Bloom Filter的误报率。

我们提高数组长度以及hash计算次数可以降低误报率,但相应的CPU、内存的消耗就会提高;这就需要根据业务需要自行权衡。

Guava 实现


刚才的方式虽然实现了功能,也满足了大量数据。但其实观察GC日志非常频繁,同时老年代也使用了 90%,接近崩溃的边缘。

总的来说就是内存利用率做的不好。

其实 Google Guava 库中也实现了该算法,下面来看看业界权威的实现。


也是同样写入了 1000W 的数据,执行没有问题。


观察 GC 日志会发现没有一次fullGC,同时老年代的使用率很低。和刚才的一对比这里明显的要好上很多,也可以写入更多的数据。

源码分析

那就来看看Guava它是如何实现的。

构造方法中有两个比较重要的参数,一个是预计存放多少数据,一个是可以接受的误报率。 我这里的测试 demo 分别是 1000W 以及 0.01。


Guava会通过你预计的数量以及误报率帮你计算出你应当会使用的数组大小numBits以及需要计算几次 Hash 函数numHashFunctions。

这个算法计算规则可以参考维基百科。

put 写入函数

真正存放数据的put函数如下:


根据murmur3_128方法的到一个 128 位长度的byte[]。

分别取高低 8 位的到两个hash值。

再根据初始化时的到的执行hash的次数进行hash运算。


其实 set 方法是BitArray中的一个函数,BitArray就是真正存放数据的底层数据结构。

利用了一个long[] data来存放数据。

所以set()时候也是对这个data做处理。


在set之前先通过get()判断这个数据是否存在于集合中,如果已经存在则直接返回告知客户端写入失败。

接下来就是通过位运算进行位或赋值。

get()方法的计算逻辑和 set 类似,只要判断为 0 就直接返回存在该值。

mightContain 是否存在函数


前面几步的逻辑都是类似的,只是调用了刚才的get()方法判断元素是否存在而已。

总结

布隆过滤的应用还是蛮多的,比如数据库、爬虫、防缓存击穿等。

特别是需要精确知道某个数据不存在时做点什么事情就非常适合布隆过滤。

这段时间的研究发现算法也挺有意思的,后续应该会继续分享一些类似的内容。

如果对你有帮助那就分享一下吧。

本问的示例代码参考这里:

github.com/crossoverJi…

转发文章作者:crossoverJie

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 215,384评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,845评论 3 391
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,148评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,640评论 1 290
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,731评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,712评论 1 294
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,703评论 3 415
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,473评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,915评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,227评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,384评论 1 345
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,063评论 5 340
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,706评论 3 324
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,302评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,531评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,321评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,248评论 2 352

推荐阅读更多精彩内容

  • 关于Mongodb的全面总结 MongoDB的内部构造《MongoDB The Definitive Guide》...
    中v中阅读 31,920评论 2 89
  • 教你如何迅速秒杀掉:99%的海量数据处理面试题 本文经过大量细致的优化后,收录于我的新书《编程之法》第六章中,新书...
    Helen_Cat阅读 7,413评论 1 39
  • 这是我的第二次公开我的日志,也是我的又一个突破。是的,太有意思了,改变自己一种生活方式,世界真的发生奇妙的变...
    曾兴林西昌阅读 254评论 1 7
  • 留下点痕迹 去年算命,相面都说我六十来岁寿命。几十年奔波,辛劳,眼看就要歇一口气,却已走到了尽头,实在是冤屈呀!一...
    零星往事阅读 240评论 0 0
  • 一个人,腿骨折入院。经过医院的一番接骨打石膏的处理后,终于出院了。因断骨处没有完全愈合,行动不便,就拄上拐杖行走。...
    放松放开放下阅读 283评论 1 2