算法-bloomfilter数据结构技术总结

bloomfilter是一种节省空间的概率数据结构，用于测试数据元素是否在一个集合中.

前言：bloomfilter是一种节省空间的概率数据结构，用于测试数据元素是否在一个集合中。核心是通过一个位数组来存储经过一组hash计算之后的值，通过判断位数组位置是否为1来判断元素是否存在。本质上是通过计算换空间的一种算法。类似的数据结构还有Trie前缀树，它是通过计算公共前缀来节省空间的。

业务场景

1. 大数据Hbase的rowkey是否存在某个数据块、API网关应用是否存在、邮件中某个用户是否在黑名单等
2. 解决缓存穿透问题，用于提前过滤掉无用的查询或者调用，减轻数据库的压力。

核心原理

解决什么问题：利用hash函数和位存储来解决判断是否一个元素存在的问题，因为可能会有hash冲突，所以当返回结果是true时，元素不一定会存在，但返回false，元素一定不存在。

核心数据结构：一组hash函数和位存储

public class BloomFilter<T> {
    private BitSet bitSet;
    private int size;
    private int hashFunctions;

    public BloomFilter(int size, int hashFunctions) {
        this.size = size;
        this.hashFunctions = hashFunctions;
        this.bitSet = new BitSet(size);
    }

    public void add(T value) {
        for (int i = 0; i < hashFunctions; i++) {
            int hash = hashFunction(i, value);
            bitSet.set(hash % size);
        }
    }

    public boolean contains(T value) {
        for (int i = 0; i < hashFunctions; i++) {
            int hash = hashFunction(i, value);
            if (!bitSet.get(hash % size)) {
                return false;
            }
        }
        return true;
    }

Java数据结构BitSet实现

1.构建一个BitSet

// 初始化-> nbits为容量，
long[] words = new long[wordIndex(nbits-1) + 1]; // 存储

// 相当于 N/64,这里用移位操作,向右移6位，也就是除以2^6
private static int wordIndex(int bitIndex) {
   return bitIndex >> ADDRESS_BITS_PER_WORD; // ADDRESS_BITS_PER_WORD为6
}

BitSet数据结构：容量N、****Long[](一个Long是8个Byte，一个Byte是8个bit，那么就是64个bit)

2. 添加元素

假设我们添加一个Key，经过hash计算后得到的值为7，那么意味着第7个位置为0，那么对应到Long的值为128，那么与此处之前的Long值进行或运算，意味着添加成功。

BitSet添加一个元素的过程

开源的实现

Guava: https://github.com/google/guava/blob/master/guava/src/com/google/common/hash/BloomFilter.java

优势与不足

优势：节省内存，通常可以降低70%左右的内存

不足：有一定的误判率、不可删除元素