【C++】哈希之位图

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

一、位图概念

假如有40亿个无重复且没有排序的无符号整数,给一个无符号整数,如何判断这个整数是否在这40亿个数中?

我们用以前的思路有这些:

  1. 把这40亿个数遍历一遍,直到找到为为止
  2. 排序+二分查找
  3. 位图解决

遍历一遍的时间复杂度为O(N);排序是O(N * logN),二分查找是O(logN),第二种还不如第一种。前面两种方法如果是针对比较小的数据的话,还行。但是如果是数据很大的,效率就低了。所以我们可以使用第三种方法,位图解决查找数据的问题。

位图概念:
位图是通过每一个比特位来判断一个数是否是在还是不在。一个二进制比特位只有两种状态,要么为0,要么为1,如果某个数据在,则对应映射的比特位为1;不在,对应的比特位为0。位图适用于海量数据处理,且数据无重复的场景,时间复杂度为O(1)

【C++】哈希之位图,C++,c++,哈希算法,开发语言

用位图解决前面的问题:

有40亿个无重复且没有排序的无符号整数,给一个无符号整数,如何判断这个整数是否在这40亿个数中?

首先要了解1G大约等于10亿个字节,1个整数等于4个字节,1个字节等于8个比特位。换算下40亿个整数大约是16G。但是我们不可能开出16G的内存去查找一个数,用位图就可以节省很多空间了。一个整数等于32个比特位,根据位图的概念,用每个比特位是1还是0来确定一个数到底在不在,1个整数的32个比特位可以用来确定32个数据的存在,所以16G除以32等于0.5G,即512M,这就是开辟的空间大小,是不是节省多了。

这里是我们自己模拟出来的一个简单的位图,主要有以下接口:

1️⃣构造
使用vector的接口resize开辟出N / 32 + 1的空间大小,每个位置初始化为0,为什么要除32?因为一个整数有32个比特位,这32个比特位存储在vector数组的一个位置里;为什么又要加1?因为假如开的空间大小是50,50/32等于1,那到底是一个位置还是2个位置?很明显是2个,第一个位置刚好满32个比特位,剩余18个比特位也要有位置放,因此要有第二个位置。

2️⃣将该比特位设置为1
每个数都有对应映射的比特位,将这个数除以32找到该数在数组中的位置,取模32找到映射的第几个比特位,1左移前面取模的位数,然后按位或将该比特位设置为1
【C++】哈希之位图,C++,c++,哈希算法,开发语言

3️⃣将该比特位设置为0
前面同上,先按位取反1左移前面取模的位数后的数,然后按位与将该比特位设置为0
【C++】哈希之位图,C++,c++,哈希算法,开发语言

4️⃣判断状态
前面同上,用按位与,映射的位置和1移动后的位都是1才说明这个数在
【C++】哈希之位图,C++,c++,哈希算法,开发语言

类的模板是非类型模板参数,传的是数据的大小。成员变量是vector类型,方便开辟空间。为什么1是左移?注意:左移不是真的往左边移,右移也不是真的往右边移,跟方向没关系。左移是往高位移动,右移是往低位移动;其次,还要看编译器,vs下是小端存储数据的,所以这里是左移。

代码:文章来源地址https://www.toymoban.com/news/detail-845801.html

namespace yss
{
	template<size_t N>
	class bitset
	{
	public:
		//构造
		bitset()
		{
			_bit.resize(N / 32 + 1, 0);
		}
		//该比特位 置为1
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bit[i] |= (1 << j);
		}
		//该比特位 置为0
		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			_bit[i] &= ~(1 << j);
		}
		//该比特位的状态(在/不在)
		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			return _bit[i] & (1 << j);
		}

	private:
		vector<int> _bit;
	};
}

void Func1()
{
	yss::bitset<100> bs;
	bs.set(30);
	bs.set(60);
	bs.set(90);
	for (size_t i = 0; i < 100; i++)
	{
		if (bs.test(i))
		{
			cout << i << "->" << "在" << endl;
		}
		else
		{
			cout << i << "->" << "不在" << endl;
		}
	}
}

40亿个数据,如下:

yss::bitset<-1>* bs = new bitset<-1>;//第一种写法
yss::bitset<4294967295>* bs = new bitset<4294967295>;//第二种写法

栈的空间有限,对于很大的数据,需要大量的内存空间,应该通过堆来申请。其他同上面代码。

二、海量数据面试题

1️⃣给定100亿个整数,设计算法找到只出现一次的整数?

