【C++】哈希的应用——bitset(STL)位图

这篇具有很好参考价值的文章主要介绍了【C++】哈希的应用——bitset(STL)位图。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哈希的应用——bitset(STL)位图

一、bitset的介绍

【C++】哈希的应用——bitset(STL)位图

1.位图的引入

看这样一道面试题:

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

单纯从判断一个数是否在一串数字的角度看,我们很容易想到下面的方法:

  1. 把这40亿个整数放到set、unordered_set容器里头,调用find函数来判断
  2. 把这40亿个整数进行外排序,再去二分查找

单就此题而言,为了推翻上面两种方法,首先,我们要清楚40亿个整数,占用多少空间:

【C++】哈希的应用——bitset(STL)位图

  • 计算得知,40亿整数占16个G内存,光数据就占了16G,若放到set容器,其底层红黑树的内部也有负载的消耗(存颜色,三叉连……),再算上16G的消耗,消耗太大了,内存不够,承受不住。同理,内存不够,数据压根放不到内存,也就不能进行排序。

为了解决此问题,这就需要我们用到位图来解决。

  • **我们在判断一个数据是否在给定的整形数据中,结果只有在或者不在这两种状态,那么就可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。这里我们采用直接定址法的哈希,用一个比特位标识映射值在不在,这就是位图。**示例:

【C++】哈希的应用——bitset(STL)位图

对于40亿个整数,我们要我们要开整型的最大值(2^32 - 1)个bit位,大概占500MB的内存:

【C++】哈希的应用——bitset(STL)位图

由此可见,使用位图的方法,大大减少了内存的消耗,并且能很好的解决此问题。


2.位图的概念

所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。


3.位图的应用

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

二、bitset的使用

1.bitset的构造方式

1、使用默认构造函数,构造一个16位的位图,默认初始化为0

bitset<16> bs1;

2、元素按照给定整数的二进制位进行初始化:0xff ——> 1111 1111

bitset<16> bs2(0xfa2);//0000111110100010

3、使用01的string进行初始化:std::string(“01101001”) ——> 01101001

bitset<16> bs3(string("01101001"));//0000000001101001

4、使用01的字符串进行初始化:(“01101001”) ——> 01101001

bitset<16> bs4("01101001");//0000000001101001

2.bitset成员函数的使用

bitset常用成员函数如下表格所示:

成员函数 功能
set 设置指定位或所有位
reset 清空指定位或所有位
flip 反转指定位或所有位
test 获取指定位的状态
count 获取被设置位的个数
size 获取可以容纳的位的个数
any 如果有任何一个位被设置则返回true
none 如果没有位被设置则返回true
all 如果所有位都被设置则返回true

示例:

int main()
{
	bitset<16> bs;
	bs.set(4);
	bs.set(6);
	bs.set(2);
	cout << bs.size() << endl;//16
	cout << bs << endl;//0000000001010100
	//获取指定位的状态
	cout << bs.test(0) << endl;//0
	cout << bs.test(2) << endl;//1
	//反转所有位
	bs.flip();
	cout << bs << endl;//1111111110101011
	//反转第1位
	bs.flip(1);
	cout << bs << endl;//1111111110101001
	cout << bs.count() << endl;//12
	//清空第3位
	bs.reset(3);
	cout << bs << endl;//1111111110100001
	//清空所有位
	bs.reset();
	cout << bs.none() << endl;//1
	cout << bs.any() << endl;//0
	//设置所有位
	bs.set();
	cout << bs.all() << endl;//1
	return 0;
}

注意: 使用成员函数set、reset、flip时,若指定了某一位则操作该位,若未指定位则操作所有位。


3.bitset运算符的使用

如表格所示:

运算符 功能说明
>>、<< 输入输出运算符
= 赋值运算符
==、!= 关系运算符
&=、|=、^=、<<=、>>= 复合赋值运算符
~ 单目运算符
&、|、^ 位运算符
[ ] operator[ ]运算符

示例:

