【C++】哈希应用之位图

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

【C++】哈希应用之位图,C++,c++,开发语言

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

1.位图的概念

2.位图的模拟实现

2.1构造

2.2set

2.3reset

2.4test

3.源码

4.位图应用变形 


前言

哈希是一种解决问题的思想,那么有关哈希的一个重要应用便是位图,该种结构适用于海量数据,数据无重复的场景,通常用来判断某个数据存在或者不存在,但只能处理整型数据。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。 

=========================================================================文章来源地址https://www.toymoban.com/news/detail-847955.html

GITEE相关代码:🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================


1.位图的概念

我们以一道面试题引入:

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

---『 腾讯』

根据题意,给定40亿个数,很明显如果是40亿个整型,1GB=10亿byte,40亿个整型=160亿byte=16GB,内存中根本放不下,那么这道题关键就在于只需要判断这个数是否在,所以我们仅需一个『 比特位』就可以表示某个数的状态,如果二进制比特位为1,代表存在,为0代表不存在。

而无符号整数总共有2^32个,因此我们仅需2^32个比特位=512M的内存空间就可以判断一个数是否在。

这种思想就是利用了哈希应用中的位图。


2.位图的模拟实现

很明显,位图的底层就是数组,那么我们就选用vector来当作底层容器。

2.1构造

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

一个整型有32个比特位,因此N个位的位图就需要用到N/32个整型,但是实际我们所需的整型个数是N/32+1,因为所给非类型模板参数N的值可能并不是32的整数倍。

例如,当N为40时,我们需要用到两个整型,即40/32+1=2。

//构造函数
bitset()
{
	_bits.resize(N / 32 + 1, 0);
}

2.2set

set用于设置位,即设置某个数为存在,所处位设置为1。

设置位图中指定的位的方法如下:

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

【C++】哈希应用之位图,C++,c++,开发语言

//设置位
void set(size_t pos)
{
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] |= (1 << j); //将该位设置为1(不影响其他位)
}

2.3reset

reset用于清空位,即设置某个数为不存在,所处位设置为0。

清空位图中指定的位的方法如下:

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

【C++】哈希应用之位图,C++,c++,开发语言

//清空位
void reset(size_t pos)
{
	assert(pos < N);

	//算出pos映射的位在第i个整数的第j个位
	int i = pos / 32;
	int j = pos % 32;
	_bits[i] &= (~(1 << j)); //将该位设置为0(不影响其他位)
}

2.4test

test用于检验位,即判断某个数是否存在,检验所处位设置的值。

获取位图中指定的位的状态的方法如下:

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

【C++】哈希应用之位图,C++,c++,开发语言

//获取位的状态
bool test(size_t x)
{
    assert(x <= N);

    //算出pos映射的位在第i个整数的第j个位
    size_t i = x / 32;
    size_t j = x % 32;

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

3.源码

#pragma once
namespace bit_set
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 32 + 1, 0);
		}

		//设置位
        void set(size_t pos)
        {
	        assert(pos < N);

	        //算出pos映射的位在第i个整数的第j个位
	        int i = pos / 32;
	        int j = pos % 32;
	        _bits[i] |= (1 << j); //将该位设置为1(不影响其他位)
        }

		//清空位
        void reset(size_t pos)
        {
	        assert(pos < N);

	        //算出pos映射的位在第i个整数的第j个位
	        int i = pos / 32;
	        int j = pos % 32;
	        _bits[i] &= (~(1 << j)); //将该位设置为0(不影响其他位)
        }        

		bool test(size_t x)
		{
			assert(x <= N);

			size_t i = x / 32;
			size_t j = x % 32;

			return _bits[i] & (1 << j);
		}
	private:
		vector<int> _bits;
	};
}

4.位图应用变形 

问:1个文件有100亿个int,1G内存,设法找到出现次数不超过2次的所有整数。

这种问题很明显就是利用位图来解决,可是前面的问题我们只需要一个比特位就能标识出一个数字是否存在。

那么这个问题呢?

我们可以设想为3种状态,出现0次、出现1次、出现2次、出现3次及以上。

分别用如下数字标识:

出现0次:00

出现1次:01

出现2次:10

出现3次及以上:11

所以设计结构如下:

namespace two_bit_set
{
	template<size_t N>
	class two_bit_set
	{
	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);
			}
		}

		bool test(size_t x)
		{
			if (_bs1.test(x) == false
				&& _bs2.test(x) == true)
			{
				return true;
			}

			return false;
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};
}

给定两组数据找交集,我们也可以通过双位图这种思想实现。


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

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

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

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

相关文章

  • 【C++】哈希的应用:位图、哈希切分与布隆过滤器

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

    2023年04月09日
    浏览(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)
  • 【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日
    浏览(55)
  • C++哈希hash:位图、布隆过滤器的实现及应用

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

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

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

    2024年02月04日
    浏览(45)
  • 【C++】哈希之位图

    假如有40亿个无重复且没有排序的无符号整数,给一个无符号整数,如何判断这个整数是否在这40亿个数中? 我们用以前的思路有这些: 把这40亿个数遍历一遍,直到找到为为止 排序+二分查找 位图解决 遍历一遍的时间复杂度为O(N);排序是O(N * logN),二分查找是O(logN),第二种

    2024年04月09日
    浏览(30)
  • 哈希的应用——位图

    ✅1主页::我的代码爱吃辣 📃2知识讲解:数据结构——位图 ☂️3开发环境:Visual Studio 2022 💬4前言:所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的,其本质也是一种hash。但是其占用空间很少。 目录

    2024年02月10日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包