java实现bloom filter

老吴2019-04-09 20:39后端371浏览


版权声明:本篇文章为原创文章,转载请注明出处。https://yao2san.com/article/2053

上一篇我们讲到了可以使用redis实现一个bloom filter,那么在这之前我首先来简要总结一下有关bloom filter的关键点,具体的bloom filter的介绍即原理就不在造轮子再写一次了,具体可以参照其他大牛的文章:

>

详解布隆过滤器的原理、使用场景和注意事项

布隆过滤器(Bloom Filter)详解

bloom filter的特点

在参看了大神们的文章后,我觉得bloom filter的特点可以归结为以下三个:

1.牺牲准确度换取空间

bloom filter是用多个hash函数来计算多个hash值,然后判断这些值对应的比特位上的的值是否为1,若都为1,则可能已经存在,若有一个为0,则必定不存在,由于即使使用多个hash函数进行计算,其结果也有可能冲突(即,某个值计算出的所有hash值处的bit位都已经被置为了1),所以,其结果不一定是准确的。但是由于使用类似bit数组的形式存储,每个bit位只占用一个字节,大大减少了存储空间。因此bloom是一个以准确度换取时间的算法。

2.假必假,真未必真

即若bloom filter判断某个值不存在,则一定不存在,反之则不一定。因为当判断其不存在时,意味着,至少又有一个比特位为0,所以必定在这之前没有出现过相同的数据;当判断某个值存在时,意味着所有bit位都为1,但是这些1有可能是之前的某些数据共同作用下而置为1的,所以有可能当前数据并不存在。所以说是假必假,真未必真

3不可删除

不可简单的认为对应的bit位置为0就算删除了,因为置为0后会影响到其他数据在该位上的值为0,很多数据都会受影响,而不仅仅是当前数据,若只为0后会导致这样的结果:在有重复的数据进来后,经过hash计算,定位到对应bit位时发现其为0,则判断该数据一定不存在,但是实际上是存在的,因为手动把它置0了,所以这就导致了误判,增加了误判率,而且置0的 位数越多,影响越大,所以说bloom是不可删除的。

4.保密性

因为bloom filter不存储真实数据,只是存了个bit数组,所以不影响数的安全性。

blomm filter的准确度

关于其误差的计算,以及最优hash函数个数的计算,这篇文章里已经给出了:https://www.cnblogs.com/liyulong1982/p/6013002.html,最后的结论就是:若使得误差在给定的范围内,则需要满足以下条件

其中p为误差,m为Bit位个数,n为实际数据量;

而hash函数的个数需满足:

其中p为误差,k为hash函数个数。

使用java实现bloom filter

下面使用java实现了一个简易版的bloom filter.

假设我们要求判断误差要小于1%,则由以上两个公式可以算得k≈7 m≈4800(假设数据量n=500),代码如下:


/**
 * Created by wxg on 2019/4/9 20:30
 */
public class BloomFilter {
    private int bitNum = 13;
    private int hashFunNum = 7;
    private boolean[] bitArray;
    private int capacity;

    public BloomFilter() {
        this.capacity = 2 << (bitNum - 1);
        this.bitArray = new boolean[capacity];
    }

    public boolean isExist(String value) {
        int[] index = index(value);
        boolean res = true;
        for (int idx : index) {
            if (!bitArray[idx]) {
                res = false;
                break;
            }
        }
        return res;
    }

    public void put(String value) {
        int[] index = index(value);
        for (int idx : index) {
            bitArray[idx] = true;
        }
    }

    public int[] index(String value) {
        int[] res = new int[hashFunNum];
        int h = hash(value);
        int h2 = h >>> 16;
        for (int i = 0; i < hashFunNum; i++) {
            int hash = h + h2 * i;
            if (hash < 0)

                hash = -hash;
            res[i] = hash % capacity;
            //System.out.println(hash);
        }
        return res;
    }

    public int hash(String value) {
        int h = value.hashCode();
        return h;
    }

    public int getBitNum() {
        return bitNum;
    }

    public void setBitNum(int bitNum) {
        this.bitNum = bitNum;
    }

    public int getHashFunNum() {
        return hashFunNum;
    }

    public void setHashFunNum(int hashFunNum) {
        this.hashFunNum = hashFunNum;
    }

    public boolean[] getBitArray() {
        return bitArray;
    }

    public void setBitArray(boolean[] bitArray) {
        this.bitArray = bitArray;
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }
}

