您现在的位置是:首页 > 正文

布隆过滤器使用总结

2024-04-01 02:58:43阅读 2

简介

简单来说,布隆过滤器(BloomFilter)是一种数据结构。特点是存在性检测如果布隆过滤器中不存在,那么实际数据一定不存在如果布隆过滤器中存在,实际数据不一定存在。相比于传统数据结构(如:List、Set、Map等)来说,它更高效,占用空间更少。缺点是它对于存在的判断是具有概率性。

原理

布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组(或者叫位向量)和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k。

以上图为例,具体的插入数据和校验是否存在的流程:
假设集合里面有3个元素{x, y, z},哈希函数的个数为3。
Step1:将位数组初始化,每位都设置为0。
Step2:对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,哈希值对应位数组上面的一个点,将该位置标记为1。
Step3:查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。
Step4:如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。

应用场景

高效在海量数据中做存在性判断,例如爬虫url去重。 

如果需要在分布式应用中做存在性判断,可以用redis实现布隆过滤器。

用redis防止缓冲穿透而使用了布隆过滤器

例如:有一个需求,分布式处理数据以后,然后存储mysql中,但是即便在入库前查询数据库做存在判断,还是会出现很多插入重复异常,因为无法确报本进程做完查重操作后其他进程是否插入了相同数据。因此在入库前再用redis的布隆过滤器做一次存在判断,存在说明数据插入,不存在则说明数据没有插入,同时对布隆过滤器做添加。


布隆过滤器为什么可以防止缓冲穿透

解答这个问题前,先来看看缓冲穿透是怎么回事。百度百科给的概念是:“缓存穿透是指查询一个一定不存在的数据,由于缓存是不命中时需要从数据库查询,查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到数据库去查询,进而给数据库带来压力。”,由此可见,缓冲穿透的特点是访问查询的数据一定在缓冲和数据库中都不存在。而一般在数据库存在的数据会通过配置自动同步或更新到缓存中,如果数据库中不存在的数据,那么就不会同步到缓存中,自然缓存中也不存在。反过来说,缓存中不存在的数据,数据库中肯定不存在。所以,当这样不存在的数据到达缓存层经过不存在的过滤,并及时返回结果,这样的数据自然也不会到达数据库的。布隆过滤器虽然对存在数据的过滤具有误报率的缺点,但是对数据做不存在的过滤是100%准确的。所以布隆过滤器可以防止缓存穿透。而且前面简介中提到了它的优点是高效,占用空间更少。尤其针对上亿级数据,在高并发场景下,,它的性能更优。

实现

guava实现

依赖

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

代码实现 

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.Funnels;
  
public class GuavaBloomFilter {
    public static void main(String[] args) {
       BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);
 
       bloomFilter.put("10086");
 
       System.out.println(bloomFilter.mightContain("123456"));
       System.out.println(bloomFilter.mightContain("10086"));
   }
}

 hutool实现

依赖

<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>5.6.0</version>
</dependency>

代码实现

// 初始化
BitMapBloomFilter filter = new BitMapBloomFilter(10);
filter.add("123");
filter.add("abc");
filter.add("ddd");
// 查找
filter.contains("abc")

Redission实现

依赖

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.16.7</version>
</dependency> 

代码实现

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
 
public class RedissonBloomFilter {
    public static void main(String[] args) {
         Config config = new Config();
         config.useSingleServer().setAddress("redis://192.168.10.182:6379");
         config.useSingleServer().setPassword("isi_redis_123");
         //构造Redisson
         RedissonClient redisson = Redisson.create(config);
 
         RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");
         //初始化布隆过滤器:预计元素为100000000L,误差率为3%
         bloomFilter.tryInit(100000000L,0.03);
         //将号码10086插入到布隆过滤器中
         bloomFilter.add("10086");
 
         //判断下面号码是否在布隆过滤器中
         System.out.println(bloomFilter.contains("123456"));//false
         System.out.println(bloomFilter.contains("10086"));//true
        redisson.shutdown();
     }
 }

 Redis自定义实现

依赖

<!-- jedis -->
<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>2.8.1</version>
</dependency>

代码实现 

import redis.clients.jedis.Jedis;

public class RedisBloomFilter {
    // 初始化集合长度
    private static final int length = Integer.MAX_VALUE;
    // 准备hash计算次数
    private static final int HASH_LENGTH = 5;
    /**
     * 准备自定义哈希算法需要用到的质数,因为一条数据需要hash计算5次 且5次的结果要不一样
     */
    private static int[] primeNums = new int[] { 17, 19, 29, 31, 37 };

    /**
     * 添加元素到bitSet中
     * @param target  要判定是否存在的元素
     * @param bit_key 布隆过滤器key
     * @param jedis
     */
    public static void addKey(String target,String bit_key,Jedis jedis) {
        for (int i : primeNums) {
            // 计算hashcode
            int hashcode = hash(target, i);
            // 计算映射在bitset上的位置
            int bitIndex = hashcode & (length - 1);
            jedis.setbit(bit_key, bitIndex, true);
        }
    }

