【C++】哈希的应用 -- 布隆过滤器

文章目录

  • 一、布隆过滤器提出
  • 二、布隆过滤器概念
  • 三、布隆过滤器哈希函数个数的选择
  • 四、布隆过滤器的实现
    • 1.布隆过滤器的插入
    • 2.布隆过滤器的查找
    • 3.布隆过滤器删除
    • 4.完整代码实现
  • 五、布隆过滤器总结
    • 1.布隆过滤器优点
    • 2.布隆过滤器缺陷
    • 3.布隆过滤器的应用
    • 4.布隆过滤器相关面试题

一、布隆过滤器提出

我们知道位图可以快速的判断某个数据是否在一个集合中,但是位图有如下缺点:

1.位图只适用于数据范围集中的场景,当数据过于分散的时候,就会存在空间的浪费

2.位图只能针对整形,对于非整形的数据无法进行处理

其中位图只能针对整形的缺点我们可以使用仿函数来解决,即针对某一种特定类型定义一个HashFunc函数,将其转换为整形,比如当数据类型为字符串的时候,我们可以使用字符串哈希算法将字符串转换为整形,然后再将这个整形映射到位图中

但是这种方法存在一个很大的缺陷–不同的字符串通过同一个HashFunc函数转换出来的值可能是一样的,也就是说,我们判断一个数在不在的时候就存在误判,在这种情况下:

1.位图中该字符串存在是不准确的,因为该字符串的比特位可能原本是0,但是和其他字符串冲突了,发生了误判,导致该比特位变为了1

2.位图中字符串不在是准确的,因为比特位为0说明该字符串以及可能与该字符串发生冲突的其他字符串都不存在,所以不在是准确的

此外,我们通常会对字符串哈希函数转换出来的值进行取模,以此来节省空间,因为转换出来结果的范围是不确定的,但是取模之后又会增加哈希冲突的概率。

那么我们该如何降低误判率呢?答案是布隆过滤器

二、布隆过滤器概念

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

我们可以看到,布隆过滤器是通过使用多个哈希函数的方式来降低误判率,即让同一个元素映射多个下标位置,在查询时只能这些位置都为1的时候才表示该值存在,而同一个元素通过不同哈希函数映射出来的不同下标同时被误判的概率肯定是比一个下标位置被误判的概率要低很多的。

在这里插入图片描述

需要注意的是,布隆过滤器只能降低误判率,不能彻底消除误判

三、布隆过滤器哈希函数个数的选择

那么是不是映射下标位置的个数越多越好呢,当然不是的,因为一个元素映射的下标位置越多,那么浪费的空间越多,此时我们可以选择哈希表或者红黑树,这样查询的结果还是准确的,对于如何选择哈希函数个数和布隆过滤器长度,这里有一篇大佬写的博客,大家可以参考:详解布隆过滤器的原理,使用场景和注意事项

我们通过这篇博客可以知道,哈希长度,布隆过滤器长度 ,插入元素个数与误判率如下图:

在这里插入图片描述

以及他们之间的关系:

在这里插入图片描述

对于上面的K取值带入可得:

1.当k取3的时候,m大约为4.3n,即一个插入元素要消耗4个左右的比特位

1.当k取5的时候,m大约为7.2n,即一个插入元素要消耗7个左右的比特位

1.当k取8的时候,m大约为11.6n,即一个插入元素要消耗12个左右的比特位

结合关系图和关系表达式可以得出,哈希函数取3-5个比较合适。

四、布隆过滤器的实现

布隆过滤器的实现很简单,位图使用库中的bitset 即可,字符串哈希算法可以从下面这篇博客中介绍的算法里面挑选几个评分比较高的算法:各种字符串Hash函数

1.布隆过滤器的插入

对个数据的插入,我们只需要让每一个位图都调用set即可,就可以实现,比如下面的例子:

在这里插入图片描述

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

在这里插入图片描述

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

在这里插入图片描述

代码实现:

void set(const T& key)
{size_t hashi1 = HashFunc1()(key) % (N * X);size_t hashi2 = HashFunc2()(key) % (N * X);size_t hashi3 = HashFunc3()(key) % (N * X);size_t hashi4 = HashFunc4()(key) % (N * X);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);_bs.set(hashi4);
}

2.布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。

注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。

比如:在布隆过滤器中查找"alibaba"时,假设3个哈希函数计算的哈希值为:1、3、7,刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的。

代码实现如下:

