布隆过滤器(Bloom Filter)算法的实现原理

2022-05-15 06:24:16

文章目录

前言
一、布隆过滤器
二、布隆过滤器算法实现
总结

前言

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

一、布隆过滤器

1、算法描述

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

初始化BitSet(默认情况下，集合中的所有位最初都具有值false (0))长度为m的比特数组。然后需要引入k个不同的散列函数，新增元素通过这k个散列函数处理之后，映射到比特数组m个比特中的k个，并且把这些命中映射的k个比特位设置为1，产生一个均匀的随机分布。通常情况下，k的一个较小的常数，取决于所需的误判率，而布隆过滤器容量m与散列函数个数k和需要添加元素数量呈正相关。

当需要新增的所有元素都添加到布隆过滤器之后，那么比特数组中的很多比特都被设置为1。这个时候如果需要判断一个元素是否存在于布隆过滤器中，只需要通过k个散列函数处理得到比特数组的k个下标，然后判断比特数组对应的下标所在比特是否为1。如果这k个下标所在比特中至少存在一个0，那么这个需要判断的元素必定不在布隆过滤器代表的集合中；如果这k个下标所在比特全部都为1，那么那么这个需要判断的元素可能存在于布隆过滤器代表的集合中或者刚好是一个False Positive

2、False positives 概率推导

布隆过滤器的显着特点是在m和误报概率之间存在明显的权衡。观察到在将n 个键插入大小为m的表后，特定位仍然为 0 的概率恰好为

因此，在这种情况下误报的概率是

右手边被最小化 k = ln ⁡ 2 × m / n k = \ln 2 \times m / n k=ln2×m/n，此时False Positives的概率为

参考资料: 链接

3、优势和劣势

布隆过滤器的优势：
- 布隆过滤器相对于其他数据结构在时空上有巨大优势，占用内存少，查询和插入元素的时间复杂度都是O(k)
- 可以准确判断元素不存在于布隆过滤器中的场景
- 散列函数可以独立设计
- 布隆过滤器不需要存储元素本身，适用于某些数据敏感和数据严格保密的场景
布隆过滤器的劣势
- 不能准确判断元素必定存在于布隆过滤器中的场景，存在误判率，在k和m固定的情况下，添加的元素越多，误判率越高
- 没有存储全量的元素，对于一些准确查询或者准确统计的场景不适用
- 原生的布隆过滤器无法安全地删除元素

二、布隆过滤器算法实现

public class HashFunction {

    /**
     * 布隆过滤器容量
     */
    private final int size;

    private final int seed;

    public HashFunction(int size, int seed) {
        this.size = size;
        this.seed = seed;
    }

    public int hash(String value) {
        int result = 0;
        int len = value.length();
        for (int i = 0; i < len; i++) {
            result = seed * result + value.charAt(i);
        }
        //与运算两位同时为1，结果才为1。确保计算出来的结果不会超过size
        return (size - 1) & result;
    }
}

public class MyBloomFilter {

/**
 * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
 */
private static final int[] SEEDS = {3, 5, 7, 11, 13, 31, 37, 61};

/**
 * 相当于构建 8 个不同的hash算法
 */
private static HashFunction[] functions;

/**
 * 初始化布隆过滤器的 bitmap
 */
private static BitSet bitset;


public MyBloomFilter(int size) {
    bitset = new BitSet(size);
    functions = new HashFunction[SEEDS.length];
    for (int i = 0; i < SEEDS.length; i++) {
        functions[i] = new HashFunction(size, SEEDS[i]);
    }
}

/**
 * 添加数据
 *
 * @param value 需要加入的值
 */
public void add(String value) {
    for (HashFunction function : functions) {
        //计算 hash 值并修改 bitmap 中相应位置为 true
        bitset.set(function.hash(value), true);
    }
}

/**
 * 判断相应元素是否存在
 *
 * @param value 需要判断的元素
 * @return 结果
 */
public boolean contains(String value) {
    if (value == null) {
        return false;
    }
    boolean ret = true;
    for (HashFunction f : functions) {
        ret = bitset.get(f.hash(value));
        //一个 hash 函数返回 false 则跳出循环
        if (!ret) {
            break;
        }
    }
    return ret;
}

/**
 * 测试。。。
 */
public static void main(String[] args) {
    MyBloomFilter bf = new MyBloomFilter(10);
    bf.add("Aa");

    System.out.println(bf.contains("BB")); //true
    System.out.println(bf.contains("Aa"));//true
}

总结

完

感谢您的阅读

如果你发现了错误的地方，可以在留言区提出来，我对其加以修改

码农公寓