【C++进阶08】哈希的应用(位图and布隆过滤器)

在这里插入图片描述

一、位图

1.1 位图的概念

面试题

给40亿个不重复的无符号整数，没排过序
给一个无符号整数，如何快速判断一个数是否在
这40亿个数中。【腾讯】

能想到的解决思路：

  1. 遍历，时间复杂度O(N)
  2. 排序(O(NlogN)) + 利用二分查找: logN
  3. 放到哈希表或红黑树

40亿整数就是16GB，无法全部加载到内存
遍历、排序和二分查找就都不太现实
虽然可以在文件中归并，但就慢了很多
文件中不能用下标，自然无法二分查找

虽然可以将数据一段一段放进哈希表和红黑树
但每次将数据插入进红黑树又释放
相当于暴力查找40亿数据
红黑树的特性完全没用上

所以以上3点都是不合适的
最大的原因就是内存不足

位图解决
数据是否在给定的整形数据中
结果是在或者不在，刚好是两种状态
那么可以用比特位表示数据是否存在
1为存在，0为不存在

比如数据{1,2,4,9,1517,23}在位图的样子
在这里插入图片描述
所谓位图，就是用每一位来存放某种状态
适用于海量数据，数据无重复的场景
通常是用来判断某个数据存不存在的

一个比特位就能表示一个整型数据在或不在
一个整型就是32比特位，相当于缩小了32倍
也就是说16G的数据只需要0.5G

1.2 位图的模拟实现

在这里插入图片描述
位图的三个主要接口：

  1. set：将数据映射位置置成1，表示存在
  2. reset：将数据映射位置置成0，表示删除
  3. test：检测数据是否存在于位图
template <size_t N>
class bitset
{
public:
	bitset()
	{
		_bits.resize(N / 8 + 1, 0); // 需求N个比特位,按字节给,所以除8.除会去余,所以加1
	}

	void set(size_t x) // 将x比特位置1
	{
		size_t i = x / 8; // 计算x映射的位在第i个char数组位置
		size_t j = x % 8; // 计算x映射的位在这个char的第j个比特位
		
		_bits[i] |= (1 << j);
	}

	void reset(size_t x) // 将x比特位置0
	{
		size_t i = x / 8;
		size_t j = x % 8;

		_bits[i] &= ~(1 << j);
	}

	bool test(size_t x) // 检测位图中x是否为1
	{
		size_t i = x / 8; 
		size_t j = x % 8; 
		
		return _bits[i] & (1 << j);
	}
private:
	vector<char> _bits;
};

1.3 位图的应用

1、给定100亿个整数，设计算法找到只出现一次的整数？

方法：

  1. 创建两个位图对象bs1、bs2
  2. 遍历数据
    出现0次用00表示
    出现1次用01表示
    出现2次用10表示
    出现3次及以上用11表示

如果数据映射的位置在bs1里为1
在bs2里为0表示此数据出现过2次
如果在bs1和bs2里都为1，表示出现3次及以上
方法实现：

template <size_t N>
class twobitset
{
public:
	void set(size_t x) 
	{
		// 00 -> 01
		if (_bs1.test(x) == false 
		&& _bs2.test(x) == false)
		{
			_bs2.set(x);
		}
		else if (_bs1.test(x) == false 
			&& _bs2.test(x) == true)
		{
			// 01 -> 10
			_bs1.set(x);
			_bs2.reset(x);
		}
		// 10 不变
		
	}

