文档章节

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

crossoverJie
 crossoverJie
发布于 11/27 08:40
字数 2699
阅读 2363
收藏 178

前言

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

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

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

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

常规实现

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

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

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

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

-Xms64m -Xmx64m -XX:+PrintHeapAtGC -XX:+HeapDumpOnOutOfMemoryError 

为了方便调试加入了 GC 日志的打印,以及内存溢出后 Dump 内存。

    @Test
    public void hashMapTest(){
        long star = System.currentTimeMillis();

        Set<Integer> hashset = new HashSet<>(100) ;
        for (int i = 0; i < 100; i++) {
            hashset.add(i) ;
        }
        Assert.assertTrue(hashset.contains(1));
        Assert.assertTrue(hashset.contains(2));
        Assert.assertTrue(hashset.contains(3));

        long end = System.currentTimeMillis();
        System.out.println("执行时间:" + (end - star));
    }

当我只写入 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 则认为数据肯定不存在于集合,否则数据可能存在于集合中

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

  1. 只要返回数据不存在,则肯定不存在。
  2. 返回数据存在,但只能是大概率存在。
  3. 同时不能清除其中的数据。

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

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

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

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

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

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

自己实现一个布隆过滤

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

public class BloomFilters {

    /**
     * 数组长度
     */
    private int arraySize;

    /**
     * 数组
     */
    private int[] array;

    public BloomFilters(int arraySize) {
        this.arraySize = arraySize;
        array = new int[arraySize];
    }

    /**
     * 写入数据
     * @param key
     */
    public void add(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);

        array[first % arraySize] = 1;
        array[second % arraySize] = 1;
        array[third % arraySize] = 1;

    }

    /**
     * 判断数据是否存在
     * @param key
     * @return
     */
    public boolean check(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);

        int firstIndex = array[first % arraySize];
        if (firstIndex == 0) {
            return false;
        }

        int secondIndex = array[second % arraySize];
        if (secondIndex == 0) {
            return false;
        }

        int thirdIndex = array[third % arraySize];
        if (thirdIndex == 0) {
            return false;
        }

        return true;

    }


    /**
     * hash 算法1
     * @param key
     * @return
     */
    private int hashcode_1(String key) {
        int hash = 0;
        int i;
        for (i = 0; i < key.length(); ++i) {
            hash = 33 * hash + key.charAt(i);
        }
        return Math.abs(hash);
    }

    /**
     * hash 算法2
     * @param data
     * @return
     */
    private int hashcode_2(String data) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < data.length(); i++) {
            hash = (hash ^ data.charAt(i)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;
        return Math.abs(hash);
    }

    /**
     *  hash 算法3
     * @param key
     * @return
     */
    private int hashcode_3(String key) {
        int hash, i;
        for (hash = 0, i = 0; i < key.length(); ++i) {
            hash += key.charAt(i);
            hash += (hash << 10);
            hash ^= (hash >> 6);
        }
        hash += (hash << 3);
        hash ^= (hash >> 11);
        hash += (hash << 15);
        return Math.abs(hash);
    }
}
  1. 首先初始化了一个 int 数组。
  2. 写入数据的时候进行三次 hash 运算,同时把对应的位置置为 1。
  3. 查询时同样的三次 hash 运算,取到对应的值,一旦值为 0 ,则认为数据不存在。

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

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

-Xms64m -Xmx64m -XX:+PrintHeapAtGC
    @Test
    public void bloomFilterTest(){
        long star = System.currentTimeMillis();
        BloomFilters bloomFilters = new BloomFilters(10000000) ;
        for (int i = 0; i < 10000000; i++) {
            bloomFilters.add(i + "") ;
        }
        Assert.assertTrue(bloomFilters.check(1+""));
        Assert.assertTrue(bloomFilters.check(2+""));
        Assert.assertTrue(bloomFilters.check(3+""));
        Assert.assertTrue(bloomFilters.check(999999+""));
        Assert.assertFalse(bloomFilters.check(400230340+""));
        long end = System.currentTimeMillis();
        System.out.println("执行时间:" + (end - star));
    }

执行结果如下:

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


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

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

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

Guava 实现

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

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

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

-Xms64m -Xmx64m -XX:+PrintHeapAtGC 

    @Test
    public void guavaTest() {
        long star = System.currentTimeMillis();
        BloomFilter<Integer> filter = BloomFilter.create(
                Funnels.integerFunnel(),
                10000000,
                0.01);

        for (int i = 0; i < 10000000; i++) {
            filter.put(i);
        }

        Assert.assertTrue(filter.mightContain(1));
        Assert.assertTrue(filter.mightContain(2));
        Assert.assertTrue(filter.mightContain(3));
        Assert.assertFalse(filter.mightContain(10000000));
        long end = System.currentTimeMillis();
        System.out.println("执行时间:" + (end - star));
    }

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

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

