您现在的位置是:首页 > 技术干货

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

技术干货作者:chenli日期:2021-11-29 10:50:22点击:167

前言

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

  1. 现在有一个非常庞大的数据,假设全是 int 类型。现在我给你一个数,你需要告诉我它是否存在其中(尽量高效)。
  2. 需求其实很清晰,只是要判断一个数据是否存在即可。

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

常规实现

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

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

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

为此我写了一个单测,利用 HashSet 来存数据(底层也是 HashMap );

当我只写入 100 条数据时自然是没有问题的。
还是在这个基础上,写入 1000W 数据试试:
执行后马上就内存溢出。

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

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

接下来就是我们的主角登场了。

Bloom Filter

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

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

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

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

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

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

Bloom Filter 过滤器介绍链接 : Bloom Filter 过滤器介绍

文章评论