【Redis】——布隆过滤器（10）

深藏阁楼爱情的钟 2022-12-28 01:46 181阅读 0赞

# 前言 #

前面在说缓存穿透的时候说到解决方案的时候正好有提到布隆过滤器，正好现在就来说一说这个布隆过滤器是怎么一回事，在说布隆过滤器之前可能需要先说下位图算法

# 位图 #

**位图**（**Bitmap**），又称**栅格图**（英语：**Raster graphics**）或**点阵图**，是使用[像素][Link 1][阵列][Link 2](Pixel-array/Dot-matrix[点阵][Link 3])来表示的[图像][Link 4]（摘自百度百科）。我们可以理解为是一个 bit 数组，每个元素存储数据的状态（由于每个元素只有 1 bit，所以只能存储 0 或 1 这 2 种状态）适用于数据量超大，但是数据的状态很少的情况。比如判断一个整数是否在给定的超大的整数集中。

# 布隆过滤器 #

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m，哈希函数的个数为k

![714644b5d633b3c206a7715cbdc4ab00.png][]

以上图为例，具体的操作流程：假设集合里面有3个元素\{x, y, z\}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候，同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。

**布隆过滤器添加元素**

*  将要添加的元素给k个哈希函数
 *  得到对应于位数组上的k个位置
 *  将这k个位置设为1

**布隆过滤器查询元素**

*  将要查询的元素给k个哈希函数
 *  得到对应于位数组上的k个位置
 *  如果k个位置有一个为0，则肯定不在集合中
 *  如果k个位置全部为1，则可能在集合中

# 代码实现 #

google的guava包中有对Bloom Filter的实现API：BloomFilter，下面是自己实现一个（摘自百度百科）

public class BloomFilter {
        /**
         * 一个长度为10 亿的比特位
         */
        private static final int DEFAULT_SIZE = 256 << 22;
    
        /**
         * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
         */
        private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61};
    
        /**
         * 相当于构建 8 个不同的hash算法
         */
        private static HashFunction[] functions = new HashFunction[seeds.length];
    
        /**
         * 初始化布隆过滤器的 bitmap
         */
        private static BitSet bitset = new BitSet(DEFAULT_SIZE);
    
        /**
         * 添加数据
         *
         * @param value 需要加入的值
         */
        public static void add(String value) {
            if (value != null) {
                for (HashFunction f : functions) {
                    //计算 hash 值并修改 bitmap 中相应位置为 true
                    bitset.set(f.hash(value), true);
                }
            }
        }
    
        /**
         * 判断相应元素是否存在
         *
         * @param value 需要判断的元素
         * @return 结果
         */
        public static 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) {
    
            for (int i = 0; i < seeds.length; i++) {
                functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);
            }
    
            // 添加1亿数据
            for (int i = 0; i < 100000000; i++) {
                add(String.valueOf(i));
            }
            String id = "123456789";
            add(id);
    
            System.out.println(contains(id));   // true
            System.out.println(contains("234567890"));  //false
            System.out.println(contains("100000000"));  //false
            System.out.println(contains("99999999"));  //true
        }
    }
    
    class HashFunction {
    
        private int size;
        private 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);
            }
            int r = (size - 1) & result;
            return r;
        }
    }

执行结果

Connected to the target VM, address: '127.0.0.1:62256', transport: 'socket'
    true
    false
    false
    true
    Disconnected from the target VM, address: '127.0.0.1:62256', transport: 'socket'

# 优缺点 #

**优点：**

1.查询时间复杂度 O(k) 一个较小的常数

2.极度节约空间

3.不存储数据本身，对源数据有一定保密性

**缺点：**

1.有一定误差

2.不能删除（不同的元素在添加进布隆过滤器时可能会在某些bit位上有相同的位图，删除某一元素会影响到其他元素，所以无法删除）

[Link 1]: https://baike.baidu.com/item/%E5%83%8F%E7%B4%A0
[Link 2]: https://baike.baidu.com/item/%E9%98%B5%E5%88%97
[Link 3]: https://baike.baidu.com/item/%E7%82%B9%E9%98%B5
[Link 4]: https://baike.baidu.com/item/%E5%9B%BE%E5%83%8F
[714644b5d633b3c206a7715cbdc4ab00.png]: /images/20221120/4eb56a30973843e0b3a439cfefccd747.png