143.布隆过滤器原理以及Go使用示例

2024-09-01 16:20
文章标签 go 使用 原理 示例 过滤器 布隆 143

本文主要是介绍143.布隆过滤器原理以及Go使用示例，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 1. 是什么？
  • 2. 干什么？
  • 3. 为什么？
  • 4. 有什么问题？
  • 5. Go使用布隆过滤器
    • 单机版(Golang)
    • 分布式版(Java)

1. 是什么？

  • 它是一个二进制bit数组，初始为 0
    在这里插入图片描述

  • 采用位存储数据结构，节省存储空间

  • 1 存在，0 不存在

  • 可以添加，但是不能删除

  • 存在误判

2. 干什么？

用于快速查找一个集合中是否存在某个元素。尤其是大数据量中快速查找判断是否存在的问题。目的就是“大海捞针”

使用场景：

  • 从10亿个手机号中如何快速判断10万个号码是否存在？
  • 白名单设置，如何正确识别合法用户？
  • 黑名单校验垃圾短信
  • …

3. 为什么？

因为它主要的作用在于快速查找，我们通过元素查找的过程说明具体的原理和可能存在的问题。

假设，现有一个集合【码，道】，我们查找某元素是否存在？

1、存储逻辑

使用多个不同hash散列函数对“码”“道”进行计算，对应下标 标记为 1

在这里插入图片描述

2、查找逻辑

1、查找示例

例如，在这个集合中，我们查找一个元素“易”。

2、查找步骤

使用多个不同hash散列函数对“易”进行计算

查找标记位全为 1代表存在，有一个为 0 代表不存在

如图示，“易”字在最后的位置计算的hash值对应为0，判定不存在集合中。

在这里插入图片描述

4. 有什么问题？

（1）什么是误判？

因为hash计算会产生hash冲突（或者hash碰撞）的问题。这就意味着：不同的字符可能存在相同的hash结果值。如下图，“ 有” 和“道” 经过多个hash计算出相同的值。那么可能判定“有” 也存在于集合中，从而产生误判。

在这里插入图片描述

总结：不存在一定不存在，存在不一定存在。

（2）为什么不能删？

布隆过滤器（Bloom Filter）是一种空间效率极高的概率型数据结构，它允许一定的误报率。但是它不支持删除操作。

主要由于哈希函数可能存在冲突（即不同的元素映射到相同的位置），因此一旦某个位置被设置为1，它就可能表示多个元素。如果尝试删除一个元素，那么就需要将该元素映射到的所有位置都重置为0。但是，这样做可能会影响到其他也映射到这些位置的元素，因为无法确定哪些1是由当前要删除的元素设置的，哪些是由其他元素设置的。

例如，紧跟上边的思路，要是删除“有”，就要将下标【3,7,8】同时置为 0 。显然误删了 “道”。

在这里插入图片描述

（3）有没有办法解决Hash冲突？

关于这个问题。只能说，减小出现hash碰撞的概率。而不能彻底杜绝. 对此，有同学肯定想：

  • 拉长点：增加bit位数
    在这里插入图片描述

  • 更散列：再多用点hash函数

事实上，在实际使用中，我们也会根据预估的业务数据，设置总位数和容错率这两个重要参数。这就是怎么用的问题。

5. Go使用布隆过滤器

Go语言里有必要用布隆过滤器嘛？

在Go语言中是否需要使用布隆过滤器取决于您的具体应用需求。布隆过滤器是一种用于判断一个元素是否属于一个集合的数据结构，它具有高效的查询速度和较小的内存占用，但也有一定的误判率。

因此，使用布隆过滤器通常是基于以下考虑：

  1. 需要快速查询元素的存在性：如果您的应用程序需要快速确定一个元素是否属于一个集合，而不需要精确的存在性验证，布隆过滤器是一个合适的选择。它的查询速度比在数据库或其他数据结构中搜索要快得多。

  2. 内存资源有限：如果您希望在内存资源受限的情况下存储大量的元素或数据，布隆过滤器可以节省内存。它的内存占用通常比存储实际元素的数据结构小得多。

  3. 容忍一定的误判率：布隆过滤器具有一定的误判率，即它可能会将不存在于集合中的元素误报为存在。如果您的应用程序可以容忍一些误报，那么使用布隆过滤器是合理的。

  4. 需要高性能：布隆过滤器的查询速度非常快，因为它通常只需要几个哈希计算和位操作。这使它非常适合需要高性能的应用。

布隆过滤器在一些应用场景下非常有用，例如缓存缺失优化、重复数据过滤、恶意输入检测等。但它并不适用于所有情况，特别是对于需要绝对准确性的情况。

在使用布隆过滤器时，需要仔细考虑误判率和容忍度，并根据应用的需求来选择合适的配置参数。布隆过滤器通常用于辅助数据结构，而不是替代传统数据库或数据存储。

