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

【C++进阶】十一、哈希的应用---位图(一)

目录

一、位图的引入

二、位图的应用

三、位图的使用(bitset的使用)

3.1 介绍

 3.2 使用

四、bitset(位图模拟实现)


一、位图的引入

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

要判断一个数是否在某一堆数中,我们可能会想到如下方法:

  • j进行遍历,时间复杂度O(N)
  • 将这一堆数进行排序,然后通过二分查找的方法判断该数是否在这一堆数中,排序(O(NlogN)),利用二分查找: logN
  • 将这一堆数插入到unordered_set容器中,查找时间复杂度O(1)

从方法上来看,这些方法都是可以的,问题是这里有40亿个无符号整数,若是我们要将这些数全部加载到内存当中,那么将会占用最小16G的空间,空间消耗极大,普通计算机内存也没有这么大,所以实际上是不可行的

 这里解决方法是:位图解决

位图概念

所谓位图,就是用每一位比特位来存放某种状态,适用于海量数据,数据无重复的场景通常是用来判断某个数据存不存在的 ,位图实际上也是使用哈希思想,只不过是哈希的变形

在上面的问题中,我们只需要判断一个数在或是不在,即只有两种状态,那么我们可以用一个比特位来表示数据是否存在,如果比特位为1则表示存在,比特位为0则表示不存在,比如:

1字节 = 8bit,代表的整数就是0~7,比特位为1则表示该数存在

无符号整数总共有 2^32 个,接近43亿,因此记录这些数字就需要 2^32 个比特位,也就是512M的内存空间,内存消耗大大减少,也就是说上面的问题可以用位图快速解决

二、位图的应用

位图可以应用于以下场景:

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

三、位图的使用(bitset的使用)

3.1 介绍

在STL中,C++提供了 bitset,也就是位图

文档介绍链接:bitset - C++ Reference (cplusplus.com)icon-default.png?t=N176https://legacy.cplusplus.com/reference/bitset/bitset/?kw=bitset

bitset的解释: 

bitset的模板参数是一个非类型模板参数,是一个无符号整数

bitset的常用接口:

set:设置指定位或所有位

reset:清空指定位或所有位

test:获取指定位的状态

其他有需求再查询文档

使用bitset需要包含头文件:

#include <bitset>

 3.2 使用

bitset容器对>>、<<运算符进行了重载,可以直接使用>>、<<运算符对biset容器定义出来的对象进行输入输出操作

简单测试代码:

#include <iostream>
#include <bitset>
using namespace std;

int main()
{
	//构造一个8位的位图,所有位都初始化为 00000000
	bitset<8> bs1;
	//构造一个16位的位图,所有位都初始化为 0000000000000000
	bitset<16> bs2; 

	bitset<8> bs;
	bs.set(2); //设置第2位为1
	bs.set(4); //设置第4位为1
	bs.set(0); //设置第0位为1
	cout << bs << endl; //10010100

	bs.reset(0); //清空第0位
	cout << bs << endl; //00010100

	cout << bs.test(3) << endl; //获取第三位状态
	return 0;
}

运行结果

  

下面进行对上面例子进行测试:

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

void Test()
{
	//bitset<-1> bs; //模板参数是无符号整数 size_t,-1代表无符号整数最大的范围,接近43亿
	bitset<0xffffffff> bs;//也可以使用0xffffffff,也是无符号整数的最大范围

	bs.set(100);//设置第100位为1
	bs.set(100000);//设置第100000位为1
	bs.set(888888);//设置第888888位为1

	cout << bs.test(100) << endl; //获取第100位状态
	cout << bs.test(100000) << endl; //获取第100000位状态
	cout << bs.test(888888) << endl; //获取第888888位状态
	cout << endl;

	bs.reset(100000);//清空第100000位
	cout << bs.test(100) << endl; //获取第100位状态
	cout << bs.test(100000) << endl; //获取第100000位状态
	cout << bs.test(888888) << endl; //获取第888888位状态
}

注意:VS可能需要需要改一下堆栈最大的空间大小,否则会栈溢出,运行不了

VS设置如下:

1)选择 "项目->属性".

(2)选择 "链接器".

(3)选择 "系统".

4)在 "堆栈保留大小"中输栈的大小,例如: 1GB为1073741824字节(1024 * 1024 * 1024)

5)重新生成项目

运行结果

四、bitset(位图模拟实现)

实现框架如下:

//使用命名空间,防止与库发生冲突
namespace fy
{
	template<size_t N>
	class bitset
	{
	public:
		//构造
		bitset()
		{}

		//设置 x 位为1
		void set(size_t x)
		{}

		//清楚 x 位的1,也就是置0
		void reset(size_t x)
		{}

		//检测某一位的状态
		bool test(size_t x)
		{}
	private:
		vector<char> _bits;//每个类型都是char
	};
}

构造函数 

在构造位图时,我们需要根据所给位数N,创建一个N位的位图,并且将该位图中的所有位都初始化为0

一个char有8个比特位,因此N个位的位图就需要用到N/8个char,但是实际我们所需的char个数是N/32+1,比如,有18个整数,映射需要18个bit,一个char 是8bit,18/8=2,还剩下2个整数,所以char 的个数需要+1

代码如下:

//构造
bitset()
{
	//默认开N/8+1个char,全部置0
	_bits.resize(N / 8 + 1, 0);
	//_bits.resize((N >> 3) + 1, 0);
}

set函数

set函数用于设置指定位 

  1. 计算出该位位于第 i 个char的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行 或运算 即可

 