int main()
{
	//>>输入、<<输出运算符
	bitset<8> bs;
	cin >> bs;//10100
	cout << bs << endl;//00010100
	//复合赋值运算符
	bitset<8> bs1("101011");
	bitset<8> bs2("100100");
	cout << (bs1 >>= 2) << endl;//00001010
	cout << (bs2 |= bs1) << endl;//00101110
	//位运算符
	bitset<8> bs3("10010");
	bitset<8> bs4("11001");
	cout << (bs3 & bs4) << endl;//00010000
	cout << (bs3 ^ bs4) << endl;//00001011
	//operator[]运算符
	cout << bs3[4] << endl;//1
	cout << bs3[2] << endl;//0
}

三、bitset位图的模拟实现

1.位图的基本框架

  • bitset能实现对数字的位的操作,同时也能通过类似于数组的下标来访问各个位的数值,以执行相应的操作。模拟bitset就是用一个普通的数组来存储数据以达到模拟的目的。
  • 如果我们以一个整型作为比特位的容器,那么如果要求0~N范围的比特位,就需要有N/32+1 个整型来容纳这些比特位,同理如果以char为容器,则需要N/8+1个char来容纳N个比特位。这里我们用vector数组作为底层容纳比特位的容器,且其存储的数据类型为char。
namespace bitset_realize
{
	//N个比特位的位图
	template<size_t N>
	class bitset
	{
	public:
		//构造函数
		bitset();
		//把x映射的位标记成1
		void set(size_t x);
		//把x映射的位标记成0
		void reset(size_t x);
		//判断指定比特位x的状态是否为1
		bool test(size_t x);
		//翻转指定pos
		void flip(size_t x);
		//获取位图中可以容纳位N的个数
		size_t size()
		//统计set中1的位数
		size_t count();
		//判断所有比特位若无置为1,返回true
		bool none();
		//判断位图中是否有位被置为1,若有则返回true
		bool any();
		//全部NUM个bit位被set返回true
		bool all();
	private:
		vector<char> _bits;//位图
	};
}

2.成员函数

2.1.构造函数

  • 一个char类型有8个bit位,所以理想状态下N个比特位的位图就需要用到N / 8个字节,但仅限于N是8的整数倍,如果N位10,那么计算下来就会少2个比特位,因此综合考虑,我们给出N / 8 + 1个字节,这样算下来,所需的N个比特位绝对都能访问到,最多可以整除的情况下浪费了8个比特位(1字节)

而构造函数,我们只需要对这所有的比特位(N / 8 + 1)个字节的大小初始化为0即可。

//构造函数
bitset()
{
	//+1保证足够比特位,最多浪费8个比特位
	_bits.resize(N / 8 + 1, 0);
}

2.2.set reset test

  • 1、set

set的作用是把x映射的位置标记成1,实现规则如下:

  1. 通过x / 8计算x在第i个char类型
  2. 通过x % 8计算x在char第j个比特位
  3. 利用按位或 | 把第i个char中的第j个比特位置为1

【C++】哈希的应用——bitset(STL)位图

//把x映射的位标记成1
void set(size_t x)
{
	//x映射的比特位在第几个char对象
	size_t i = x / 8;
	//x在char第几个比特位
	size_t j = x % 8;
	//利用按位或|把第j位标记成1
	_bits[i] |= (1 << j);
}
  • 2、reset

reset的作用是把把x映射的位标记成0,实现规则如下:

  1. 通过x / 8计算x在第i个char类型
  2. 通过x % 8计算x在char第j个比特位
  3. 将1左移 j 位再整体反转后与第 i 个char类型进行与运算即可。

【C++】哈希的应用——bitset(STL)位图

//把x映射的位标记成0
void reset(size_t x)
{
	//x映射的比特位在第几个char对象
	size_t i = x / 8;
	//x在char第几个比特位
	size_t j = x % 8;
	//将1左移 j 位再整体反转后与第 i 个char进行与运算
	_bits[i] &= (~(1 << j));
}
  • 3、test

