← 返回学习路线

SYSTEM

位图

Java基础位图system
src/content/notes/system/位图.md

位图

基本介绍

布隆过滤器:一种数据结构,是一个很长的二进制向量(位数组)和一系列随机映射函数(哈希函数),既然是二进制,每个空间存放的不是 0 就是 1,但是初始默认值都是 0,所以布隆过滤器不存数据只存状态

这种数据结构是高效且性能很好的,但缺点是具有一定的错误识别率和删除难度。并且理论情况下,添加到集合中的元素越多,误报的可能性就越大


工作流程

向布隆过滤器中添加一个元素 key 时,会通过多个 hash 函数得到多个哈希值,在位数组中把对应下标的值置为 1

布隆过滤器查询一个数据,是否在二进制的集合中,查询过程如下:

  • 通过 K 个哈希函数计算该数据,对应计算出的 K 个 hash 值
  • 通过 hash 值找到对应的二进制的数组下标
  • 判断方法:如果存在一处位置的二进制数据是 0,那么该数据一定不存在。如果都是 1,则认为数据存在集合中(会误判)

布隆过滤器优缺点:

  • 优点:

    • 二进制组成的数组,占用内存极少,并且插入和查询速度都足够快
    • 去重方便:当字符串第一次存储时对应的位数组下标设置为 1,当第二次存储相同字符串时,因为对应位置已设置为 1,所以很容易知道此值已经存在
  • 缺点:

    • 随着数据的增加,误判率会增加:添加数据是通过计算数据的 hash 值,不同的字符串可能哈希出来的位置相同,导致无法确定到底是哪个数据存在,这种情况可以适当增加位数组大小或者调整哈希函数
    • 无法删除数据:可能存在几个数据占据相同的位置,所以删除一位会导致很多数据失效
  • 总结:布隆过滤器判断某个元素存在,小概率会误判。如果判断某个元素不在,那这个元素一定不在

参考文章:https://www.cnblogs.com/ysocean/p/12594982.html


Guava

引入 Guava 的依赖:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.0-jre</version>
</dependency>

指定误判率为(0.01):

public static void main(String[] args) {
    // 创建布隆过滤器对象
    BloomFilter<Integer> filter = BloomFilter.create(
        Funnels.integerFunnel(),
        1500,
        0.01);
    // 判断指定元素是否存在
    System.out.println(filter.mightContain(1));
    System.out.println(filter.mightContain(2));
    // 将元素添加进布隆过滤器
    filter.put(1);
    filter.put(2);
    System.out.println(filter.mightContain(1));
    System.out.println(filter.mightContain(2));
}

实现布隆

class MyBloomFilter {
    //布隆过滤器容量
    private static final int DEFAULT_SIZE = 2 << 28;
    //bit数组,用来存放key
    private static BitSet bitSet = new BitSet(DEFAULT_SIZE);
    //后面hash函数会用到,用来生成不同的hash值,随意设置
    private static final int[] ints = {1, 6, 16, 38, 58, 68};

    //add方法,计算出key的hash值,并将对应下标置为true
    public void add(Object key) {
        Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
    }

    //判断key是否存在,true不一定说明key存在,但是false一定说明不存在
    public boolean isContain(Object key) {
        boolean result = true;
        for (int i : ints) {
            //短路与,只要有一个bit位为false,则返回false
            result = result && bitSet.get(hash(key, i));
        }
        return result;
    }

    //hash函数,借鉴了hashmap的扰动算法
    private int hash(Object key, int i) {
        int h;
        return key == null ? 0 : (i * (DEFAULT_SIZE - 1) & ((h = key.hashCode()) ^ (h >>> 16)));
    }
}