	void print()
	{
		for (size_t i = 0; i < N; i++) 
		{
			if (_bs2.test(i))
				cout << i << " ";
		}
	}
private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

void test_twobitset3()
{
	twobitset<1000> bs;
	int a[] = { 0, 12, 12, 0, 20, 12, 12, 0, 223, 22, 45, 4 };
	for (auto e : a)
	{
		bs.set(e);
	}

	bs.print();
}

2、给两个文件，分别有100亿个整数
我们只有1G内存，如何找到两个文件交集？

方法1：
其中的一个文件读到内存的位图中
再读另一个文件，判断在不在上面的位图
在就是交集

问题：
找出的交集存在重复值

解决方法1：
一个数为交集就在第一个文件set那个数

解决方法2：
读取文件1映射到位图1
读取文件2映射到位图2
判断数据映射的位置在这两个位图中
是否都为1

for (int i = 0; i < N; i++)
{
	if (bs1.test(i) && bs2.test(i))
	{
		// 交集
	}
}

或者按位与这两个位图

3、位图应用变形：1个文件有100亿个int
1G内存，设计算法找到出现次数不超过2次的所有整数

定义两个位图对象
将数据插入到位图
出现0次用00表示
出现1次用01表示
出现2次用10表示
出现3次及以上用11表示

除了两个位图对应位置都为1
其他都打印

二、布隆过滤器

位图的优点：

  1. 速度快、节省空间

缺点：

  1. 只能映射整形，其他如浮点数、string等
    不能存储映射

布隆过滤器便是解决此缺点

2.1 布隆过滤器提出

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

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

2.2 布隆过滤器概念

布隆过滤器是由布隆(Burton Howard Bloom)
在1970年提出的 一种紧凑型的、比较巧妙的概
率型数据结构，特点：高效地插入和查询
可以用来告诉你
“某样东西一定不存在或者可能存在”
它是用多个哈希函数
将一个数据映射到位图结构中
此种方式不仅可以提升查询效率
也可以节省大量的内存空间
在这里插入图片描述
用多个哈希函数将字符映射到不同的位置
以此降低重复率，查找时在所有映射的位置
查看是否均为1

查找一个值在与不在
在：是不准确的，存在误判
不在：是准确的
比如美团，本来不在
查找时每个映射的位置都跟别人冲突
导致认为它在

2.3 布隆过滤器的使用场景

  1. 能容忍误判场景
    比如：改名时，快速判断昵称是否使用过

昵称在数据库，而数据库在磁盘
如果去磁盘查找修改的昵称是否使用过
效率非常慢，我们平时改昵称时
只要输入就能立即反馈昵称是否使用

这时可以把所有用户昵称放入布隆过滤器
即使误判修改昵称已使用，用户也感知不到
(只要误判率不高还是可以接受的)

2.4 布隆过滤器的实现

如何选择哈希函数个数和布隆过滤器长度
k 为哈希函数个数
m 为布隆过滤器长度
n 为插入的元素个数
p 为误报率
在这里插入图片描述
在这里插入图片描述
代码实现：

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash = hash * 30 + ch;
		}
		return hash;
	}
	
};

struct APHash
{
	size_t operator()(const string& s) // 仿函数的作用：把一个类当作对象去访问或把一个对象像函数去使用
	{
		size_t hash = 0; // 加register放到最前面表示建议变量放到寄存器里面
		for (long i = 0; i < s.size(); i++)
		{
			size_t ch = s[i];
			if ((i & 1) == 0) // i 是偶数走if，i 是奇数else.奇数二进制的低位一定是1，按位与1得到的便是奇数
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			else
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

// N是key,插入值的个数
template<size_t N, 
class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t len = N * _X;
		size_t hash1 = Hash1()(key) % len; // 用Hash仿函数转成可以取模的整型值，模N是怕转出来的值超出N
		_bs.set(hash1);

		size_t hash2 = Hash2()(key) % len;
		_bs.set(hash2);

		size_t hash3 = Hash3()(key) % len;
		_bs.set(hash3);
		cout << hash1 << " " << hash2 << " " << hash3 << endl;
	}

	bool test(const K& key) // 判断3个位置，有一个位置为0就是不在
	{
		size_t len = N * _X;
		size_t hash1 = Hash1()(key) % len; 
		if (!_bs.test(hash1))
			return false;
		size_t hash2 = Hash2()(key) % len;
		if (!_bs.test(hash2))
			return false;

		size_t hash3 = Hash3()(key) % len;
		if (!_bs.test(hash3))
			return false;
		return true;
	}
private:
	static const size_t _X = 6; // 比重为6，冲突率5%以内.比重建议5-10(冲突率1%-10%)
	bitset<_X * N> _bs; // 开_X倍的空间,空间开得越大,冲突率越低
};

2.5 布隆过滤器的应用

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

100亿query：假设每个query平均50byte
100亿就是5000亿byte，也就是大约占用500G

