布隆过滤器使用

简介: 关于布隆过滤器使用简单情形

布隆过滤器使用场景

  1. 判断给定数据是否存在:比如判断一个数字是否存在于包含大量数字的数字集中(数字集很大,上亿)、 防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)等等、邮箱的垃圾邮件过滤(判断一个邮件地址是否在垃圾邮件列表中)、黑名单功能(判断一个IP地址或手机号码是否在黑名单中)等等。
  2. 去重:比如爬给定网址的时候对已经爬取过的 URL 去重、对巨量的 QQ号/订单号去重。

去重场景也需要用到判断给定数据是否存在,因此布隆过滤器主要是为了解决海量数据的存在性问题。

# 编码实战

# 通过 Java 编程手动实现布隆过滤器

我们上面已经说了布隆过滤器的原理,知道了布隆过滤器的原理之后就可以自己手动实现一个了。

如果你想要手动实现一个的话,你需要:

  1. 一个合适大小的位数组保存数据
  2. 几个不同的哈希函数
  3. 添加元素到位数组(布隆过滤器)的方法实现
  4. 判断给定元素是否存在于位数组(布隆过滤器)的方法实现。

下面给出一个我觉得写的还算不错的代码(参考网上已有代码改进得到,对于所有类型对象皆适用):

import java.util.BitSet;
public class MyBloomFilter {
    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};
    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];
    /**
     * 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }
    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }
    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }
    /**
     * 静态内部类。用于 hash 操作!
     */
    public static class SimpleHash {
        private int cap;
        private int seed;
        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }
        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }
    }
}

测试:

String value1 = "https://javaguide.cn/";
String value2 = "https://github.com/Snailclimb";
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));

Output:

false
false
true
true

测试:

Integer value1 = 13423;
Integer value2 = 22131;
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));
filter.add(value1);
filter.add(value2);
System.out.println(filter.contains(value1));
System.out.println(filter.contains(value2));

Output:

false
false
true
true

# 利用 Google 开源的 Guava 中自带的布隆过滤器

自己实现的目的主要是为了让自己搞懂布隆过滤器的原理,Guava 中布隆过滤器的实现算是比较权威的,所以实际项目中我们不需要手动实现一个布隆过滤器。

首先我们需要在项目中引入 Guava 的依赖:

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

实际使用如下:

我们创建了一个最多存放 最多 1500 个整数的布隆过滤器,并且我们可以容忍误判的概率为百分之(0.01)

// 创建布隆过滤器对象
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));

在我们的示例中,当 mightContain() 方法返回 true 时,我们可以 99%确定该元素在过滤器中,当过滤器返回 false 时,我们可以 100%确定该元素不存在于过滤器中。

Guava 提供的布隆过滤器的实现还是很不错的(想要详细了解的可以看一下它的源码实现),但是它有一个重大的缺陷就是只能单机使用(另外,容量扩展也不容易),而现在互联网一般都是分布式的场景。为了解决这个问题,我们就需要用到 Redis 中的布隆过滤器了。


著作权归Guide所有 原文链接:https://javaguide.cn/cs-basics/data-structure/bloom-filter.html#%E5%88%A9%E7%94%A8-google-%E5%BC%80%E6%BA%90%E7%9A%84-guava-%E4%B8%AD%E8%87%AA%E5%B8%A6%E7%9A%84%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

目录
相关文章
|
机器学习/深度学习 算法 vr&ar
数学建模三大类模型适用场景及建模方法(纯干货)
如果评价指标个数过多(一般超过9个),利用层次分析法所得到的权重就有-定的偏差,继而组合评价模型的结果就不再可靠。可以根据评价对象的实际情况和特点,利用一定的方法,将各原始指标分层和归类,使得每易各类中的指标数少于9个。
4537 0
数学建模三大类模型适用场景及建模方法(纯干货)
|
自然语言处理 供应链 数据可视化
大数据在市场营销中的应用案例:精准洞察,驱动增长
【8月更文挑战第25天】大数据在市场营销中的应用案例不胜枚举,它们共同展示了大数据技术在精准营销、市场预测、用户行为分析等方面的巨大潜力。通过深度挖掘和分析数据,企业能够更加精准地洞察市场需求,优化营销策略,提升市场竞争力。未来,随着大数据技术的不断发展和普及,其在市场营销领域的应用将更加广泛和深入。
2944 3
|
12月前
|
数据采集 Web App开发 JavaScript
Selenium爬虫技术:如何模拟鼠标悬停抓取动态内容
本文介绍了如何使用Selenium爬虫技术抓取抖音评论,通过模拟鼠标悬停操作和结合代理IP、Cookie及User-Agent设置,有效应对动态内容加载和反爬机制。代码示例展示了具体实现步骤,帮助读者掌握这一实用技能。
520 0
Selenium爬虫技术:如何模拟鼠标悬停抓取动态内容
|
Java Android开发 UED
安卓应用开发中的内存管理优化技巧
在安卓开发的广阔天地里,内存管理是一块让开发者既爱又恨的领域。它如同一位严苛的考官,时刻考验着开发者的智慧与耐心。然而,只要我们掌握了正确的优化技巧,就能够驯服这位考官,让我们的应用在性能和用户体验上更上一层楼。本文将带你走进内存管理的迷宫,用通俗易懂的语言解读那些看似复杂的优化策略,让你的开发之路更加顺畅。
250 2
|
机器学习/深度学习 大数据 数据处理
存内计算市场规模到 2030 年将突破 526 亿美元
存内计算市场规模到 2030 年将突破 526 亿美元
287 10
|
存储 小程序 开发者
微信小程序猜拳游戏步骤及代码
微信小程序猜拳游戏步骤及代码
315 0
|
JavaScript 前端开发 API
Vue.js入门指南:从基础到进阶,掌握现代JavaScript框架的核心概念与高级特性(2W字小白教程)
Vue.js入门指南:从基础到进阶,掌握现代JavaScript框架的核心概念与高级特性(2W字小白教程)
319 0
|
SQL 关系型数据库 MySQL
这篇MySQL主从复制与分库分表读取分离稳了!
这篇MySQL主从复制与分库分表读取分离稳了!
281 0
|
NoSQL Cloud Native 关系型数据库
阿里云数据库是什么?阿里云数据库的优势和应用场景
阿里云数据库是什么?阿里云数据库的优势和应用场景
641 0
|
机器学习/深度学习 存储 人工智能
模型压缩技术综述
模型压缩技术综述
634 0