侧边栏壁纸
博主头像
Monkey部落博主等级

Monkey部落,分享技术、经验、遇到的问题及解决方法,欢迎大家互相讨论分享。

  • 累计撰写 59 篇文章
  • 累计创建 36 个标签
  • 累计收到 2 条评论

目 录CONTENT

文章目录

Bloom Filter概念和实现原理

Monkey部落
2022-10-10 / 0 评论 / 1 点赞 / 163 阅读 / 1,085 字
温馨提示:
本文最后更新于 2022-10-18,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

Bloom Filter概念和实现原理

背景

我们在判断某一个元素是否在某个集合里面时,一般是将集合里面的所有元素都保存下来,然后直接读取磁盘上的数据再进行判断,但是如果数据量很大,此时读取速度就会降低,这时我们可以将数据提前存储到内存中,内存读取速度会快很多,但是数据量在逐渐增大时,内存的开销也在逐渐增大,检索的时间也会变长。此时,在数据量特别大的情况下,需要一个时间和空间上都具有优势的数据结构。

介绍

Bloom Filter是由Howard Bloom在1970年提出的二进制向量数据结构,它具有较好的时间和空间效率,用来检测一个元素是否在某个集合中,但是缺点是,有一定的错误率和删除困难。

原理

Bloom Filter判断某一个元素是否在集合中时,会将集合中的每一个元素都通过K个不同的Hash函数映射到一个bit数组里面的K个点,每个点设置为1。此时检索一个元素时,只需要将该元素同样进行K个不同的Hash函数,求得K个点位,如果这K个点位全部是1,则代表元素可能在集合里面,如果有一个为0,则代表元素不在集合里面。

image-20221010141654427

公式

  1. Bit数组大小的计算

    需要根据预估的数据量n以及错误率p来计算Bit数组的大小m:

    m=nlnp(ln2)2m=- \frac {n \ln {p}} {(\ln {2})^2}

  2. Hash函数个数k计算

    根据预估的数据量n和已经求得的Bit数组长度m,可以计算出Hash函数的个数k:

    k=mnln2k=\frac {m} {n} \ln {2}

代码实现

/**
 * All rights Reserved, Designed By monkey.blog.xpyvip.top
 *
 * @version V1.0
 * @Package PACKAGE_NAME
 * @Description:
 * @Author: xpy
 * @Date: Created in 2022年10月09日 4:42 下午
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(calNumOfBits(3,0.1));
        System.out.println(calNumOfHashFuns(3, 14));
    }

    /**
     * 计算bit数组大小m
     * @param n 预估的数据量
     * @param p 错误率 在0-1之间 0<p<1
     * @return
     */
    private static long calNumOfBits(long n, double p){
        if(p == 0){
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 计算最佳需要多少个hash函数,即k值
     * @param n 预估的数据量
     * @param m bit数组大小m
     * @return
     */
    private static int calNumOfHashFuns(long n, long m){
        return  Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
}

实际Bloom Filter使用

  1. 使用hutool里面的Bloom Filter

    /**
     * All rights Reserved, Designed By monkey.blog.xpyvip.top
     *
     * @version V1.0
     * @Package PACKAGE_NAME
     * @Description:
     * @Author: xpy
     * @Date: Created in 2022年10月09日 4:42 下午
     */
    public class Test {
        public static void main(String[] args) {
            BitMapBloomFilter bitMapBloomFilter = new BitMapBloomFilter(8);
            bitMapBloomFilter.add("test123");
            bitMapBloomFilter.add("tset123456");
            System.out.println(bitMapBloomFilter.contains("test123"));
            System.out.println(bitMapBloomFilter.contains("test12"));
        }
    }
    
  2. 使用Google的guava包

    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    
    import java.nio.charset.Charset;
    
    /**
     * All rights Reserved, Designed By monkey.blog.xpyvip.top
     *
     * @version V1.0
     * @Package PACKAGE_NAME
     * @Description:
     * @Author: xpy
     * @Date: Created in 2022年10月09日 4:42 下午
     */
    public class Test {
        public static void main(String[] args) {
            // 设置预估的数据量在1000000,错误率在0.01
            BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 1000000, 0.01);
            bloomFilter.put("test123");
            bloomFilter.put("test123456");
            bloomFilter.put("tset123456");
            System.out.println(bloomFilter.mightContain("test123456"));
            System.out.println(bloomFilter.mightContain("tset12"));
        }
    }
    

扩展

  1. 错误率

    Bloom Filter存在判断错误的情况,适用于允许存在判断错误的场景。

  2. 不允许删除

    删除其中某一个元素,需要将该元素对应的bit位设置为0,但是很可能有其他元素对应,所以不能删除,设置为0。

关注微信公众号「平哥技术站」, 每日更新,在手机上阅读所有教程,随时随地都能学习。

觉得写的还不错的小伙伴,请作者喝杯咖啡☕ ,支持一下。😊

如有侵权请立即与我们联系,我们将及时处理,联系邮箱:865934097@qq.com。

1

评论区