当前位置: 首页 > news >正文

【C++修炼之路】25.哈希应用--布隆过滤器

在这里插入图片描述
每一个不曾起舞的日子都是对生命的辜负

布隆过滤器

  • 前言
  • 一.布隆过滤器提出
  • 二.布隆过滤器概念
  • 三. 布隆过滤器的操作
    • 3.1 布隆过滤器的插入
    • 3.2 布隆过滤器的查找
    • 3.3 布隆过滤器的删除
  • 四.布隆过滤器的代码
    • 4.1 HashFunc的仿函数参考
    • 4.2 BloomFilter.h
  • 五.布隆过滤器的优缺点
  • 六.布隆过滤器的应用场景

前言

上一节中,我们学到了位图,可以看出位图有如下优点:1.节省空间。2.快。

但相对的,位图同样有缺点存在:1. 一般要求范围相对集中,如果范围特别分散,空间消耗就会上升。2. 只能针对整形

那如果此时是字符串类型,能不能通过位图的思想来确定字符串在不在呢?

一.布隆过滤器提出

我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录。 如何快速查找呢?

  1. 用哈希表存储用户记录,缺点:浪费空间
  2. 用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理了。
  3. 将哈希与位图结合,即布隆过滤器

即通过位图的方式确定字符串在还是不在,我们可以采用HashFunc将字符串转换成整形映射到位图中,这就是布隆过滤器。

二.布隆过滤器概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

但实际上这种布隆过滤器的方式可能会产生误判:

  1. 在是不一定准确的。(hashFunc映射冲突)
  2. 不在一定是准确的。

可能存在是因为映射可能出现重复,即产生冲突,这是布隆过滤器无法避免的,但是可以通过增加HashFunc的映射次数从而降低冲突引起的误判率。

img

如图,映射之后,当查找时,如果三个映射值都不为0,那么可以大概认为这个变量是存在的。(映射越多,越准确)当然映射越多的话,同样会浪费空间,因此需要根据需求设计HashFunc的个数。

如何选择哈希函数个数和布隆过滤器长度

很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

k 为哈希函数个数,m 为布隆过滤器长度,n 为插入的元素个数,p 为误报率

image-20230305114447713

如何选择适合业务的 k 和 m 值呢,这里直接贴一个公式:k=m∗ln2/nk = m*ln2 / nk=mln2/n

可以看出,当k=3时,m≈4.2*n。因此,下面代码中我们采用5*N大小的布隆过滤器长度无疑是非常合适的。

三. 布隆过滤器的操作

上述虽然将大致的思路提到,但还是需要具体描述一下步骤

3.1 布隆过滤器的插入

image-20230305140840132

向布隆过滤器中插入:“baidu”

image-20230305140904760

image-20230305140914755

此过程就需要用到指定的HashFunc了。

3.2 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。
比如:在布隆过滤器中查找"alibaba"时,假设3个哈希函数计算的哈希值为:1、3、7,刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的。

3.3 布隆过滤器的删除

布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。

比如:删除上图中"tencent"元素,如果直接将该元素所对应的二进制比特位置0,“baidu”元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。

缺陷:

  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

四.布隆过滤器的代码

4.1 HashFunc的仿函数参考

各种字符串Hash函数 - clq - 博客园 (cnblogs.com)

我们没必要重复造轮子,因此直接采用上面链接的仿函数即可,有评分高的选高的,有需要就稍微改一下参数类型即可。

4.2 BloomFilter.h