布隆过滤器通常用于以下场景：

  • 缓存缺失优化：当需要查找的数据量很大，而内存有限时，可以使用布隆过滤器来快速判断某个数据是否存在于缓存中，从而减少磁盘或网络访问。

  • 重复数据过滤：在某些情况下，需要避免重复数据的插入。布隆过滤器可以用来快速判断一个数据是否已经存在，避免重复。

  • 防止恶意输入：在网络应用中，可以使用布隆过滤器来检测恶意输入，例如防止恶意爬虫或垃圾邮件。

  • 分布式系统：在分布式系统中，布隆过滤器可以用来判断某个数据是否需要从远程节点获取，从而减少网络开销。

单机版(Golang)

下面是一个简单的示例，演示如何在Go中使用布隆过滤器。您可以使用第三方库来实现布隆过滤器，如 github.com/wangjia184/sortedset/bf。

首先，您需要安装这个库：

go get github.com/wangjia184/sortedset/bf

然后，您可以编写代码来创建和使用布隆过滤器：

package mainimport ("fmt""github.com/wangjia184/sortedset/bf"
)func main() {// 创建一个布隆过滤器，参数分别是预期的元素数量和错误率filter := bf.New(10000, 0.01)// 添加元素到布隆过滤器filter.Add([]byte("example"))// 检查元素是否存在于布隆过滤器中if filter.Has([]byte("example")) {fmt.Println("Element 'example' is in the filter.")} else {fmt.Println("Element 'example' is not in the filter.")}if filter.Has([]byte("nonexistent")) {fmt.Println("Element 'nonexistent' is in the filter.")} else {fmt.Println("Element 'nonexistent' is not in the filter.")}
}

布隆过滤器的大小和误判率是可以配置的，根据具体需求进行调整。但需要注意，随着误判率的降低，过滤器所需的内存空间也会增加。

在使用布隆过滤器时，应该考虑到误判率的问题，确保它在实际应用中的误判不会导致严重问题。布隆过滤器对于快速的存在性检查非常有用，但不适用于需要精确匹配的情况。

上面介绍的是单机版的布隆过滤器，但大部分时候我们需要一个分布式场景下的全局布隆过滤器，Go版本的暂时没有找到，可以先看一个Java版的。字节内部有分布式版的布隆过滤器Golang SDK ，但并未开源使用

分布式版(Java)

Java Redisson中的布隆过滤器就是分布式的。

使用 Redisson 创建布隆过滤器，插入元素，并检查某个元素是否存在。

在 pom.xml 文件中添加 Redisson 依赖：

<dependencies><dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.16.1</version> <!-- 使用最新版本 --></dependency>
</dependencies>

编写代码来创建布隆过滤器，插入元素，并检查元素：

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;public class RedissonBloomFilterExample {public static void main(String[] args) {// 配置 Redisson 客户端Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379"); // 替换为你的 Redis 服务器地址// 创建 Redisson 客户端实例RedissonClient redisson = Redisson.create(config);// 创建布隆过滤器// 注意：这里的名称 "myBloomFilter" 是布隆过滤器的唯一标识，你可以根据需要更改RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myBloomFilter");// 初始化布隆过滤器，设置预期插入的元素数量和误报率bloomFilter.tryInit(10000L, 0.03);// 插入元素bloomFilter.add("example");bloomFilter.add("example1");// 查找元素boolean mightContain = bloomFilter.contains("example");System.out.println("布隆过滤器中可能包含'example'：" + mightContain);// 关闭 Redisson 客户端redisson.shutdown();}
}

注意：

  • 由于布隆过滤器的特性，contains 方法返回 true 并不意味着元素一定存在，而返回 false 则意味着元素一定不存在。

  • 对于 bloomFilter.tryInit(10000L, 0.03)，的参数设置，应根据实际业务给出。

这篇关于143.布隆过滤器原理以及Go使用示例的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1127443。

相关文章

中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
深入探索协同过滤：从原理到推荐模块案例

深入探索协同过滤：从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤（UserCF）2. 基于物品的协同过滤（ItemCF）3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代，推荐系统成为连接用户与内容的桥梁。本文聚焦于
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
hdu4407(容斥原理)

hdu4407(容斥原理)

题意：给一串数字1,2，......n，两个操作:1、修改第k个数字，2、查询区间[l,r]中与n互质的数之和。 解题思路：咱一看，像线段树，但是如果用线段树做，那么每个区间一定要记录所有的素因子，这样会超内存。然后我就做不来了。后来看了题解，原来是用容斥原理来做的。还记得这道题目吗？求区间[1,r]中与p互质的数的个数，如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和
阅读更多...
pdfmake生成pdf的使用

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据，将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma
阅读更多...
零基础学习Redis(10) -- zset类型命令使用

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合，内部除了存储元素外，还会存储一个score，存储在zset中的元素会按照score的大小升序排列，不同元素的score可以重复，score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]
阅读更多...
git使用的说明总结

git使用的说明总结

Git使用说明 下载安装(下载地址) macOS: Git - Downloading macOS Windows: Git - Downloading Windows Linux/Unix: Git (git-scm.com) 创建新仓库 本地创建新仓库：创建新文件夹，进入文件夹目录，执行指令 git init ，用以创建新的git 克隆仓库 执行指令用以创建一个本地仓库的
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2