Skip to content

Latest commit

 

History

History
263 lines (213 loc) · 8.46 KB

布隆过滤器.md

File metadata and controls

263 lines (213 loc) · 8.46 KB
Raw

基础知识

哈希函数

将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。

特点：

  • 单向散列函数：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。
  • 散列碰撞：散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同

用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

布隆过滤器

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除元素困难

  • 判断元素如果不在集合内，那么一定不在
  • 判断元素如果在集合内，那么不一定在
  • 从上面两点可以看出删除元素的问题，因为有可能会误删除

数据结构

布隆过滤器(BloomFilter )是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，它的所有位都被置为0：

000000000000000000000000000000000000

往布隆过滤器中添加一个元素时，我们将这个值传入 k 个hash函数，然后将结果位置bit置为1,例如k=3

000000000100000010000000100000000000

此时可以看出，当我们插入元素时，有可能存在bit位置是其他元素的结果，此时就会存在误判率。

  • 如果这些点有任何一个 0，则被查询变量一定不在；
  • 如果都是 1，则被查询变量很可能存在

误判率

通过数据结构我们可以看出，有可能多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射为 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。

Guava实现布隆过滤器

package com.redis.advanced.pierce;

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

/**
 * Guava实现布隆过滤器
 * TODO 基本原理
 * @author lizhifu
 * @date 2021/1/14
 */
public class GuavaBloomFilter {
    /**
     * 预计要插入多少数据
     */
    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) {
        //插入数据
        for (int i = 0; i < 10 ; i++) {
            bloomFilter.put(i);
        }
        for (int i = 10; i < 20 ; i++) {
            System.out.println("========"+bloomFilter.mightContain(i));
        }
    }
}

当误判率大小为0.1时，k为3。当误判率大小为0.01时，k为7(k为hash函数次数)

redis布隆过滤器

模仿guava实现布隆过滤器

package com.redis.advanced.service;

import com.google.common.base.Preconditions;
import com.google.common.hash.Funnel;
import com.google.common.hash.Hashing;

/**
 * 布隆过滤器
 * 0代表不存在某个数据，1代表存在某个数据,一般不能删除布隆过滤器里的数据
 * 代码来源于{@link com.google.common.hash.BloomFilter}
 * @author lizhifu
 * @date 2020/12/9
 */
public class BloomFilterHelper<T> {
    private int numHashFunctions;
    private int bitSize;
    /**
     * Guava中定义的一个接口，它和PrimitiveSink配套使用，
     * 主要是把任意类型的数据转化成Java基本数据类型（primitive value，如char，byte，int……）
     * ，默认用java.nio.ByteBuffer实现，最终均转化为byte数组
     */
    private Funnel<T> funnel;

    /**
     * 初始化
     * @param funnel
     * @param expectedInsertions 预计插入量
     * @param fpp 可接受的错误率
     */
    public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
        Preconditions.checkArgument(funnel != null, "funnel不能为空");
        this.funnel = funnel;
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }

    /**
     * 散列时，此策略使用Hashing.murmur3_128所有128位。
     * 它看起来与MURMUR128_MITZ_32中的实现不同，
     * 因为我们避免了循环中的乘法，并且执行了（更简单）+ = hash2。
     * 我们还通过与Long.MAX_VALUE进行“与”操作而不是翻转位来将索引更改为正数
     * @param value
     * @return
     */
    public int[] murmurHashOffset(T value) {
        int[] offset = new int[numHashFunctions];

        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);
        for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
                nextHash = ~nextHash;
            }
            offset[i - 1] = nextHash % bitSize;
        }

        return offset;
    }

    /**
     * 拿来用的
     * 计算m（Bloom过滤器的总位），对于指定的预期插入，该m将达到所需的误报概率。
     * n –预期插入（必须为正）
     * p –误报率（必须为0 <p <1）
     */
    private int optimalNumOfBits(long n, double p) {
        if (p == 0) {
            // 设定最小期望长度
            p = Double.MIN_VALUE;
        }
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 给定预期的插入次数和布隆过滤器中的位数，计算最佳k（布隆过滤器中插入的每个元素的哈希数）
     * 参数：
     * n –预期插入（必须为正）
     * m –布隆过滤器中的总位数（必须为正）
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

初始化：

    @Bean
    public BloomFilterHelper<String> initBloomFilterHelper() {
        return new BloomFilterHelper<>((Funnel<String>) (from, into) ->
                into.putString(from, Charsets.UTF_8).putString(from, Charsets.UTF_8),
                1000000, 0.01);
    }

如何使用：

/**
     * 根据给定的布隆过滤器判断值是否存在
     *
     * @param bloomFilterHelper 布隆过滤器对象
     * @param key               KEY
     * @param value             值
     * @param <T>               泛型，可以传入任何类型的value
     * @return 是否存在
     */
    public <T> boolean includeByBloomFilter(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
        int[] offset = bloomFilterHelper.murmurHashOffset(value);
        for (int i : offset) {
            if (!redisTemplate.opsForValue().getBit(key, i)) {
                return false;
            }
        }
        return true;
    }

代码位置：https://github.com/lizhifuabc/spring-learn/tree/main/spring-boot-redis-advanced

使用redisson实现布隆过滤器

代码位置：https://github.com/lizhifuabc/spring-learn/tree/main/spring-boot-redis-redisson

package com.redis.redisson;

import org.junit.jupiter.api.Test;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.boot.test.context.SpringBootTest;

import jakarta.annotation.Resource;

/**
 * RedisBloomFilter
 *
 * @author lizhifu
 * @date 2021/1/14
 */
@SpringBootTest
public class RedisBloomFilterTest {
    @Resource
    private RedissonClient redissonClient;
    @Test
    public void test(){
        // 获取布隆过滤器
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("userList");
        //初始化布隆过滤器：预计元素为1wL,误差率为0.01
        bloomFilter.tryInit(10000,0.01);

        for (int i = 0; i < 10000; i++) {
            bloomFilter.add("testtest" + i);
        }
        int count = 0;
        for (int i = 0; i < 100; i++) {
            if (bloomFilter.contains("testtest" + i)) {
                count++;
            }
        }
        // 匹配数量 100
        System.out.println("匹配数量 " + count);
    }
}