布隆过滤器的基本原理和使用

工作中遇到一个需求，需要从词库中快速判断某个关键字是否存在，词库大小不超过百万，当时脑子第一反应是用hash表相关数据结构，和同事一交流，同事推荐用布隆过滤器，查询效率不输hashmap，而且非常节省存储空间。经过研究发现布隆过滤器挺好用的，这篇文章来说说三点：
1.什么是布隆过滤器。
2.布隆过滤器基本原理。
3.布隆过滤器的使用方式。

1.什么是布隆过滤器？

布隆过滤器（Bloom Filter）是1970年由[布隆]提出的。它实际上是一个很长的[二进制]向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

2.布隆过滤器的基本原理

a.下图是一个初始化后的长度为11的布隆过滤器结构，可以看成一个数组，还未放入任何数据，所有位的值都是0。

还未放入数据的布隆过滤器

b.假如有三个hash函数（hash1、hash2、hash3）此时我们添加一个关键字进去，假设我们添加一个字母"a"，通过三个hash函数分别求出2、5、6，于是把下标为2、5、6的值都改为1。

布隆过滤器添加数据流程

c.此时我们根据字母"a"去布隆过滤器查找，判断a是否存在的流程如下图，由于对a进行三个hash函数取模得到的2、5、6下标的值都是1，说明这个a大概率已经存在了（为什么是大概率呢？因为布隆过滤器是一种概率型数据结构，存在非常小的误判几率，不能判断某个元素一定百分之百存在，所以只能用在允许有少量误判的场景，不能用在需要100%精确判断存在的场景）。
如果使用字母b进行查找，三个hash函数取模得到的是7、8、9或者3、5、6，发现这些下标对应的值都不全部是1，则判定为不存在。

布隆过滤器查找数据流程

相对于HashMap的优点：
布隆过滤器节省空间，无需存储全部数据，只需要将多个hash函数取模得到的下标对应位置的值改为1即可，无需存储全部数据，是一种极度节省存储空间的数据结构。

相对于HashMap的缺点：
布隆过滤器无法做到100%精确判断，而HashMap可以。布隆过滤器本质上是赌不同的字符串不太可能所有的哈希函数都发生哈希碰撞，虽然有极低的概率发生，但是基本可以把误判率控制在1%以内。

3.布隆过滤器的使用

3.1引入guava依赖

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>19.0</version>
        </dependency>

3.2 如下是使用示例

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterTester {
    
    private static int size = 1000000;//预计要插入多少数据

    private static double fpp = 0.01;//期望的误判率

    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);

    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        //插入数据
        for (int i = 0; i < size; i++) {
            // 向布隆过滤器添加数据，类似HashMap.put(key, data)方法
            bloomFilter.put(i);
        }
        System.out.println("初始化耗时：" + (System.currentTimeMillis() - time));
        
        time = System.currentTimeMillis();
        int count = 0;
        for (int i = 0; i < size; i++) {
            // 如果布隆过滤器存在对应元素，类似HashMap.contains(key)方法
            if (bloomFilter.mightContain(i)) {

            } else {
                System.out.println(i + "误判了");
                count++;
            }
        }
        System.out.println("总共的误判数:" + count);
        System.out.println(size + "次查询耗时：" + (System.currentTimeMillis() - time));
    }

最后编辑于：2020.07.12 10:17:07