
import java.util.BitSet;
 
class SimpleHash {
 
    public int cap;//当前容量
    public int seed;//随机
 
    public SimpleHash(int cap,int seed) {
        this.cap = cap;
        this.seed = seed;
    }
 
    //模仿库中哈希写哈希函数：
    //根据seed的不同，创建不同的哈希函数
    int hash(String key) {
        int h;
        return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }
 
}
public class MyBloomFilter {
    //导入库中的位图
    public BitSet bitSet;
 
    //记录存储了多少数据
    public int usedSize;
 
    //随机种子
    public static final int[] seeds = {3,5,9,11,15,19,25,31};//这里面的数字是随便设置的
 
    public SimpleHash[] simpleHashes;
 
    public static final int SIZE = 1 << 20;//这个20是随意给的
 
    public MyBloomFilter() {
        bitSet = new BitSet(SIZE);
        simpleHashes = new SimpleHash[seeds.length];
 
        for(int i = 0;i<simpleHashes.length;i++) {
            simpleHashes[i] = new SimpleHash(SIZE,seeds[i]);
        }
    }
 
    /**
     * 添加数据 到布隆过滤器
     * @param val
     */
    public void add(String val) {
        //3个哈希函数，分别处理当前的数据
        //把他们都存储在位图中即可
 
    }
 
    /**
     * 是否包含val，会存在误判
     * @param val
     * @return
     */
    public boolean contains(String val) {
 
    }
 
}

补充上述代码空缺部分：

5.1、添加元素


    /**
     * 添加数据 到布隆过滤器
     * @param val
     */
    public void add(String val) {
        //3个哈希函数，分别处理当前的数据
 
        for (SimpleHash simpleHash : simpleHashes) {
            int index = simpleHash.hash(val);
            //把他们都存储在位图中即可
            bitSet.set(index);
        }
        usedSize ++;
    }

5.2、查询元素


    /**
     * 是否包含val，会存在误判
     * @param val
     * @return
     */
    public boolean contains(String val) {
        for (SimpleHash simpleHash : simpleHashes) {
            int index = simpleHash.hash(val);
            boolean flg = bitSet.get(index);
            if(!flg) {
                return false;
            }
        }
        return true;
    }

5.3、测试：


    //测试
    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("baidu1");
        myBloomFilter.add("baidu2");
        myBloomFilter.add("tencent");
 
        System.out.println(myBloomFilter.contains("baidu1"));//true
        System.out.println(myBloomFilter.contains("haha"));//false
    }

6、guava实现布隆过滤器

创建一个maven项目
导入依赖
测试

依赖：


        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>19.0</version>
        </dependency>

测试：


import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
 
 
public class Test {
    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 < 1000000; i++) {
            bloomFilter.put(i);
        }
        int count = 0;
        for (int i = 1000000; i < 2000000; i++) {
            if (bloomFilter.mightContain(i)) {
                count++;
                System.out.println(i + "误判了");
            }
        }
        System.out.println("总共的误判数:" + count);
    }
}

测试结果：

7、布隆过滤器适用场景

网页爬虫中对URL的去重，避免爬取相同的URL地址
垃圾邮件过滤，从数十亿个垃圾邮件列表中判断邮箱是否是垃圾邮箱
秒杀系统，查看用户是否重复购买
数据库防止穿库。 Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。
业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务
Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

好啦！！！我们下期再见咯~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/497466