  1. 可以把每个文件分成1000份读进内存
    每份是0.5个G

在这里插入图片描述
B文件的每一份在A文件的每一份里去找
但是这样时间复杂度太高了
于是可以用哈希函数来切分文件
哈希切分：i = HashFunc(query) % 1000
每个query，算出i是多少就进入Ai小文件
B也是一样，算出i放进Bi小文件
B0、B1……在对应的A0、A1……
小文件里去找，找到了就是交集

跟之前的哈希桶很像
进入同一个桶的都是冲突的值
在这里A和B相同的值用的同一个哈希函数
便一定会进入同一个编号的文件
在这里插入图片描述
会导致的问题：
因为不是平均切分，可能会出现冲突多
每个Ai、Bi小文件过大

  1. 单个文件大量重复query
  2. 单个文件大量不同query

解决方法：
直接使用unordered_set/set
依次读取文件query，插入set中

  1. 如果读取整个小文件query
    都可以成功插入set，说明是情况1
  2. 如果读取整个小文件query
    插入过程抛异常则是情况2
    换其他哈希函数，再次分割求交集

说明：set插入key如果已经有了返回false
如果内存不足抛bad_alloc异常
剩下的都会成功

2、如何扩展BloomFilter使得它支持删除元素的操作

删除一个元素可能会影响其它元素
用多个位图计数的方式表示每个位置被映射了几次
删除时减减该位置

3、哈希切割
给一个超过100G大小的log file, log中存着IP地址,
设计算法找到出现次数最多的IP地址？
与上题条件相同，如何找到top K的IP？

解决方法：
哈希切分成500个小文件
依次读取数据，i = HashFunc(ip)%500
这个ip就是第i个小文件

依次处理每个小文件
使用unordered_map/map统计ip出现次数