bool test(const T& key)
{size_t hashi1 = HashFunc1()(key) % (N * X);if (!_bs.test(hashi1)){return false;}size_t hashi2 = HashFunc2()(key) % (N * X);if (!_bs.test(hashi2)){return false;}size_t hashi3 = HashFunc3()(key) % (N * X);if (!_bs.test(hashi3)){return false;}size_t hashi4 = HashFunc4()(key) % (N * X);if (!_bs.test(hashi4)){return false;}// 前面判断不在都是准确,不存在误判return true; // 可能存在误判,映射几个位置都冲突,就会误判
}

3.布隆过滤器删除

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

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

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

缺陷:

1.无法确认元素是否真正在布隆过滤器中

2.存在计数回绕

4.完整代码实现

#pragma oncenamespace hdp
{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;}};struct JSHash{size_t operator()(const string& s){size_t hash = 1315423911;for (auto ch : s){hash ^= ((hash << 5) + ch + (hash >> 2));}return hash;}};template<size_t N,size_t X = 6,class T=string,class HashFunc1= BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJBHash,class HashFunc4 = JSHash>class BloomFilter{public:void set(const T& key){size_t hashi1 = HashFunc1()(key) % (N * X);size_t hashi2 = HashFunc2()(key) % (N * X);size_t hashi3 = HashFunc3()(key) % (N * X);size_t hashi4 = HashFunc4()(key) % (N * X);_bs.set(hashi1);_bs.set(hashi2);_bs.set(hashi3);_bs.set(hashi4);}bool test(const T& key){size_t hashi1 = HashFunc1()(key) % (N * X);if (!_bs.test(hashi1)){return false;}size_t hashi2 = HashFunc2()(key) % (N * X);if (!_bs.test(hashi2)){return false;}size_t hashi3 = HashFunc3()(key) % (N * X);if (!_bs.test(hashi3)){return false;}size_t hashi4 = HashFunc4()(key) % (N * X);if (!_bs.test(hashi4)){return false;}// 前面判断不在都是准确,不存在误判return true; // 可能存在误判,映射几个位置都冲突,就会误判}private:std::bitset<N * X> _bs;};void test_bloomfilter1(){// 10:46继续string str[] = { "猪八戒", "孙悟空", "沙悟净", "唐三藏", "白龙马1","1白龙马","白1龙马","白11龙马","1白龙马1" };BloomFilter<10> bf;for (auto& str : str){bf.set(str);}for (auto& s : str){cout << bf.test(s) << endl;}cout << endl;srand(time(0));for (const auto& s : str){cout << bf.test(s + to_string(rand())) << endl;}}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;}
}

我们可以使用上面两个函数对布隆过滤器进行测试,我们最终会发现误判率是可控的,我们可以根据具体的应用场景来测试调整哈希函数的个数以及布隆过滤器的长度,最终实现出最符合当前应用场景的布隆过滤器

五、布隆过滤器总结

1.布隆过滤器优点

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

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

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

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

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

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

2.布隆过滤器缺陷

1.有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)

2.不能获取元素本身

3.一般情况下不能从布隆过滤器中删除元素

4.如果采用计数方式删除,可能会存在计数回绕问题

3.布隆过滤器的应用

布隆过滤器是解决位图只能处理整形和数据范围集中的缺陷而提出的,但是哈希函数和取模会导致哈希冲突从而发生误判,为了降低误判率,我们需要合理的选择哈希函数的个树以及布隆过滤器的长度

布隆过滤器适用于不需要完全准确,允许出现一定误判的场景,例如如下场景:

1.用户注册时的昵称判重:某些网站在注册时不允许出现重复昵称,而已注册的昵称都保存在服务器的数据库中,因为数据库存在磁盘是上,访问速度非常慢,所以如果用户没选择一个昵称都去数据库中查找是否存在的话效率是很低的。此时我们就可以在服务器前面加一个布隆过滤器进行过滤–将已注册的昵称都映射到布隆过滤器中,而不在一定是准确的,此时运行用户可以使用该昵称,可以直接返回,不再需要到数据库中进行查找。如果昵称在布隆过滤器中,则提示用户重新输入,但是这个并不影响用户的使用,我们也可以去数据库中进行查找,返回准确的结果。

2.查询个人的数据:比如我们要在公司的客户的数据中以身份证号为key值查找某一个用户的具体信息。由于直接访问数据的效率非常低,此时,我们即可以在服务器前面加一个布隆过滤器。查找方式和第一点一样,不在就直接返回,如果存在,则再到数据库中进行查找再返回查找的结果

在于其他的领域,比如判断一个网站是否是危险网站,我们在点进该网站时就应该显示出信息,此时我们就可以使用布隆过滤器,快速的进行显示。

