C++|哈希应用->布隆过滤器

server/2024/9/23 4:12:13/

目录

一、概念

二、模拟实现

三、布隆过滤器扩展应用


 

上一篇章学习了位图的使用,但它只适用于整数,对于要查询字符串是否在不在,位图并不能解决。所以针对这一问题,布隆过滤器可以派上用场,至于布隆过滤器是什么,其实并没有什么神奇的,就是在位图上套了哈希函数罢了,这两者组合起来就是布隆过滤器,而字符串就可以通过哈希函数转换成整数映射到位图当中去。 

一、概念

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

原理分析: 

我们来进行分析,为什么不存在是一定的,而存在是可能的,以及为什么要这样做。

首先来解释为什么要用多个哈希函数。

我们知道,字符串可以通过哈希函数转换成整数,但是哈希冲突是避免不了的,可能存在多个字符串通过哈希函数都得到了一样的整数,所以,为了尽量的减少哈希冲突,可以使用多个哈希函数,让字符串通过多个哈希函数得到多个映射位置,只要不是多个映射位置都相同,就不会冲突,这样大大提高了效率。至于要用几个哈希函数是适合的。

这里有一份研究:(转载详解布隆过滤器的原理,使用场景和注意事项 - 知乎 (zhihu.com))

其中误报率就是哈希冲突率 

其中k、m、n满足:

 其中k、m、p满足:

我们可以发现,哈希函数用的越多,哈希冲突率就越低,但是哈希函数到3之后,误报率已经很低了,其次,当哈希函数、插入元素固定,所开空间越大,误报率也越低。

用一张图来表示通过哈希函数映射到位图中:

那么综上,即使采用了多个哈希函数,也依然可能会存在哈希冲突,所以在判断东西在不在时,若返回的是存在,这有可能是误判,说明映射的位置依然可能完全相同,而不存在时,说明映射的位置不完全相同,这是正确的结果,为了确保冲突率,我们在模拟实现的时候就采用3个哈希函数。

二、模拟实现

#include "MyBitSet.h"//在上一篇章已实现
struct BKDRHash
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){//BKDRhash *= 31;hash += e;}return hash;}
};struct APHash
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); i++){if ((i & 1) == 0){hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));}}return hash;}
};
struct DJHash
{size_t operator()(const string& key){register size_t hash = 5381;for(auto e : key){hash += (hash << 5) + e;}return hash;}
};
namespace bit
{template<size_t N, class K = string, //默认输入的是字符串class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJHash>class BloomFilter{public:void set(const K& key){//获取三个映射位置int hash1 = HashFunc1()(key) % N;int hash2 = HashFunc2()(key) % N;int hash3 = HashFunc3()(key) % N;_blf.set(hash1);_blf.set(hash2);_blf.set(hash3);}bool test(const K& key){//key不存在是准确的。int hash1 = HashFunc1()(key) % N;if (_blf.test(hash1) == false)return false;int hash2 = HashFunc2()(key) % N;if (_blf.test(hash2) == false)return false;int hash3 = HashFunc3()(key) % N;if (_blf.test(hash3) == false)return false;//key存在可能有误判return true;}private:bitset<N> _blf;};
}void TestBF1()
{bit::BloomFilter<100> bf;bf.set("猪八戒");bf.set("沙悟净");bf.set("孙悟空");bf.set("二郎神");cout << bf.test("猪八戒") << endl;cout << bf.test("沙悟净") << endl;cout << bf.test("孙悟空") << endl;cout << bf.test("二郎神") << endl;cout << bf.test("二郎神1") << endl;cout << bf.test("二郎神2") << endl;cout << bf.test("二郎神 ") << endl;cout << bf.test("太白晶星") << endl;
}void TestBF2()
{srand(time(0));const size_t N = 100000;bit::BloomFilter<N * 10> bf;std::vector<std::string> v1;//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";std::string url = "猪八戒";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 urlstr = url;urlstr += std::to_string(9999999 + i);v2.push_back(urlstr);}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";string url = "孙悟空";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;
}