思路:

  • 使用两个位图来实现,表示00(没有出现) - 01(出现一次) - 10 - 11 的情况(后面两个是出现2个及2个以上),本题是找到只出现一次的整数,所以最终判断这个整数在不在的条件是两个位图映射的比特位是不是01
  • 有100亿个整数,为了映射所有整数,一个位图开辟的空间大小是512M,即2的32次方个比特位,两个合起来是占1G内存

代码:

int main()
{
	vector<int> a{ 2,2,3,3,5,8,8,14,14,66 };
	bitset<-1>* bs1 = new bitset<-1>;//指针
	bitset<-1>* bs2 = new bitset<-1>;
	
	for (auto e : a)
	{
		if (bs1->test(e) == false && bs2->test(e) == false)
		{
			bs2->set(e);//00->01
		}
		else if (bs1->test(e) == false && bs2->test(e) == true)
		{
			bs1->set(e);
			bs2->reset(e);//01->10
		}
		else
		{
			//
		}
	}
	for (size_t i = 0; i < -1; i++)
	{
		if (bs1->test(i) == false && bs2->test(i) == true)
		{
			cout << i << endl;// 5   66
		}
	}
	return 0;
}

2️⃣给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

思路:

  • 既然给两个文件,那么也要用两个位图。100亿个整数,跟前面一样,一个位图也是512M,两个位图刚好1G
  • 只需判断某个数据在两个位图是否存在即可,如果两个位图的对应映射的比特位都是1,就是交集;反之,有一个不是1,或者两个都是0就不是交集

代码:

int main()
{
	vector<int> a1{ 2,4,6,8,10,14,20 };
	vector<int> a2{ 1,3,4,5,7,9,10,17 };
	bitset<-1>* bs1 = new bitset<-1>;
	bitset<-1>* bs2 = new bitset<-1>;
	for (auto e : a1)
	{
		bs1->set(e);
	}
	for (auto e : a2)
	{
		bs2->set(e);
	}
	for (size_t i = 0; i < -1; i++)
	{
		if (bs1->test(i) == true && bs2->test(i) == true)
		{
			cout << i << endl;// 4  10
		}
	}
	return 0;
}

3️⃣1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

思路:

  • 步骤同问题1,在它的基础上增加了10->11的情况,即出现3次和3次以上,然后最后判断条件为出现1次和2次的数据打印出来

代码:

int main()
{
	vector<int> a{ 2,4,4,5,5,5,7,9,9,9,9 };
	bitset<-1>* bs1 = new bitset<-1>;
	bitset<-1>* bs2 = new bitset<-1>;
	for (auto e : a)
	{
		if (bs1->test(e) == false && bs2->test(e) == false)
		{
			bs2->set(e);//00->01 出现1次
		}
		else if (bs1->test(e) == false && bs2->test(e) == true)
		{
			bs1->set(e);
			bs2->reset(e);//01->10 出现2次
		}
		else if (bs1->test(e) == true && bs2->test(e) == false)
		{
			bs2->set(e);//10->11 出现3次
		}
		//3次以上
	}
	for (size_t i = 0; i < -1; i++)
	{
		if ( (bs1->test(i) == false && bs2->test(i) == true)
			|| (bs1->test(i) == true && bs2->test(i) == false))
		{
			cout << i << endl;// 2  4  7
		}
	}
	return 0;
}

到了这里,关于【C++】哈希之位图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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日
    浏览(49)
  • 【C++】哈希(位图,布隆过滤器)

    今天的内容是哈希的应用:位图和布隆过滤器 目录 一、位图 1.位图概念 2.位图的应用 二、哈希切分 三、布隆过滤器 1.布隆过滤器的概念 2.布隆过滤器的应用 四、总结   今天的内容从一道面试题开始引入: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何

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

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

    2023年04月09日
    浏览(49)
  • C++哈希应用——位图布隆过滤器

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

    2024年02月04日
    浏览(53)
  • 【C++】哈希位图和布隆过滤器

    哈希位图和布隆过滤器都是常用的概率数据结构,用于高效地判断一个元素是否存在于一个集合当中,但它们在实现方法和各自的优缺点上有所区别。 哈希位图 哈希位图(Hash Bitmap)是由一个位数组构成,每个元素(通常是一个整数)被映射到位数组中的某个位置。对于集合

    2024年02月08日
    浏览(49)
  • 【C++】哈希的应用——bitset(STL)位图

    看这样一道面试题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】 单纯从判断一个数是否在一串数字的角度看,我们很容易想到下面的方法: 把这40亿个整数放到set、unordered_set容器里头,调用find函数来判

    2023年04月20日
    浏览(48)
  • [C++]哈希应用之位图&布隆过滤器

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

    2024年04月15日
    浏览(40)
  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希是一种映射思想,这里再讲解两种应用哈希思想的数据结构。 问题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数

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

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

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

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

    2024年02月05日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包