代码如下: 

//设置 x 位为1
void set(size_t x)
{
	size_t i = x / 8;//在第几个char
	//size_t i = x >> 3;//也可以这么写
	size_t j = x % 8;//在char的第几位

	_bits[i] |= (1 << j);//将该位设置为1(不影响其他位)
}

 reset函数

reset函数用于清空指定位 

  1. 计算出该位位于第 i 个char的第 j 个比特位。
  2. 将1左移 j 位再整体取反后与第 i 个char进行与运算即可

代码如下:

//清除 x 位的1,也就是置0
void reset(size_t x)
{
	size_t i = x / 8;//在第几个char
	//size_t i = x >> 3;//也可以这么写
	size_t j = x % 8;//在char的第几位

	_bits[i] &= (~(1 << j));//将该位设置为0(不影响其他位)
}

test函数

test函数用于获取位的状态 

  1. 计算出该位位于第 i 个char的第 j 个比特位
  2. 将1左移 j 位后与第 i 个char进行与运算得出结果
  3. 若结果非0,则该位被设置,否则该位未被设置

代码如下

//检测某一位的状态
bool test(size_t x)
{
	size_t i = x >> 3;
	size_t j = x % 8;

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

 测试代码

void Test_bitset()
	{
		bitset<0xffffffff> bs;

		bs.set(10);
		bs.set(10000);
		bs.set(8888);

		cout << bs.test(10) << endl;
		cout << bs.test(10000) << endl;
		cout << bs.test(8888) << endl;
		cout << bs.test(8887) << endl;
		cout << bs.test(9999) << endl << endl;

		bs.reset(8888);
		bs.set(8887);

		cout << bs.test(10) << endl;
		cout << bs.test(10000) << endl;
		cout << bs.test(8888) << endl;
		cout << bs.test(8887) << endl;
		cout << bs.test(9999) << endl;
	}

运行结果

查看一下内存资源,调试下查看,使用了512MB的内存

完整代码

 

#pragma once
#include <vector>
//使用命名空间,防止与库发生冲突
namespace fy
{
	template<size_t N>
	class bitset
	{
	public:
		//构造
		bitset()
		{
			//默认开N/8+1个char,全部置0
			_bits.resize(N/8+1, 0);
			//_bits.resize((N >> 3) + 1, 0);//也可以这么写,要注意优先级
		}

		//设置 x 位为1
		void set(size_t x)
		{
			size_t i = x / 8;//在第几个char
			//size_t i = x >> 3;//也可以这么写
			size_t j = x % 8;//在char的第几位

			_bits[i] |= (1 << j);//将该位设置为1(不影响其他位)
		}

		//清除 x 位的1,也就是置0
		void reset(size_t x)
		{
			size_t i = x / 8;//在第几个char
			//size_t i = x >> 3;//也可以这么写
			size_t j = x % 8;//在char的第几位

			_bits[i] &= (~(1 << j));//将该位设置为0(不影响其他位)
		}

		//检测某一位的状态
		bool test(size_t x)
		{
			size_t i = x >> 3;
			size_t j = x % 8;

			return _bits[i] & (1 << j);
		}
	private:
		vector<char> _bits;//每个类型都是char
	};

	void Test_bitset()
	{
		bitset<0xffffffff> bs;

		bs.set(10);
		bs.set(10000);
		bs.set(8888);

		cout << bs.test(10) << endl;
		cout << bs.test(10000) << endl;
		cout << bs.test(8888) << endl;
		cout << bs.test(8887) << endl;
		cout << bs.test(9999) << endl << endl;

		bs.reset(8888);
		bs.set(8887);

		cout << bs.test(10) << endl;
		cout << bs.test(10000) << endl;
		cout << bs.test(8888) << endl;
		cout << bs.test(8887) << endl;
		cout << bs.test(9999) << endl;
	}
}

----------------我是分割线---------------

文章到这里就结束了,下一篇即将更新


http://www.kler.cn/a/2347.html

相关文章:

  • tslib(触摸屏输入设备的轻量级库)的学习、编译及测试记录
  • 计算机组成原理的学习笔记(5)--数据的表示与运算·其四 浮点数的储存和加减/内存对齐/大端小端
  • Connecting to Oracle 11g Database in Python
  • [ESP]从零开始的Arduino IDE安装与ESP环境配置教程
  • 猫咪睡眠:萌态背后的奥秘与启示
  • 物联网:全面概述、架构、应用、仿真工具、挑战和未来方向
  • 机器学习算法——决策树详解
  • 蓝桥杯刷题第十五天
  • STM32的CAN总线调试经验分享
  • 【安全与风险】密码学介绍
  • Qt调用Chrome浏览器
  • Qt示例3:用Qt画一个温度计
  • 【thingsboard】实现设备联动
  • 数据结构与算法——二叉树遍历、查找、删除、顺序存储二叉树、线索化二叉树
  • 【数据结构】环形链表
  • 大数据模型、离线架构、实时架构
  • Qt实践项目:仿Everything软件实现一个QtEverything
  • 提高曝光率:外贸网站如何充分利用谷歌优化赢得客户
  • C++成神之路 | 第一课【步入C++的世界】
  • 23种设计模式
  • Linux第一个小程序git三板斧
  • 【28】Verilog进阶 - RAM的实现
  • JAVA开发(自研项目的开发与推广)
  • BeanPostProcessor原理分析
  • Flutter内阴影
  • 人脸识别经典网络-MTCNN(含Python源码实现)