Java教程

Java 布隆过滤器

本文主要是介绍Java 布隆过滤器,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

实际上就是一个额很长的二进制向量![在这里插入图片描述](https://www.www.zyiz.net/i/ll/?i=fcc694c61f324e43a1f85686bacbfd4f.png?,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAU3BhcmE=,size_20,color_FFFFFF,t_70,g_se,x_1
布隆过滤器本质上是一个巨大的二进制数组,以Redis中的布隆过滤器实现为例,Redis中的布隆过滤器底层是一个大型位数组(二进制数组)+多个无偏hash函数。

多个无偏hash函数:

无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数,能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图,其中k1、k2代表增加的元素,a、b、c即为无偏hash函数,最下层则为二进制数组。

在这里插入图片描述
注意,这里abc是三个Hash函数,k1和k2是两个要存进来的数据。存进来以后,某几个位置上就被置为1。

在查询的时候,要计算该元素的三个hash函数,然后去找每个位置上的0或者1,如果所有的都是1,就是存在,如果有任何一个位置为0,就不存在。

但是,这也会导致误判,因为某些元素会计算得出相同的位,也就是说在计算中会出现误判——把不存在于数据中的元素当成了存在的。

同样,也不能删除,因为删除会删除掉其他数据。

public static void main(String[] args){
        int capacity = 100000;
        /** 初始化容量为10万大小的字符串布隆过滤器,默认误差率为0.03
         *  布隆过滤器容量为10万并非指bitmap的长度就是10万,因为需要考虑到存在hash冲突的情况,所以bitmap的实际长度要比10万要大很多
         *  bitmap长度比需要存在的数据量大小越大,误差率会越低
         * */
        BloomFilter bloomFilter =BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), capacity);

        Set<String> sets = new HashSet<>();
        List<String> lists = new ArrayList<>();

        for (int i =0;i< capacity; i++){
            String str = UUID.randomUUID().toString();
            bloomFilter.put(str);
            sets.add(str);
            lists.add(str);
        }

        int existsCount = 0;
        int mightExistsCount = 0;

        for(int i=0;i<10000;i++){
            //如果i为100倍数,取实际的值;否则就随机一个字符串
            String data = i%100==0?lists.get(i/100):UUID.randomUUID().toString();
            /** 通过布隆过滤器判断字符串是否存在*/
            if(bloomFilter.mightContain(data)){
                /** 如果布隆过滤器认为存在,则表示可能存在的数量mightExistsCount自增1*/
                mightExistsCount++;
                /** 如果set中存在则existsCount自增1*/
                if(sets.contains(data)){
                    existsCount++;
                }
            }
        }

        //测试总次数
        BigDecimal total = new BigDecimal(10000);
        //错误总次数
        BigDecimal error = new BigDecimal(mightExistsCount - existsCount);
        //误差率
        BigDecimal rate = error.divide(total, 2, BigDecimal.ROUND_HALF_UP);

        System.out.println("初始化10万条数据,判断100个真实数据,9900个不存在数据");
        System.out.println("实际存在的字符串个数为:" + existsCount);
        System.out.println("布隆过滤器认为存在的个数为:" + mightExistsCount);
        System.out.println("误差率为:" + rate.doubleValue());
    }

影响误判率的主要因素就是 布隆过滤器数据所占的空间大小,以及哈希方法的个数。

如果需要误判率低,就需要布隆过滤器空间更大,以及哈希方法更多。

这篇关于Java 布隆过滤器的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!