#pragma once
#include<bitset>//设置的仿函数
struct BKDRHash
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;hash += ch;}return hash;}
};struct APHash
{size_t operator()(const string& key){unsigned int hash = 0;int i = 0;for (auto ch : key){if ((i & 1) == 0){hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));}i++;}return hash;}
};struct DJBHash
{size_t operator()(const string& key){unsigned int hash = 5381;for (auto ch : key){hash += (hash >> 5) + ch;}return hash;}
};template<size_t N,size_t X = 5,class K = string,class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash>class BloomFilter
{
public:void set(const K& key){size_t hash1 = HashFunc1()(key) % (X * N);size_t hash2 = HashFunc2()(key) % (X * N);size_t hash3 = HashFunc3()(key) % (X * N);_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K& key){size_t hash1 = HashFunc1()(key) % (X * N);if (!_bs.test(hash1))//如果不在,没必要往后走了{return false;//不存在误判}size_t hash2 = HashFunc2()(key) % (X * N);if (!_bs.test(hash2))//如果不在,没必要往后走了{return false;//不存在误判}size_t hash3 = HashFunc3()(key) % (X * N);if (!_bs.test(hash3))//如果不在,没必要往后走了{return false;//不存在误判}return true;//可能存在误判}
private:std::bitset<N * X> _bs;};

通过大量的数据可以判断冲突率:

void test_bloomfilter2()
{srand(time(0));const size_t N = 100000;BloomFilter<N> bf;std::vector<std::string> v1;std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";for (size_t i = 0; i < N; ++i){v1.push_back(url + std::to_string(i));}for (auto& str : v1){bf.set(str);}// v2跟v1是相似字符串集,但是不一样std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";url += std::to_string(999999 + i);v2.push_back(url);}size_t n2 = 0;for (auto& str : v2){if (bf.test(str)){++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;// 不相似字符串集std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){string url = "zhihu.com";url += std::to_string(i + rand());v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

image-20230305135335177

通过控制X,X越大,空间就越大,越不易产生冲突,误判率越低。当然,增加HashFunc也可以降低误判率。

五.布隆过滤器的优缺点

优点:

  1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关

  2. 哈希函数相互之间没有关系,方便硬件并行运算

  3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势

  4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势

  5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能

  6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

缺点:

  1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再
    建立一个白名单,存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除,可能会存在计数回绕问题

六.布隆过滤器的应用场景

不需要一定准确的场景。注册时候的昵称判重。提高效率

image-20230305143031981

在客户端和数据库之间建立一个布隆过滤器,如果通过布隆的结果发现没有找到,那么一定不在,也就不用继续向数据库中查找了。如果在,那么就需要进数据库中一一查找,因为布隆对于找到的值是不一定存在的。所以通过布隆可以提高数据不在时查找的效率。

相关文章:

【C++修炼之路】25.哈希应用--布隆过滤器

每一个不曾起舞的日子都是对生命的辜负 布隆过滤器前言一.布隆过滤器提出二.布隆过滤器概念三. 布隆过滤器的操作3.1 布隆过滤器的插入3.2 布隆过滤器的查找3.3 布隆过滤器的删除四.布隆过滤器的代码4.1 HashFunc的仿函数参考4.2 BloomFilter.h五.布隆过滤器的优缺点六.布隆过滤…...

linux入门---权限

目录标题什么是权限人的分类为什么会有所属组查看文件属性文件的分类如何查看权限文件不同权限的表现rwx权限修改八进制权限修改umask有关内容文件中人的修改目录不同权限的表现rwx什么是权限 首先来看一个例子&#xff1a;比如说我没有爱奇艺的vip&#xff0c;那么我也就没有…...

Unity记录2.1-动作-多段跳、蹬墙跳、墙体滑落

文章首发及后续更新&#xff1a;https://mwhls.top/4450.html&#xff0c;无图/无目录/格式错误/更多相关请至首发页查看。 新的更新内容请到mwhls.top查看。 欢迎提出任何疑问及批评&#xff0c;非常感谢&#xff01; 汇总&#xff1a;Unity 记录 摘要&#xff1a;实现跳跃、蹬…...

Spring Boot结合IDEA自带Maven插件快速切换profile | Spring Cloud 10

一、前言 IDEA是目前 Java 开发者中使用最多的开发工具&#xff0c;它有着简约的设计风格&#xff0c;强大的集成工具&#xff0c;便利的快捷键。 在项目项目整个开发运维周期中&#xff0c;我们的的项目往往需要根据不同的环境&#xff0c;使用不同的文件配置。 比如以下部…...

ES 7.7.0 数据迁移

本文使用 elasticdump 做数据迁移&#xff0c;支持在线和离线俩种方式&#xff0c;适用于数据量比较小的情况。 1、Node 安装 由于elasticdump 依赖于 node&#xff0c;首先需要安装下node。 1.1、 Linux 安装 $ wget https://nodejs.org/dist/v10.15.0/node-v10.15.0-linu…...

【玩转c++】vector讲解和模拟底层实现

本期主题&#xff1a;vector的讲解和模拟实现博客主页&#xff1a;小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限&#xff0c;出现错误希望大家不吝赐vector的介绍及使用1.1vector的介绍vector其实就是一个数组的模板 &#xff0c;存放的数据可以改变而已…...

基本类型、包装类型、引用类型、String等作为实参传递后值会不会改变?

看了半天帖子&#xff0c;讲得乱七八糟&#xff0c;坑死了 [1] 先说结论 基本类型、包装类型、String类型作为参数传递之后&#xff0c;在方法里面修改他们的值&#xff0c;原值不会改变&#xff01;引用类型不一定&#xff0c;要看是怎么修改它的。 [2] 为什么基本类型、包装类…...

Tomcat服务器配置以及问题解决方案

文章目录01 Tomcat简介02 Tomcat的安装03 Tomcat的使用启动Tomcat服务器 &#xff08;解决一闪而过&#xff09;测试 Tomcat 是否启动Tomcat 服务器的关闭04 Tomcat的配置配置端口控制台配置&#xff08;乱码解决&#xff09;部署工程到Tomcat中01 Tomcat简介 Tomcat是一款开源…...

【Node.js】HTTP协议、HTTP的请求报文和响应报文

HTTP协议、HTTP的请求报文和响应报文HTTP协议HTTP主要特点HTTP的请求报文和响应报文请求报文请求行请求消息头空行请求体响应报文响应状态行响应消息头空行响应体总结HTTP协议 HTTP 全称为超文本传输协议&#xff0c;是用于从WWW服务器传输超文本到本地浏览器的传送协议&#…...

CodeForce 455A. Boredom

题目链接 CodeForce 455A. Boredom 思路 因为跟序列的下标无关&#xff0c;所以先对数组a排个序。那么每次选择只会影响两侧的元素。 记号 令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。 但是这样不足以区分是否当前元素可以被使用&#xff0c;所…...

geoserver之BlobStores使用

概述 geoserver是常用的地图服务器之一&#xff0c;除了基本的能力之外&#xff0c;也提供了很多的插件方便大家使用。在本文&#xff0c;讲述一下如何在geoserver中使用BlobStores和gwc-sqlite-plugin插件实现地图的切片和部署。 BlobStores简介 在geoserver中&#xff0c;…...

跨域问题以及Ajax和Axios的区别

文章目录1. 同源策略2. 同源策略案例3. 什么是跨域4. 跨域解决方法4.1 Ajax的jsonp4.2 CORS方式4.3 Nginx 反向代理5. Axios 和 Ajax 的区别6. Axios 和 Ajax 的区别及优缺点6.1 Ajax&#xff1a;6.1.1 什么是Ajax6.1.2 Ajax的原理6.1.3 核心对象6.1.4 Ajax优缺点6.1.4.1 优点&…...

现代卷积神经网络(AlexNet)

专栏&#xff1a;神经网络复现目录 本章介绍的是现代神经网络的结构和复现&#xff0c;包括深度卷积神经网络&#xff08;AlexNet&#xff09;&#xff0c;VGG&#xff0c;NiN&#xff0c;GoogleNet&#xff0c;残差网络&#xff08;ResNet&#xff09;&#xff0c;稠密连接网络…...

单向非循环链表

1、顺序表遗留问题 1. 中间/头部的插入删除&#xff0c;时间复杂度为O(N) 2. 增容需要申请新空间&#xff0c;使用malloc、realloc等函数拷贝数据&#xff0c;释放旧空间。会有不小的消耗。 3. 当我们以2倍速度增容时&#xff0c;势必会有一定的空间浪费。例如当前容量为100&a…...

Vue2的基本内容(一)

目录 一、插值语法 二、数据绑定 1.单向数据绑定 2.双向数据绑定 三、事件处理 1.绑定监听 2.事件修饰符 四、计算属性computed和监视属性watch 1.计算属性-computed 2.监视属性-watch &#xff08;1&#xff09;通过 watch 监听 msg 数据的变化 &#xff08;2&a…...

蚁群算法优化最优值

%%%%%%%%%%%%%%蚁群算法求函数极值%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有变量 close all; %清图 clc; %清屏 m 20; %蚂蚁个数 G 500; %最大迭代次数 Rho 0.9; %信息素蒸发系数 P0 0.2; %转移概率常数 XMAX 5; %搜索变量 x…...

Docker镜像的内部机制

Docker镜像的内部机制 镜像就是一个打包文件&#xff0c;里面包含了应用程序还有它运行所依赖的环境&#xff0c;例如文件系统、环境变量、配置参数等等。 环境变量、配置参数这些东西还是比较简单的&#xff0c;随便用一个 manifest 清单就可以管理&#xff0c;真正麻烦的是文…...

每日的时间安排规划

14:23 2023年3月4日星期六 开始 现在我要做一套试卷。模拟6级考试。 现在是&#xff1a; 16:22 2023年3月4日星期六。 做完了线上的试卷&#xff01; 发现我真的是不太聪明的样子&#xff01; 明明买的有历年真题&#xff0c;做真题就行了&#xff0c;还要做它们出的模拟的…...

【C++】类和对象——六大默认成员函数

&#x1f3d6;️作者&#xff1a;malloc不出对象 ⛺专栏&#xff1a;C的学习之路 &#x1f466;个人简介&#xff1a;一名双非本科院校大二在读的科班编程菜鸟&#xff0c;努力编程只为赶上各位大佬的步伐&#x1f648;&#x1f648; 目录前言一、类的6个默认成员函数二、构造…...

远程debug被arthas watch了的idea

开发工具idea端(2021.2.1) 远程调试 被 应用了 修改的arthas端 的 鸡idea端(2022.3.2) A. 鸡idea端 鸡idea: “D:\IntelliJ IDEA 2022.3.2\bin\idea64.exe” 中安装有目标插件 比如 RedisNew-2022.07.24.zip 对文件 “D:\IntelliJ IDEA 2022.3.2\bin\idea64.exe.vmoptions” 新…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...