哈希的应用——位图

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

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

目录

一.位图概念

二.STL库中的位图

三.模拟实现位图

1.构造函数

2.set

3.reset

4.test

四.完整代码

五.位图的引用


哈希的应用——位图,数据结构,数据结构

一.位图概念

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

面试体:

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

分析:首先这道题的40亿个无符号整数,如果直接存储到内存的话需要16G的内存,我们首先想到的是使用set,或者unordered_set,但是这里仅仅是数据就已经存储由将近16G大小了,如果我们存放到容器里面,加上一些存储的消耗(指针),实际消耗的内存更是远超16G,这就导致了一般的计算机的内存和普通数据结构来对这些数据进行处理。

所以我们引用一个新的数据结构,就是位图。简单来说仅仅使用一个比特位来标识数据在不在的状态。

  1. 遍历,时间复杂度O(N)
  2.  排序(O(NlogN)),利用二分查找: logN
  3. 位图解决

数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一
个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0
代表不存在
。比如:

哈希的应用——位图,数据结构,数据结构

位图也是利用了哈希映射的思想,而且采用的是直接定值映射的方法,最大的区别是位图仅仅使用一个比特位来标识数据是否存在,hash是需要对数据进行存储的。

二.STL库中的位图

STL库中也给我们提供了位图结构bitset,头文件<bitset>

哈希的应用——位图,数据结构,数据结构

简单介绍几个核心接口:

  • set():将数据插入位图。
  • reset():将数据从位图中挪去。
  • test():判断数据在不在位图中。
int main()
{
	bitset<10000> bit;
	int arr1[] = { 1,15,3,6,8,9,4,23 };
	int arr[] = { 45,12,32,3,6,35,12,78,94,23,62,54 };
	//将arr数据插入位图
	for (auto e : arr)
	{
		bit.set(e);
	}
	//检查arr1,时候出现在位图中
	for (auto e : arr1)
	{
		cout << e << ":" << bit.test(e) << endl;;
	}

	return 0;
}

哈希的应用——位图,数据结构,数据结构

三.模拟实现位图

C/C++中没有单个比特位类型,最小的也是单个字节的char,所以我们只能使用,char配合vector来存储位图结构。

在定义位图的时候我们可以控制定义的位图存储位数,所以位图的设计我们可以使用一个非类型模板参数来控制。

template<size_t N>
class BitSet
{
public:
	
private:
	vector<char> _map;
};

1.构造函数

假如我们需要开85个比特位,而我们因为最小的开辟单元是char即八比特位,所以如果剩下的不足八比特位,我们仍然按照一个char开辟。

	BitSet()
	{
        //不足一个字节时,就按一个字节开辟,并且全部初始化0
		_map.resize((N / 8) + 1, 0);
	}

2.set

找到需要插入的比特位共需两步:

  1. 找到所在char
  2. 找到所在的比特位
  3. 使用位运算插入

哈希的应用——位图,数据结构,数据结构

	void set(const int num)
	{
		size_t i = num / 8;
		size_t j = num % 8;
		_map[i] |= 1 << j;
	}

3.reset

reset与set在查找位置时,步骤一致仅仅是在最后一步换成使用位运算将最后一位变为0.

哈希的应用——位图,数据结构,数据结构

	void reset(const int num)
	{
		size_t i = num / 8;
		size_t j = num % 8;
		_map[i] &= ~(1 << j);
	}

4.test

先找到需要判断的位置,在使用位运算判断。

哈希的应用——位图,数据结构,数据结构

	bool test(const int num)
	{
		size_t i = num / 8;
		size_t j = num % 8;
		return _map[i] & (1 << j) ;
	}

四.完整代码

template<size_t N>
class BitSet
{
public:
	BitSet()
	{
		_map.resize((N / 8) + 1, 0);
	}

	void set(const int num)
	{
		size_t i = num / 8;
		size_t j = num % 8;
		_map[i] |= 1 << j;
	}

	void reset(const int num)
	{
		size_t i = num / 8;
		size_t j = num % 8;
		_map[i] &= ~(1 << j);
	}

	bool test(const int num)
	{
		size_t i = num / 8;
		size_t j = num % 8;
		return _map[i] & (1 << j) ;
	}

private:
	vector<char> _map;
};

测试:

哈希的应用——位图,数据结构,数据结构

 五.位图的引用

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

 回顾刚才的面试题:

我们将40亿的整数全部存入位图,仅仅才占有512M而已。而且位图一旦插入之后,他的搜索效率非常高。文章来源地址https://www.toymoban.com/news/detail-691206.html

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

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

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

相关文章

  • 哈希思想应用【C++】(位图,布隆过滤器,海量数据处理面试题)

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

    2024年02月04日
    浏览(45)
  • [JDK8下的HashMap类应用及源码分析] 数据结构、哈希碰撞、链表变红黑树

    [Java基础] StringBuffer 和 StringBuilder 类应用及源码分析 [Java基础] 数组应用及源码分析 [Java基础] String,分析内存地址,源码 [JDK8环境下的HashMap类应用及源码分析] 第一篇 空构造函数初始化 [JDK8环境下的HashMap类应用及源码分析] 第二篇 看源码了解HashMap的扩容机制 [JDK8环境下的

    2024年02月10日
    浏览(44)
  • 【数据结构和算法】位图 BitMap

    2024年02月14日
    浏览(42)
  • 数据结构:位图、布隆过滤器以及海量数据面试题

    1.1概念 引入 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 (1)遍历: 时间复杂度O(N) (2)排序加二分:时间复杂度O(N*logN) 其中 方法(2)是行不通 的,因为内存很难装下这么多数据(40亿整数大概为16G)。 方法(1) 可行

    2024年02月05日
    浏览(44)
  • 【C++】哈希应用之位图

    👀 樊梓慕: 个人主页  🎥 个人专栏: 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》 《算法》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 1.位图的概念 2.位图的模拟实现 2.1构造 2.2set 2.3reset 2.4test 3.源码 4.位图应

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

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

    2024年02月10日
    浏览(34)
  • C++ 哈希的应用【位图】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2022 版本 17.6.5 位图( bitset )是一种特殊的数据结构,仅仅依靠 0 、 1 表示当前位置是否有数据存在,常用于对查找速度和存储空间有着高要求的场景中,除此之外,位图还可以配合宏定义,实现同时传

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

    我走后,他们会给你们加班费,会给你们调休,这并不是他们变好了,而是因为我来过。------龙哥 1. 大厂经典的面试题,给你40亿个不重复的无符号整数,让你快速判断一个数是否在这40亿个数中,最直接的思路就是遍历这40亿个整数,逐一进行比对,当然这种方式可以倒是可

    2023年04月09日
    浏览(41)
  • 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++】哈希的应用:位图、哈希切分与布隆过滤器

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

    2023年04月09日
    浏览(49)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包