源码分析

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

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

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

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

put 写入函数

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

  • 根据 murmur3_128 方法的到一个 128 位长度的 byte[]
  • 分别取高低 8 位的到两个 hash 值。
  • 再根据初始化时的到的执行 hash 的次数进行 hash 运算。
bitsChanged |= bits.set((combinedHash & Long.MAX_VALUE) % bitSize);

其实也是 hash取模拿到 index 后去赋值 1.

重点是 bits.set() 方法。

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

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

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

  • set 之前先通过 get() 判断这个数据是否存在于集合中,如果已经存在则直接返回告知客户端写入失败。
  • 接下来就是通过位运算进行位或赋值
  • get() 方法的计算逻辑和 set 类似,只要判断为 0 就直接返回存在该值。

mightContain 是否存在函数

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

总结

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

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

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

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

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

https://github.com/crossoverJie/JCSprout

你的点赞与分享是对我最大的支持

© 著作权归作者所有

共有 人打赏支持
crossoverJie
粉丝 569
博文 75
码字总数 140479
作品 0
江北
后端工程师
私信 提问
加载中

评论(22)

crossoverJie
crossoverJie

引用来自“天峰”的评论

引用来自“crossoverJie”的评论

引用来自“天峰”的评论

Bloom Filter 只能判断是否不存在。
是的,我在文中有提到。

@crossoverJie 你的标题就是错的。Bloom Filter 有两种结果:“一定不存在”或“可能存在也可能不存在”。

引用来自“crossoverJie”的评论

文字游戏就不纠结了,标题叫做《如何判断一个元素在亿级数据中是否存在?》那返回不存在不就对了嘛?

引用来自“matyhtf”的评论

不严谨。
文中反复提到布隆过滤的特点和适用范围
matyhtf
matyhtf

引用来自“天峰”的评论

引用来自“crossoverJie”的评论

引用来自“天峰”的评论

Bloom Filter 只能判断是否不存在。
是的,我在文中有提到。

@crossoverJie 你的标题就是错的。Bloom Filter 有两种结果:“一定不存在”或“可能存在也可能不存在”。

引用来自“crossoverJie”的评论

文字游戏就不纠结了,标题叫做《如何判断一个元素在亿级数据中是否存在?》那返回不存在不就对了嘛?
不严谨。
crossoverJie
crossoverJie

引用来自“天峰”的评论

引用来自“crossoverJie”的评论

引用来自“天峰”的评论

Bloom Filter 只能判断是否不存在。
是的,我在文中有提到。

@crossoverJie 你的标题就是错的。Bloom Filter 有两种结果:“一定不存在”或“可能存在也可能不存在”。
文字游戏就不纠结了,标题叫做《如何判断一个元素在亿级数据中是否存在?》那返回不存在不就对了嘛?
天峰
天峰

引用来自“crossoverJie”的评论

引用来自“天峰”的评论

Bloom Filter 只能判断是否不存在。
是的,我在文中有提到。

@crossoverJie 你的标题就是错的。Bloom Filter 有两种结果:“一定不存在”或“可能存在也可能不存在”。
crossoverJie
crossoverJie

引用来自“小熊宝宝”的评论

如果是数据字符串,如果允许分组存放。那么按照字母,每个字母一个文件,每个数字一个文件,共36个文件。数据再多就继续分组,按照两个字母分组,36*36=1296个文件。
这种方法我在某个网游的私服上见到过,游戏帐号就是每个字母一个文件。根本没用到数据库。这个网游流行的时候数据库还没那么流行。

引用来自“crossoverJie”的评论

这里还有一个前提条件,就是“高效”。

所以不希望有额外的 IO 读取,所以才需要全部 load 到内存。

引用来自“小熊宝宝”的评论

数据过大一次load到内存是不现实的。很容易爆内存
所以这才是布隆过滤的优势,以较小的内存开销存放大量的数据。
小熊宝宝
小熊宝宝

引用来自“小熊宝宝”的评论

如果是数据字符串,如果允许分组存放。那么按照字母,每个字母一个文件,每个数字一个文件,共36个文件。数据再多就继续分组,按照两个字母分组,36*36=1296个文件。
这种方法我在某个网游的私服上见到过,游戏帐号就是每个字母一个文件。根本没用到数据库。这个网游流行的时候数据库还没那么流行。

引用来自“crossoverJie”的评论

