AI 助理
备案控制台
开发者社区 云原生 文章 正文

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

2023-04-20 239
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 目录一、位图的引入二、位图的应用三、位图的使用（bitset的使用）3.1 介绍 3.2 使用四、bitset（位图模拟实现）

目录

一、位图的引入

二、位图的应用

三、位图的使用（bitset的使用）

3.1 介绍

3.2 使用

四、bitset（位图模拟实现）

一、位图的引入

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

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

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

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

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

位图概念

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

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

image.png

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

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

二、位图的应用

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

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

三、位图的使用（bitset的使用）

3.1 介绍

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

文档介绍链接：

https://legacy.cplusplus.com/reference/bitset/bitset/?kw=bitset

bitset的解释：

image.png

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

bitset的常用接口：

set：设置指定位或所有位

image.png

reset：清空指定位或所有位

image.png

test：获取指定位的状态

image.png

其他有需求再查询文档

使用bitset需要包含头文件：

#include <bitset>

3.2 使用

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

简单测试代码：

#include <iostream>#include <bitset>usingnamespacestd;
intmain()
{
//构造一个8位的位图，所有位都初始化为 00000000bitset<8>bs1;
//构造一个16位的位图，所有位都初始化为 0000000000000000bitset<16>bs2; 
bitset<8>bs;
bs.set(2); //设置第2位为1bs.set(4); //设置第4位为1bs.set(0); //设置第0位为1cout<<bs<<endl; //10010100bs.reset(0); //清空第0位cout<<bs<<endl; //00010100cout<<bs.test(3) <<endl; //获取第三位状态return0;
}

运行结果

image.png

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

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

voidTest()
{
//bitset<-1> bs; //模板参数是无符号整数 size_t，-1代表无符号整数最大的范围，接近43亿bitset<0xffffffff>bs;//也可以使用0xffffffff，也是无符号整数的最大范围bs.set(100);//设置第100位为1bs.set(100000);//设置第100000位为1bs.set(888888);//设置第888888位为1cout<<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）重新生成项目

image.png

运行结果

image.png

四、bitset（位图模拟实现）

实现框架如下：

//使用命名空间，防止与库发生冲突namespacefy{
template<size_tN>classbitset    {
public:
//构造bitset()
        {}
//设置 x 位为1voidset(size_tx)
        {}
//清楚 x 位的1，也就是置0voidreset(size_tx)
        {}
//检测某一位的状态booltest(size_tx)
        {}
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 个整数进行 或运算 即可

image.png

代码如下： 

//设置 x 位为1voidset(size_tx)
{
size_ti=x/8;//在第几个char//size_t i = x >> 3;//也可以这么写size_tj=x%8;//在char的第几位_bits[i] |= (1<<j);//将该位设置为1（不影响其他位）}

reset函数

reset函数用于清空指定位

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

image.png

代码如下：

//清除 x 位的1，也就是置0voidreset(size_tx)
{
size_ti=x/8;//在第几个char//size_t i = x >> 3;//也可以这么写size_tj=x%8;//在char的第几位_bits[i] &= (~(1<<j));//将该位设置为0（不影响其他位）}

test函数

test函数用于获取位的状态

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

代码如下

//检测某一位的状态booltest(size_tx)
{
size_ti=x>>3;
size_tj=x%8;
return_bits[i] & (1<<j);
}

测试代码

voidTest_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;
    }

运行结果

image.png

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

image.png

完整代码

 

#pragma once#include <vector>//使用命名空间，防止与库发生冲突namespacefy{
template<size_tN>classbitset    {
public:
//构造bitset()
        {
//默认开N/8+1个char，全部置0_bits.resize(N/8+1, 0);
//_bits.resize((N >> 3) + 1, 0);//也可以这么写，要注意优先级        }
//设置 x 位为1voidset(size_tx)
        {
size_ti=x/8;//在第几个char//size_t i = x >> 3;//也可以这么写size_tj=x%8;//在char的第几位_bits[i] |= (1<<j);//将该位设置为1（不影响其他位）        }
//清除 x 位的1，也就是置0voidreset(size_tx)
        {
size_ti=x/8;//在第几个char//size_t i = x >> 3;//也可以这么写size_tj=x%8;//在char的第几位_bits[i] &= (~(1<<j));//将该位设置为0（不影响其他位）        }
//检测某一位的状态booltest(size_tx)
        {
size_ti=x>>3;
size_tj=x%8;
return_bits[i] & (1<<j);
        }
private:
vector<char>_bits;//每个类型都是char    };
voidTest_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;
    }
}

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

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

文章标签：
C++
容器
关键词：
C++应用
C++哈希
C++哈希应用
C++哈希应用位图
C++位图
枫叶先生_
目录
相关文章
陌陌谣
|
6月前
|
存储 负载均衡 算法
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中，迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点，确保高效稳定的网络环境。该算法通过计算最短路径，提升数据传输速率与稳定性，实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用，为企业信息化建设提供有力支持。
陌陌谣
175 15
小山那边
|
7月前
|
算法 Serverless 数据处理
从集思录可转债数据探秘：Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据，帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均（SMA），展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA，而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据，助力投资者结合算法与社区讨论，做出更明智的投资决策。掌握这些工具和技术，有助于在复杂多变的金融市场中挖掘更多价值。
小山那边
250 12
RossyYan
|
8月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用（头歌实践教学平台习题）【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括： 1. **类的继承关系基础概念**：介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**：详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**：解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类，添加特定属性并测试这些类的功能。最终通过创建教师和助教实例，验证代码
RossyYan
180 5
小王老师呀
|
11月前
|
存储 并行计算 安全
C++多线程应用
【10月更文挑战第29天】C++ 中的多线程应用广泛，常见场景包括并行计算、网络编程中的并发服务器和图形用户界面（GUI）应用。通过多线程可以显著提升计算速度和响应能力。示例代码展示了如何使用 `pthread` 库创建和管理线程。注意事项包括数据同步与互斥、线程间通信和线程安全的类设计，以确保程序的正确性和稳定性。
小王老师呀
221 5
平凡程序猿~
|
7月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
168 0
hahaha无
|
3月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
91 0
hahaha无
|
3月前
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
169 0
ephemerals__
|
5月前
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
177 12
蓝易云
|
6月前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨，我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性，而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧，对于提升C++编程水平至关重要。
蓝易云
128 16
羑悻的小杀马特
|
7月前
|
编译器 C语言 C++
类和对象的简述（c++篇）
类和对象的简述（c++篇）
羑悻的小杀马特
172 28