  1. 统计过程抛异常，说明单个文件过大
    冲突太多，需要重新换哈希函数
    再次哈希切分这个小文件
  2. 如果没有抛异常，则正常统计
    统计完一个小文件，记录最大的
    clear map，再统计下一个小文件

总结特点：
相同的ip一定进入相同的小文件
读取单个小文件就可以统计ip出现次数

在这里插入图片描述
本篇博客完，感谢阅读🌹
如有错误之处可评论指出
博主会耐心听取每条意见

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

centos搭建ftp踩坑记录

centos搭建ftp踩坑记录

ftp服务器搭建参考b站视频 第1坑&#xff0c;开放端口后仍然无法连接&#xff1a; 这里不仅需要在防火墙打开20和21端口&#xff0c;还需要打开被动访问所使用的端口&#xff0c;也就是在配置文件vsftpd.conf中指定的被动访问接收端口。 pasv_enableYES pasv_min_port40000 p…
阅读更多...
小红书论文刷新 SOTA：人体动作预测再升级，能精准到指尖

小红书论文刷新 SOTA：人体动作预测再升级，能精准到指尖

想象一下&#xff0c;你在玩一款 VR 游戏&#xff0c;准备伸手拿起一个虚拟杯子喝水。‍​​‌​‌​‎‎ 在传统的交互系统中&#xff0c;这通常需要你按下控制器上的特定按钮。但如果游戏集成了 EAI 框架&#xff0c;这一过程将变得无比自然。当你的手缓缓接近虚拟杯子时&…
阅读更多...
数据库基础知识（一）

数据库基础知识（一）

数据库基础知识&#xff08;一&#xff09; 一、数据库基本概念 1.1 数据 数据&#xff08;Data&#xff09;是指对客观事物进行描述并可以鉴别的符号&#xff0c;这 些符号是可识别的、抽象的。它不仅指狭义上的数字&#xff0c;而是有多 种表现形式&#xff1a;字母、文…
阅读更多...
如何开通GitHub Copilot

如何开通GitHub Copilot

GitHub Copilot 是由GitHub 和OpenAI共同开发的人工智能代码辅助工具&#xff0c;可以自动地生成高质量代码片段、上下文信息等。 通过自然语言处理和机器学习技术&#xff0c;能够通过分析程序员编写的代码、注释和上下文信息&#xff0c;自动生成代码&#xff0c;减轻程序员的…
阅读更多...
在线摸头GIF生成系统源码

在线摸头GIF生成系统源码

在线摸头GIF在线生成器html网页源码&#xff0c;可以点击选择文件按钮&#xff0c;或者直接将图片拖入&#xff0c;即可生成导出
阅读更多...
Python爬虫---Scrapy框架---CrawlSpider

Python爬虫---Scrapy框架---CrawlSpider

CrawlSpider 1. CrawlSpider继承自scrapy.Spider 2. CrawlSpider可以定义规则&#xff0c;再解析html内容的时候&#xff0c;可以根据链接规则提取出指定的链接&#xff0c;然后再向这些链接发送请求&#xff0c;所以&#xff0c;如果有需要跟进链接的需求&#xff0c;意思就是…
阅读更多...
Code - VQ-VAE (Vector Quantised Variational AutoEncoder) 的实现源码

Code - VQ-VAE (Vector Quantised Variational AutoEncoder) 的实现源码

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/135936848 VQ-VAE&#xff0c;即Vector Quantized Variational AutoEncoder&#xff0c;向量量化变分自编码器。VQ-VAE 的创新之处是引入了一个向…
阅读更多...
ArcGIS学习（二）属性表的基本操作

ArcGIS学习（二）属性表的基本操作

ArcGIS学习（二）属性表的基本操作 1.查看属性表 ArcGIS是处理空间数据的平台。对于空间数据，大家可以理解成它是由两个部分构成：1.一个是空间形体，也就是点、线、面三种。线又可以分为直线、曲线，面又分为圆形、正方形、不规则形体等；2.另外一个部分是空间形体所附带的…
阅读更多...
Unix/Linux上的五种IO模型

Unix/Linux上的五种IO模型

a.阻塞 blocking 调用者调用了某个函数&#xff0c;等待这个函数返回&#xff0c;期间什么也不做&#xff0c;不停的去检查这个函数有没有返回&#xff0c;必须等这个函数返回才能进行下一步动作。 注意&#xff1a;阻塞并不是函数的行为&#xff0c;而是跟文件描述符有关。通…
阅读更多...
离谱题 3236：练39.1 书香阁座位

离谱题 3236：练39.1 书香阁座位

3236正常写法 #include<bits/stdc.h> using namespace std; int main() {int sum,a,b;a1;b10;sumb;cout<<a<<" "<<b;cout<<" "<<sum<<endl;do{a;b2;sumx;cout<<a<<" "<<b<<&…
阅读更多...
uniapp本地存储日志

uniapp本地存储日志

uniapp本地存储日志 背景实现代码实现使用查看生成log读取 注意事项尾巴 背景 我们的APP开发完成之后&#xff0c;在我们测试环境或者自测的时候都好好的&#xff0c;但是发布到生产环境客户使用总会出现一些奇奇怪怪的问题。这时候因为没在开发环境&#xff0c;我们无法查看到…
阅读更多...
力扣hot100 买卖股票的最佳时机 贪心 经典题

力扣hot100 买卖股票的最佳时机 贪心 经典题

Problem: 121. 买卖股票的最佳时机 文章目录 思路复杂度Code 思路 假设今天卖出&#xff0c;那怎么样收益最大呢&#xff1f;之前买入价是最低的 复杂度 ⏰ 时间复杂度: &#xff1a; O ( n ) O(n) O(n) &#x1f30e; 空间复杂度: O ( 1 ) O(1) O(1) Code class Solut…
阅读更多...
c++之IO流

c++之IO流

1.C语言的输入与输出 C语言中我们用到的最频繁的输入输出方式就是scanf ()与printf()。 scanf(): 从标准输入设备(键 盘)读取数据&#xff0c;并将值存放在变量中。printf(): 将指定的文字/字符串输出到标准输出设备(屏幕)。 注意宽度输出和精度输出控制。C语言借助了相应的缓…
阅读更多...
tsmc12: m0po max length问题（H384.M0_PO.L.1）

tsmc12: m0po max length问题（H384.M0_PO.L.1）

更多学习内容请关注「拾陆楼」知识星球 拾陆楼知识星球入口 在pt eco之后会有一些m0po max length问题出现，大部分问题都可以通过替换decap来解决，少部分由于局部density过高，需要手动调整。
阅读更多...
2023强网杯复现

2023强网杯复现

强网先锋 SpeedUp 要求2的27次方的阶乘的逐位之和 在A244060 - OEIS 然后我们将4495662081进行sha256加密 就得到了flag flag{bbdee5c548fddfc76617c562952a3a3b03d423985c095521a8661d248fad3797} MISC easyfuzz 通过尝试输入字符串判断该程序对输入字符的验证规则为9…
阅读更多...
【C++】类和对象之构造函数、析构函数、拷贝构造函数(二)

【C++】类和对象之构造函数、析构函数、拷贝构造函数(二)

前言&#xff1a;在上一篇我们对于C中类和对象有了一个初步的了解&#xff0c;今天我们将进一步的学习&#xff0c;今天我们目标是对构造函数、析构函数、拷贝构造函数进行一个初步学习在后面也会进一步的学习&#xff0c;一起加油呐&#xff01; &#x1f496; 博主CSDN主页:卫…
阅读更多...
代码随想录 Leetcode669. 修剪二叉搜索树

代码随想录 Leetcode669. 修剪二叉搜索树

题目&#xff1a; 代码(首刷看解析 2024年1月31日&#xff09;&#xff1a; class Solution { public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (!root) return root;if (root->val < low) {TreeNode* node trimBST(root->right,low,high);return…
阅读更多...
Flutter canvas 画一条波浪线 进度条

Flutter canvas 画一条波浪线 进度条

之前用 Flutter Canvas 画过一个三角三角形&#xff0c;html 的 Canvas 也画过一次类似的&#xff0c; 今天用 Flutter Canvas 试了下 感觉差不多&#xff1a; html 版本 大致效果如下&#xff1a; 思路和 html 实现的类似&#xff1a; 也就是找出点的位置&#xff0c;使用二阶…
阅读更多...
山东第四次文物普查启动，全面开展不可移动文物预防性保护

山东第四次文物普查启动，全面开展不可移动文物预防性保护

一、山东进行全面普查不可移动文物资源 近日&#xff0c;山东省政府下发了《关于做好第四次全国文物普查工作通知》&#xff0c;根据调查充分摸清山东不可移动文物资源状况。这是我国时隔16年再次启动文物普查&#xff0c;也是“十四五”期内最大的文物保护行动&#xff0c;以…
阅读更多...
Memcached缓存服务器

Memcached缓存服务器

目录 简介 NoSQL的优点和缺点 下面扩展一下关系型数据库和非关系型数据库的区别 Memcached 特点 原理 配置与安装 Memcached我们直接使用yum安装就可以了 安装后启动 修改配置文件 测试 开发端安装telnet 进行远程连接memcached&#xff0c;端口探测 以下显示为连接…
阅读更多...
最新文章

Copyright @ 2022~2023