测试:


    public class BloomFilterTest {
        @Test
        public void test() {
            BloomFilter bf = new BloomFilter();
            final int total = 500;
            int errorCount = 0;

            for (int i = 0; i < total; i++) {
                boolean isExist = bf.isExist(i+"");
                if (isExist) {
                    errorCount++;
                }
                bf.put(i+"");
            }
            System.out.println("数据量 " + total + ",bitmap容量 " + bf.getBitArray().length + "(2^" + bf.getBitNum() + "),hash次数  " + bf.getHashFunNum() + ",判别错误个数 " + errorCount + ",误差 " + (float) errorCount / total);
        }
    }

结果:


数据量 500,bitmap容量 8192(2^13),hash次数  7,判别错误个数 0,误差 0.0

可以看到全部判断正确,那把比特数组的长度改一下,改为12,即4096个比特位,测试结果如下:


数据量 500,bitmap容量 4096(2^12),hash次数  7,判别错误个数 0,误差 0.0

可以看到,仍然全对,再次修改为11:


数据量 500,bitmap容量 2048(2^11),hash次数  7,判别错误个数 96,误差 0.192

这下误差就比较大了,因此选取合适的比特位数可hash函数个数是很重要的,不能瞎写。

以上代码需要自己计算k和m,不方便,于是改进一下,由公式自动计算,改进后的代码如下:


public class BloomFilter {
    private float tolerance;
    private int capacity;

    private int hashFunNum;
    private boolean[] bitArray;
    private int bitArrayLen;

    public void init(float tolerance, int capacity) {
        this.bitArrayLen = bitArrayLen(tolerance, capacity);
        this.hashFunNum = hashFunNum(tolerance);
        this.bitArray = new boolean[bitArrayLen];
    }

    private int bitArrayLen(float tolerance, int capacity) {
        return (int) -(Math.log(tolerance) / (Math.log(2) * Math.log(2))) * capacity;
    }

    private int hashFunNum(float tolerance) {
        return (int) Math.ceil(-Math.log(tolerance) / Math.log(2));
    }

    public boolean isExist(String value) {
        int[] index = index(value);
        boolean res = true;
        for (int idx : index) {
            if (!bitArray[idx]) {
                res = false;
                break;
            }
        }
        return res;
    }

    public void put(String value) {
        int[] index = index(value);
        for (int idx : index) {
            bitArray[idx] = true;
        }
    }

    private int[] index(String value) {
        int[] res = new int[hashFunNum];
        int h = hash(value);
        int h2 = h >>> 16;
        for (int i = 0; i < hashFunNum; i++) {
            int hash = h + h2 * i;
            hash = hash % bitArrayLen;
            if (hash < 0)
                hash = -hash;
            res[i] = hash;
        }
        return res;
    }

    private int hash(String value) {
        int h = value.hashCode();
        return h;
    }

    public float getTolerance() {
        return tolerance;
    }

    public void setTolerance(float tolerance) {
        this.tolerance = tolerance;
    }

    public int getHashFunNum() {
        return hashFunNum;
    }

    public void setHashFunNum(int hashFunNum) {
        this.hashFunNum = hashFunNum;
    }

    public boolean[] getBitArray() {
        return bitArray;
    }

    public void setBitArray(boolean[] bitArray) {
        this.bitArray = bitArray;
    }

    public int getCapacity() {
        return capacity;
    }

    public void setCapacity(int capacity) {
        this.capacity = capacity;
    }

    public int getBitArrayLen() {
        return bitArrayLen;
    }

    public void setBitArrayLen(int bitArrayLen) {
        this.bitArrayLen = bitArrayLen;
    }
}

测试方法如下:


public class BloomFilterTest {
    @Test
    public void test() {
        BloomFilter bf = new BloomFilter();
        final int total = 1000_00;
        bf.init(0.01F, total);
        int errorCount = 0;

        for (int i = 0; i < total; i++) {
            boolean isExist = bf.isExist(i + "bloom filter");
            if (isExist) {
                errorCount++;
            }
            bf.put(i + "bloom filter");
        }
        System.out.println("数据量 " + total + ",bitmap容量 " + bf.getBitArrayLen() + ",hash次数  " + bf.getHashFunNum() + ",判别错误个数 " + errorCount + ",误差 " + (float) errorCount / total);
    }
}

分别对10万,100万,1000万,1亿的数据量进行误差测试,测试结果如下:

数据量 100000,bitmap容量 900000,hash次数  7,判别错误个数 169,误差 0.00169

数据量 1000000,bitmap容量 9000000,hash次数  7,判别错误个数 2719,误差 0.002719

数据量 10000000,bitmap容量 90000000,hash次数  7,判别错误个数 27196,误差 0.0027196

数据量 100000000,bitmap容量 900000000,hash次数  7,判别错误个数 1311073,误差 0.01311073

优化

主要优化点在于hash值的计算以及hash函数的选取,好的hash函数能够使得hash更分散,冲突越小,这样误检率就会越低。

赞一个! (1)

文章评论(如需发表图片,请转至留言)