测试:

#include <string>
#include "MyBloomFilter.h"int main()
{TestBF2();return 0;
}

 输出结果:

三、布隆过滤器扩展应用

1.给两个文件,分别由100亿个字符串,只有1G内存,如何找到两个文件交集?

假设每个字符串占50个字节,那么100亿就是5000字节,约等于500G,内存肯定存不下,此时可以采用哈希切分。如图:

 

2.给一个超过100G大小的log file,log中存着IP地址,设计算法找到出现次数最多的IP地址?

与第一题类似,先进行哈希切分,然后通过map统计每个小文件中IP地址出现的次数进行比较即可。 


http://www.ppmy.cn/server/55828.html

相关文章

简单分享下python多态

目录&#xff1a; 一、多态是啥嘞&#xff08;龙生九子各有不同&#xff0c;这就是多态&#xff09; 二、基础的实例 三、多态的优势与应用场景 四、深入理解 一、多态是啥嘞&#xff08;龙生九子各有不同&#xff0c;这就是多态&#xff09; 多态&#xff08;Polymorphism&…

Linux-DNS

DNS域名解析服务 1.DNS介绍 DNS 是域名系统 (Domain Name System) 的缩写&#xff0c;是因特网的一项核心服务&#xff0c;它作为可以将域名和IP地址相互映射的一个分布式数据库&#xff0c;能够使人更方便的访问互联网&#xff0c;而不用去记住能够被机器直接读取的IP数串。…

Python爬虫零基础实战,简洁实用!

1.爬虫简介 简单来讲&#xff0c;爬虫就是一个探测机器&#xff0c;它的基本操作就是模拟人的行为去各个网站溜达&#xff0c;点点按钮&#xff0c;查查数据&#xff0c;或者把看到的信息背回来。就像一只虫子在一幢楼里不知疲倦地爬来爬去。 你可以简单地想象&#xff1a;每个…

Postman保存API返回的token以全局使用的整个流程

1、 调通获取token的接口&#xff0c;包含传递参数的类型&#xff0c;和输入密码是否需要md5加密&#xff0c;根据接口的要求&#xff0c;传入数据 2、 查看接口响应的报文&#xff0c;可以看到token的有效时间&#xff0c;token的类型&#xff0c;里面的access_token就是想要获…

适用于Mac和Windows的最佳iPhone恢复软件

本文将指导您选择一款出色的iPhone数据恢复软件来检索您的宝贵数据。 市场上有许多所谓的iPhone恢复程序。各种程序很难选择并选择其中之一。一旦您做出了错误的选择&#xff0c;您的数据就会有风险。 最好的iPhone数据恢复软件应包含以下功能。 1.安全可靠。 2.恢复成功率高…

linux 服务器与本地文件传输

相信有的小伙伴在刚开始接触linux时&#xff0c;不知道如何把文件上传到linux中&#xff0c;本文介绍两种方式供大家使用&#xff08;推荐使用第二种&#xff09; 一.scp传输 scp C:\\..... root165.3.3.3 /root/.....使用上述指令&#xff0c;即可实现将制定文件传输到服务…

树型结构数据存储实践

很多业务场景会遇到树形结构的数据&#xff0c;如公司的人员职级树、行政区划树等。 使用类似MySQL的数据库进行存储&#xff0c;需要将树形结构&#xff08;二维&#xff09;存储到行格式&#xff08;一维&#xff09;的db中。 本文介绍了树型结构数据存储的三种方式&#xf…

仙人掌中的SNMP检测不到服务器

登录有问题的服务器1.检测snmp localhost:~ # ps -ef|grep snmp root 55180 1 0 08:37 ? 00:00:08 /usr/sbin/snmpd -r -A -LF n /var/log/net-snmpd.log -p /var/run/snmpd.pid root 58436 53989 0 09:44 pts/0 00:00:00 grep --colorauto snmp2.检测…