在这里插入图片描述

4.布隆过滤器相关面试题

给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

我们需要使用哈希切割的思想–使用相同的哈希函数分别对这两个文件进行切割,切割结果为A0–Ai,B0-Bi;因为哈希函数相同,所以Ai和Bi中的query及发生冲突的query都在同一个小文件中,此时我们只需要分别求出Ai和Bi相同下标小文件中的交集即可。需要注意的是,如果小文件很大,说明某一个或几个query有大量的重复,此时换一个哈希函数再分别对Ai和Bi小文件递归子文件进行哈希切割即可。

对于精确算法来说,我们需要先将Ai号小文件中的元素全部存入set/map中,再依次取Bi号小文件中的数据到set/map中查询即可得到交集,但是最后的结果需要进行去重处理。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/167272.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

华为云HECS云服务器docker环境下安装nacos

华为云HECS云服务器&#xff0c;安装docker环境&#xff0c;查看如下文章。 华为云HECS安装docker-CSDN博客 一、拉取镜像 docker pull nacos/nacos-server二、宿主机创建挂载目录 执行如下命令&#xff1a; mkdir -p /usr/local/nacos/logs mkdir -p /usr/local/nacos/con…

【iOS】UITableView总结(Cell的复用原理、自定义Cell、UITableViewCell协议方法)

UITableView 列表的特点&#xff1a; 数据量大样式较为统一通常需要分组垂直滚动通常可视区只有一个 -> 视图的复用 UITableViewDataSource UITableView作为视图&#xff0c;只负责展示&#xff0c;协助管理&#xff0c;不管理数据 需要开发者为UITableView提供展示所需…

基于springboot实现java学习平台项目【项目源码+论文说明】计算机毕业设计

基于springboot实现java学习平台演示 摘要 在Internet高速发展的今天&#xff0c;我们生活的各个领域都涉及到计算机的应用&#xff0c;其中包括学习平台的网络应用&#xff0c;在外国学习平台已经是很普遍的方式&#xff0c;不过国内的管理平台可能还处于起步阶段。学习平台具…

网络编程-java基础

两台电脑之间的通信形成了网络 最小的网络&#xff1a;局域网 校园网(局域网) 城域网(一个市) 广域网(全球) 为什么我发QQ你能收到&#xff0c;这是因为我发的消息实际上是发给了QQ服务器&#xff0c;并不是直接发给你的&#xff0c; 我是与QQ服务器进行通信的&#xff0c…

正方形(Squares, ACM/ICPC World Finals 1990, UVa201)rust解法

有n行n列&#xff08;2≤n≤9&#xff09;的小黑点&#xff0c;还有m条线段连接其中的一些黑点。统计这些线段连成了多少个正方形&#xff08;每种边长分别统计&#xff09;。 行从上到下编号为1&#xff5e;n&#xff0c;列从左到右编号为1&#xff5e;n。边用H i j和V i j表示…

深度学习零基础教程

代码运行软件安装&#xff1a; anaconda:一个管理环境的软件–>https://blog.csdn.net/scorn_/article/details/106591160&#xff08;可选装&#xff09; pycharm&#xff1a;一个深度学习运行环境–>https://blog.csdn.net/scorn_/article/details/106591160&#xf…

2023/10/30-LED灯驱动开发

k1.c #include <linux/init.h> #include <linux/module.h> #include <linux/fs.h> #include <linux/uaccess.h> #include <linux/io.h> #include "head.h" char kbuf[128] {}; unsigned int major; //定义三个指针指向映射后的虚拟内…

家庭燃气表微信抄表识别系统

1.背景需求 目前家里燃气度数的读数上报&#xff0c;每个月在社区微信群里面将手机拍摄的燃气表读数截图&#xff08;加住址信息水印&#xff09;&#xff0c;发到群里给抄表员。 2.总体设计 设计目标 功能一&#xff1a;手机上随时可以远程采集读数图片&#xff08;自动加住…

单片机郭天祥(02)

1&#xff1a;解决keil5软件的乱码问题&#xff0c;修改编码为UTF-8 2&#xff1a;打开keil5使用debug对编写好的程序进行调试 给程序打上断点 使用仿真芯片 更改设备管理器相关设置 接通电源后点击debug连接到51单片机 使用stc-isp获取延时函数 将延时函数添加进入创建好的…

云计算与云服务

云计算与大数据 1、虚拟化简介1.1、什么是虚拟化1.2、虚拟化的分类 2、云计算与云服务2.1、云计算2.2、云服务2.3、云计算的特点 3、云服务模式&#xff08;IaaS、PaaS、SaaS和DaaS&#xff09;4、云计算分类&#xff08;公有云、私有云和混合云&#xff09; 1、虚拟化简介 当下…