test的作用是判断指定比特位x的状态是否为1,实现规则如下:

  1. 通过x / 8计算x在第i个char类型
  2. 通过x % 8计算x在char第j个比特位
  3. 将1左移 j 位后与第 i 个char类型进行与运算得出结果
  4. 若结果非0,则该位被设置,否则该位未被设置

【C++】哈希的应用——bitset(STL)位图

//判断指定比特位x的状态是否为1
bool test(size_t x)
{
	//x映射的比特位在第几个char对象
	size_t i = x / 8;
	//x在char第几个比特位
	size_t j = x % 8;
	//将1左移 j 位后与第 i 个char类型进行与运算得出结果
	return _bits[i] & (1 << j);
}

2.3.flip count size

  • 1、flip

flip的作用是用于翻转指定位,若指定位为0,翻转后为1,若指定位为1,反转后为0,实现规则如下:

  1. 通过x / 8计算x在第i个char类型
  2. 通过x % 8计算x在char第j个比特位
  3. 将1左移 j 位后与第 i 个char进行按位异或运算^即可。

【C++】哈希的应用——bitset(STL)位图

//翻转指定位x
void flip(size_t x)
{
	//x映射的比特位在第几个char对象
	size_t i = x / 8;
	//x在char第几个比特位
	size_t j = x % 8;
	//将1左移 j 位后与第 i 个char进行按位异或运算^即可。
	_bits[i] ^= (1 << j);
}
  • 2、count

count的作用是统计位图中被设计为1的个数,实现规则如下:

  1. n = n & (n-1) => 消去n的二进制数中最右边的1
  2. n不为零继续执行第一步
  3. 执行了几次说明n中有多少个1

【C++】哈希的应用——bitset(STL)位图

//统计set中1的个数
size_t count()
{
	size_t count = 0;
	for (auto e : _bits)
	{
		int n = e;
		while (n)
		{
			n = n & (n - 1);
			count++;
		}
	}
	return count;
}
  • 3、size

size的作用是获取位图中可以容纳位N的个数

//获取位图中可以容纳位N的个数
size_t size()
{
	return N;
}

2.4.none any all

  • 1、none

none的作用是遍历每一个char,如果全为0,则none返回true。

//判断所有比特位若无置为1,返回true
bool none()
{
	//遍历每个char
	for (auto e : _bits)
	{
		if (e != 0)//说明有位被置为1,返回false
			return false;
	}
	return true;//说明全为0,返回true
}
  • 2、any

any的作用判断位图中是否有位被置为1,若有则返回true,这其实和none的作用刚好相反,因此我们直接复用none即可。

//判断位图中是否有位被置为1,若有则返回true
bool any()
{
	return !none();
}
  • 3、all

all的作用是判断位图中是否所有的位都被置为1,注意这里的特殊性,先前开辟空间时我们为了避免出现N/8不能整除的情况,特地在resize时多开了一个char类型(8比特)的空间,这8比特里面只有前N%8个比特位才是有效的(剩下的都是多开的空间),因此all函数需要分情况讨论。

  1. 先检查前n-1个char的二进制是否为全1。
  2. 再检查最后一个char的前N%8个比特位是否为全1。

【C++】哈希的应用——bitset(STL)位图文章来源地址https://www.toymoban.com/news/detail-418972.html

//全部NUM个bit位被set返回true
bool all()
{
	size_t size = _bits.size();
	//先检查前N-1个char
	for (size_t i = 0; i < size - 1; i++)
	{
		if (~_bits[i] != 0)//取反应该为0,否则取反之前不全为1,返回false
			return false;
	}
	//再检查最后一个char的前 N%8 个位
	for (size_t j = 0; j < N % 8; j++)
	{
		if ((_bits[size - 1] & (1 << j)) == 0)//和test的原理一致
			return false;
	}
	return true;
}