这里还有一个前提条件,就是“高效”。

所以不希望有额外的 IO 读取,所以才需要全部 load 到内存。
数据过大一次load到内存是不现实的。很容易爆内存
简单生活
简单生活

引用来自“crossoverJie”的评论

引用来自“简单生活”的评论

天意啊,最近两天一直在研究亿级数据差集,看到这篇文章豁然开朗,和redis,setbit简直不要太完美
嗯 目的类似。

@crossoverJie 如果对准确率要求高的话可以使用Cuckoo Filter
crossoverJie
crossoverJie

引用来自“简单生活”的评论

天意啊,最近两天一直在研究亿级数据差集,看到这篇文章豁然开朗,和redis,setbit简直不要太完美
嗯 目的类似。
简单生活
简单生活
天意啊,最近两天一直在研究亿级数据差集,看到这篇文章豁然开朗,和redis,setbit简直不要太完美
crossoverJie
crossoverJie

引用来自“moodlxs”的评论

引用来自“crossoverJie”的评论

引用来自“moodlxs”的评论

作者明显没有搞明白什么叫布隆过滤器,发出来就有点贻笑大方了
哦?愿闻其详。我哪里说错了?

它主要就是用于解决判断一个元素是否在一个集合中,但它的优势是只需要占用很小的内存空间以及有着高效的查询效率。
——
看到这句话就已经看不下去了,你仔细想想。
请不要故作高深,直接点说哪里有问题就行。
大数据处理算法一:Bitmap算法

腾讯面试题:给20亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中并且所耗内存尽可能的少? 解析:bitmap算法就好办多了 所谓bitmap,...

超人学院
2015/04/29
0
2
使用BloomFilter优化scrapy-redis去重

使用BloomFilter优化scrapy-redis去重 1. 背景 做爬虫的都知道,scrapy是一个非常好用的爬虫框架,但是scrapy吃内存非常的厉害。其中有个很关键的点就在于去重。 “去重”需要考虑三个问题:...

zwq912318834
2017/12/27
0
0
如何实现大数据集查询?Bloom Filter或许是你想要的

1、什么情况下需要布隆过滤器? 先来看几个比较常见的例子 字处理软件中,需要检查一个英语单词是否拼写正确 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里,一个网址是否被访...

流川枫AI
2017/06/18
0
0
如何判断一个数是否在40亿个整数中

【面试现场】 题目:我有40亿个整数,再给一个新的整数,我需要判断新的整数是否在40亿个整数中,你会怎么做? 【请教大神】 小史回到学校,把面试的情况和计算机学院的吕老师说了一下。 小史...

Ocean_K
09/05
0
0
找出数组中两数之和为指定值的所有整数对

一,问题描述 给定一个整型数组(数组中的元素可重复),以及一个指定的值。打印出数组中两数之和为指定值的 所有整数对 思路1:可以用hash表来存储数组中的元素,这样我们取得一个数后,去判...

一贱书生
2016/11/28
35
0

没有更多内容

加载失败,请刷新页面

加载更多

09.ajax局部渲染---《Beetl视频课程》

本期视频实现分类实时获取; 内容简介:使用了局部渲染技术,实现分类的实时获取 一起学beetl目录:https://my.oschina.net/u/1590490?tab=newest&catalogId=6214598 作者:GK Beetl满足了更...

Gavin-King
13分钟前
1
0
同步访问共享的可变数据(66)

关键字synchronized 保证同一时刻,只有一个线程执行某一个方法或代码块 当一个对象被一个线程修改时,可以阻止其他线程看到其内部的不一致状态 正确的使用同步可以避免任何对象看到其不一致...

Java搬砖工程师
15分钟前
1
0
银行卡二要素真实性查询

验证用户的银行卡号、持卡人姓名是否真实。 示例代码: private static String host = "https://bank.market.alicloudapi.com";private static String path = "/bank2";private sta...

貔貅叔
19分钟前
1
0
iOS补位动画、沙漏效果、移动UITableViewCell、模拟贪吃蛇、拖拽进度等源码

iOS精选源码 JHAlertView - 一款黑白配色的HUD之沙漏效果 继承UIButton的自定义按钮SPButton 用递归算法实现iOS补位动画 iOS 长按移动UITableViewCell JHLikeButton - 有趣的点赞动画 兼容X...

Android爱开源
29分钟前
1
0
上币至iamToken

https://github.com/consenlabs/token-profile 点击Fork按钮,插入到自己的github项目中 cd /Users/shijun/Desktop/blockChain/iamToken git clone https://github.com/yellmi1983/token-pro......

八戒八戒八戒
33分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部