高斯分布与高斯过程

一元高斯分布 我们从最简单最常见的一元高斯分布开始&#xff0c;其概率密度函数为&#xff1a; p ( x ) 1 σ 2 π e x p ( − ( x − μ ) 2 2 σ 2 ) p(x)\frac{1}{\sigma\sqrt{2\pi}}exp(-\frac{(x-\mu)^2}{2\sigma^2}) p(x)σ2π ​1​exp(−2σ2(x−μ)2​) 其中 μ \…

【大数据】Kafka 实战教程(一)

Kafka 实战教程&#xff08;一&#xff09; 1.Kafka 介绍1.1. 主要功能1.2. 使用场景1.3 详细介绍1.3.1 消息传输流程1.3.2 Kafka 服务器消息存储策略1.3.3 与生产者的交互1.3.4 与消费者的交互 2.Kafka 生产者3.Kafka 消费者3.1 Kafka 消费模式3.1.1 At-most-once&#xff08;…

FPGA设计FIR滤波器低通滤波器,代码及视频

名称&#xff1a;FIR滤波器低通滤波器 软件&#xff1a;Quartus 语言&#xff1a;Verilog/VHDL 本资源含有verilog及VHDL两种语言设计的工程&#xff0c;每个工程均可实现以下FIR滤波器的功能。 代码功能&#xff1a; 设计一个8阶FIR滤波器&#xff08;低通滤波器&#xff…

【试题040】多个逻辑或例题2

1.题目&#xff1a;设int n0;&#xff0c;执行表达式n ||(n-1) ||(n0)||(n1)||(n2)后n的值是 &#xff1f; 2.代码解析&#xff1a; 逻辑或 || 运算符是一个短路运算符&#xff0c;它从左到右依次计算表达式&#xff0c;如果遇到一个为真&#xff08;非零&#xff09;的值&am…

SequenceFile、元数据操作与MapReduce单词计数

文章目录 SequenceFile、元数据操作与MapReduce单词计数一、实验目标二、实验要求三、实验内容四、实验步骤附&#xff1a;系列文章 SequenceFile、元数据操作与MapReduce单词计数 一、实验目标 熟练掌握hadoop操作指令及HDFS命令行接口掌握HDFS SequenceFile读写操作掌握Map…

2021年03月 Python(三级)真题解析#中国电子学会#全国青少年软件编程等级考试

Python编程&#xff08;1~6级&#xff09;全部真题・点这里 一、单选题&#xff08;共25题&#xff0c;每题2分&#xff0c;共50分&#xff09; 第1题 下列代码的输出结果是&#xff1f;&#xff08; &#xff09; x 0x10print(x)A&#xff1a;2 B&#xff1a;8 C&#xff…

数据结构:二叉树(2)

二叉树的基本操作 获取树的结点总数 遍历思路&#xff1a; 每次遍历一个节点&#xff0c;遍历完nodeSize&#xff0c;然后遍历它的左右子树 如果遍历到空的节点&#xff0c;就返回0 public int nodeSize 0;int size(TreeNode root){if(root null){return 0;}nodeSize;siz…

LeetCode讲解篇之77. 组合

文章目录 题目描述题解思路题解代码 题目描述 题解思路 遍历nums&#xff0c;让当前数字添加到结果前缀中&#xff0c;递归调用&#xff0c;直到前缀的长度为k&#xff0c;然后将前缀添加到结果集 题解代码 func combine(n int, k int) [][]int {var nums make([]int, n)fo…

【MATLAB源码-第51期】基于matlab的粒子群算法(PSO)的栅格地图路径规划。

操作环境&#xff1a; MATLAB 2022a 1、算法描述 粒子群算法&#xff08;Particle Swarm Optimization&#xff0c;简称PSO&#xff09;是一种模拟鸟群觅食行为的启发式优化方法。以下是其详细描述&#xff1a; 基本思想&#xff1a; 鸟群在寻找食物时&#xff0c;每只鸟都会…

arrow(c++)改写empyrical系列1---用arrow读取基金净值数据并计算夏普率

用arrow c版本读取了csv中的基金净值数据&#xff0c;然后计算了夏普率&#xff0c;比较尴尬的是&#xff0c;arrow c版本计算耗费的时间却比python的empyrical版本耗费时间多。。。 arrow新手上路&#xff0c;第一次自己去实现功能&#xff0c;实现的大概率并不是最高效的方…