到了这里,关于【C++】哈希的应用——bitset(STL)位图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++ 哈希思想应用:位图,布隆过滤器,哈希切分

    1.问题 给你40亿个不重复的无符号整数,没排过序.给一个无符号整数,如何快速判断一个数是否在这40亿个数中? 2.分析 1 Byte = 8 bit 1KB = 1024 Byte 1MB = 1024KB = 1024 1024 大约= 10的6次方Byte 1GB = 1024MB = 1024 10的6次方 大约= 10的9次方Byte = 10亿字节 因此4GB 约等于40亿字节 其实最快的方式就是

    2024年04月17日
    浏览(48)
  • C++哈希应用——位图布隆过滤器

    用哈希表存储用户记录,缺点是需要消耗较大的内存;用位图存储用户记录,缺点是位图一般处理整形,内容是字符串或者自定义类型就很勉强。基于以上,若将哈希和位图结合,称为布隆过滤器,会不会把上面的问题都解决了呢? 概念 布隆过滤器是一种概率型数据结构。

    2024年02月04日
    浏览(53)
  • 【C++】哈希的应用:位图、哈希切分与布隆过滤器

    需要云服务器等云产品来学习Linux的同学可以移步/--腾讯云--/--阿里云--/--华为云--/官网,轻量型云服务器低至112元/年,新用户首次下单享超低折扣。   目录 一、位图 1、位图的概念 2、大厂面试题 2.1位图应用(腾讯) 2.2位图应用 3、位图的优缺点 二、哈希切分 三、布隆过滤

    2023年04月09日
    浏览(48)
  • C++语法中bitset位图介绍及模拟实现

    一、位图的引入 先来看下边一道面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 经过我们之前的学习,我们可能会有以下的思路: 对这些数进行排序,再通过二分算法,查找这个数是否存在 插入到unordered

    2024年02月13日
    浏览(38)
  • [C++]哈希应用之位图&布隆过滤器

               主厨:邪王真眼 主厨的主页:Chef‘s blog   所属专栏:c++大冒险        我们之前学习了哈希表,哈希表通过映射关系,实现了O(1)的复杂度来查找数据,哈希在实践中是一个非常重要的思想,今天要学习的就是哈希思想的两大应用:位图与布隆过滤器 给 40 亿个

    2024年04月15日
    浏览(40)
  • 【C++学习】哈希的应用—位图与布隆过滤器

    文章简介 : 在这篇文章中,你会学习到关于哈希思想的最常见的两个应用,也就是 位图 与 布隆过滤器 , 文章会讲解位图和布隆过滤器的概念,底层实现,对应的适应的场景,以及相关经典 海量数据面试题 及解析。 所谓位图,就是用每一位来存放某种状态,适用于 海量

    2024年04月14日
    浏览(60)
  • 【C++高阶(六)】哈希的应用--位图&布隆过滤器

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 哈希最常用的应用是unordered 系列的容器,但是当面对海量数据 如100亿个数据中找有没有100这 个数时,使用无序容器的话内存放不下 所以哈希

    2024年02月05日
    浏览(45)
  • C++进阶--哈希的应用之位图和布隆过滤器

    哈希是一种映射的思想。 先来看一道题:给40亿个不重复的无符号整数,没排序过。给一个无符号整数,如何 快速判断 一个数 是否在 这40亿个数中。 首先想到的解法可能有这几种: 解法1 :遍历40亿个数,O(N) 解法2 :先排序,快排O( N l o g 2 N Nlog_2N Nl o g 2 ​ N ),再利

    2024年02月22日
    浏览(52)
  • C++哈希hash:位图、布隆过滤器的实现及应用

    所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用 来判断某个数据存不存在的。 当我们想查找某一个数据是否存在或者是否处于某种状态时,相比于直接对存放数据的容器进行遍历查找,与原存放数据的容器所建立映射关系的位图来

    2024年04月11日
    浏览(49)
  • 哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题)

       目录 一,位图 1. 位图概念 2.实现 3. 测试题 位图的优缺点 二,布隆过滤器 1). 布隆过滤器提出 2). 概念 3). 布隆过滤器的查找 4). 布隆过滤器删除(了解) 5). 布隆过滤器优点 6). 布隆过滤器缺陷 三,海量数据面试题 1)哈希切割 我们首先由一道面试题来理解位图 给40亿个不

    2024年02月04日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包