    /**
     * 判断bitSet中是否有被查询的的key(经过hash处理之后的)
     * @param target 要判定是否存在的元素
     * @param bit_key 布隆过滤器key
     * @param jedis
     * @return
     */
    public static boolean hasKey(String target,String bit_key,Jedis jedis) {
        for (int i : primeNums) {
            // 计算hashcode
            int hashcode = hash(target, i);
            // 计算映射在bitset上的位置
            int bitIndex = hashcode & (length - 1);
            // 只要有一个位置对应不上,则返回false
            if (!jedis.getbit(bit_key, bitIndex)) {
                return false;
            }
        }
        return true;
    }
    /**
     * 自定义hash函数
     * @param target
     * @param prime
     * @return
     */
    private static int hash(String target,int prime) {
        int h = 0;
        char[] value = target.toCharArray();
        if (h == 0 && value.length > 0) {
            char val[] = value;
            for (int i = 0; i < value.length; i++) {
                h = prime * h + val[i];
            }
        }
        return h;
    }

    public static void main(String[] args) {
        Jedis jedis = RedisConfig.getConn();
        String bit_key="bloom2";
        RedisBloomFilter.addKey("username",bit_key,jedis);
        RedisBloomFilter.addKey("username1",bit_key,jedis);
        System.out.println(RedisBloomFilter.hasKey("username",bit_key,jedis));//true
        System.out.println(RedisBloomFilter.hasKey("username1",bit_key,jedis));//true
        System.out.println(RedisBloomFilter.hasKey("username2",bit_key,jedis));//false

        RedisConfig.close(jedis);
    }
}

来源

布隆过滤器的原理_快马扬鞭的博客-CSDN博客_布隆过滤器原理

java redis 布隆过滤器_Hefei19881002的博客-CSDN博客

布隆过滤器原理理解分享_金戈拉斯的博客-CSDN博客_布隆过滤器的原理

Redis 之布隆过滤器_wang0112233的博客-CSDN博客_redis布隆过滤器

网站文章

  • 负载均衡调度算法大全

    负载均衡调度算法大全

    http://www.open-open.com/lib/view/open1416560538742.html负载主机可以提供很多种负载均衡方法,也就是我们常说的调度方法或算法:轮循(Round Robin)这种方法会将收到的请求循环分配到服务器集群中的每台机器,即有效服务器。如果使用这种方式,所有的标记进入虚拟服务的服务器应该有相近的资源容量 以及负载形同的

    2024-04-01 02:58:02
  • 计算机毕设ssmAndroid的问卷调查管理系统9q4d4(开题+源码)

    计算机毕设ssmAndroid的问卷调查管理系统9q4d4(开题+源码)

    通过该系统,研究者能够灵活地设计问卷题目,方便地发布和管理问卷,高效地收集和分析调查数据。研究方案和预期成果: 本研究将采用软件开发的方法,结合Android平台的特点,设计并实现一款功能完善、易于使...

    2024-04-01 02:57:56
  • Unity ToLua 使用教程

    Unity ToLua 使用教程

    下载地址https://github.com/jarjin/LuaFramework_NGUIhttps://github.com/jarjin/LuaFramework_UGUI环境搭建(1) 生成...

    2024-04-01 02:57:49
  • stringRedisTemplate中ValueOperations设置值

    stringRedisTemplate中ValueOperations设置值

    stringRedisTemplate中ValueOperations设置值

    2024-04-01 02:57:08
  • TZ_13_微服务场景Eureka

    1.搭建Eureka的注册中心 Eureka服务中心 application.yaml文件的配置#配置自己的端口号server: port: 10086#配置注册中心让自己也能注册到自己 Client就不会因为注册不到自己而报错了eureka: client: service-url: defaultZone: http://...

    2024-04-01 02:57:01
  • springboot自动装配的原理

    @EnableAutoConfiguration实现的关键在于引入了AutoConfigurationImportSelector,其核心逻辑为selectImports方法, 逻辑大致如下:从spr...

    2024-04-01 02:56:54
  • 阿里云海外服务器需要备案吗?海外服务器地域节点分布表

    阿里云海外服务器需要备案?云吞铺子:当然不需要备案!阿里云地域节点覆盖全球,云吞铺子分享海外服务器地域节点分布表:海外服务器需要备案吗?购买阿里云海外服务器需要备案吗?不需要备案!海外服务器地域节点分布表随着时间推移,阿里云会支持越来越多的地域节点,精准信息请以官方文档为准:地域和可用区 - 阿里云地域名称所在城市Region ID可...

    2024-04-01 02:56:48
  • 【深度学习笔记1.1】人工神经网络(内含模型保存与恢复介绍)

    【深度学习笔记1.1】人工神经网络(内含模型保存与恢复介绍)

    线性阈值单元 线性阈值单元(LTU):输入和输出是数字(而不是二进制开/关值),并且每个输入连接都与权重相连。LTU计算其输入的加权和(z = W1×1 + W2×2 + … + + WN×n = W...

    2024-04-01 02:56:08
  • JDK17遇到报错 module java.base does not “opens java.util“ to unnamed module 问题解决 热门推荐

    JDK17遇到报错 module java.base does not “opens java.util“ to unnamed module 问题解决 热门推荐

    在Java 9及以上版本运行应用程序时,在各种情况下都会发生此异常。 详细可以参考module java.base does not &quot;opens java.lang&quot; to un...

    2024-04-01 02:56:00
  • NoSQL 中 MongoDB 和 Redis 的入门知识

    今天学习了 NoSQL 中 MongoDB 和 Redis 的一些入门知识,因为并不想深入了解学习(只是想了解学习 SQL 之外的),所以只是简单了解了入门的一些基础知识与命令,在此总结记录下。 文档...

    2024-04-01 02:55:54