【数据结构进阶】位图
🌟🌟作者主页：ephemerals__
🌟🌟所属专栏：数据结构
目录
前言
一、位图的概念与结构
二、位图的实现
1. 结构定义
2. 构造函数
3. 三大接口实现
set
unset
test
总代码
4. 测试
三、 标准库的位图
四、位图的优缺点
总结
前言
在计算机科学中，高效地存储和操作数据是永恒的追求。面对海量数据，传统的存储方式往往显得笨拙而低效，因此，位图作为一种简洁而强大的数据结构，应运而生。它将数据的存在与否抽象为二进制的0和1，利用比特位的排列组合，巧妙地实现了对数据的压缩存储和快速检索。从图像处理到数据库索引，从网络爬虫到布隆过滤器，位图的身影无处不在。本文将带你走进位图的世界，探索其精妙的设计思想和广泛的应用场景。
注：希望大家在学习了哈希表以及位运算的知识后，再来阅读本文，否则其中内容可能难以理解。
一、位图的概念与结构
首先看一道经典面试题：
给定40亿个不重复的无符号整数，且没排过序。如何快速判断某个数是否在这40亿数当中。
解决思路：
1. 存放在数组中，按顺序查找。但数据量太大，消耗时间太长。
2. 排序 + 二分查找 （O(NlogN)）
3. 使用位图存储数据，达到O(1)查找效率
那么位图是什么呢？
位图的本质是一个直接定址法的哈希表，其中存储了若干个整形值。每一个整形值都有对应数量的比特位，每一位的二进制值都可以表示两种状态，例如“在”或者“不在”。
使用位图时，将输入的数据进行映射，找到在位图当中的对应位置，该位置的值就能表示数据的两种状态。
如果我们将int作为位图的数据元素类型，那么一个元素就有32个比特位，第一个int值就可以表示映射值为0~31的数据的两种状态，第二个int值就表示32~65......这样，每一个int值都可以存储32个数据，极大程度减少了空间消耗。
那么怎么求出数据在位图中的映射值呢？
以位图数据元素为int为例，我们拿到一个数x，进行如下计算：
i = x / 32;
j = x % 32;
这样，i 就表示x在第 i 个int值当中；j 表示它在该值的第 j 位。
二、位图的实现
接下来我们尝试用c++代码实现一个简易的位图。
位图的三大关键接口：
- set -- 将一个数在位图中的对应位设置为1（相当于插入数据）
- unset -- 将一个数在位图中的对应位设置为0（相当于删除数据）
- test -- 判断一个数在位图对应位的值是1还是0，是1返回true，是0返回false。（查找）
1. 结构定义
首先是位图结构定义：
#include <vector>
template<size_t N>
class BitSet
{
public:
//插入
void set(size_t x);
//删除
void unset(size_t x);
//查找
bool test(size_t x);
private:
std::vector<int> _bs;//用vector表示位图
};这里我们使用vector容器来表示位图，其中将int作为元素，每个元素表示32个数据的状态。
2. 构造函数
在构造函数当中，我们需要给位图开辟相应的内存。代码如下：
//构造函数
BitSet()
{
//在模板中传入比特位的个数，这里求出需要开辟的int型元素个数
_bs.resize(N / 32 + 1);
}3. 三大接口实现
set
要将一个数x在位图中对应的位标记为1，且不影响其他位的值，我们的做法是：先求出映射的位置（之前已经提到），然后通过位运算，将1左移 j 位，然后与数组的第 i 个值进行“按位或”运算。
注：无需考虑大小端等底层存储问题，因为左移就是会从低位向高位移动。
代码实现：
//插入
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] |= (1 << j);
}unset
unset将位图的对应位标记为0。实现思路：求出映射位置，将1左移 j 位，然后按位取反，再与数组的第 i 个值进行“按位与”运算。代码实现：
//删除
void unset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] &= ~(1 << j);
}test
test用于判断一个数在位图对应位的值是1还是0。思路：也是先求出映射位置，然后将1左移j位，然后与数组的第i个值进行“按位与”运算，判断运算结果是否非0。非0说明该位一定是1，否则该位是0。代码实现：
//查找
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bs[i] & (1 << j);
}总代码
位图总实现代码如下：
#include <vector>
template<size_t N>
class BitSet
{
public:
//构造函数
BitSet()
{
//在模板中传入比特位的个数，这里求出需要开辟的int型元素个数
_bs.resize(N / 32 + 1);
}
//插入
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] |= (1 << j);
}
//删除
void unset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
_bs[i] &= ~(1 << j);
}
//查找
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bs[i] & (1 << j);
}
private:
std::vector<int> _bs;//用vector表示位图
};4. 测试
接下来我们给一串数据，测试位图的功能：
#include "BitSet.h"
#include <iostream>
using namespace std;
int main()
{
BitSet<100> bs;//创建一个一百位的位图
int a[] = { 6,22,5,81,7,2,15,94,82,0,3,56,1,17,9,66,49 };
//遍历数据，存入位图
for (auto& e : a)
{
bs.set(e);
}
int n = 0;
while (cin >> n)
{
if (bs.test(n)) cout << "存在" << endl;
else cout << "不存在" << endl;
}
return 0;
}运行结果：
三、 标准库的位图
c++标准库中也实现了位图，我们可以直接使用。注意：使用时需要包含头文件<bitset> 。
标准库位图查阅：bitset - C++ Reference
可以看到，相比我们实现的位图，标准库的位图还实现了operator[]、size、to_string等接口，使用起来更加灵活。这里的接口使用大家可以自行了解，这里博主就不过多赘述。
需要注意：对于标准库的位图，它的数据元素是存放在对象内部的，并不像我们一样在堆区开辟空间。所以无法使用它直接创建超大位数的位图（如UINT_MAX位），此时可以考虑直接将位图对象从堆中动态申请：
std::bitset<UINT_MAX>* p = new std::bitset<UINT_MAX>();//在堆区中创建对象四、位图的优缺点
优点：由于位图本质是哈希表，所以其增删查改速度极快，时间复杂度为O(1)，且相比传统哈希表更加节省空间，适用于海量数据处理的场景。
缺点：只能对整形数据做出处理，无法表示浮点数或其他类型数据的状态。
小技巧：如果需要用表示数据的多种状态（如重复出现的个数等），可以考虑将多个位图配合起来使用。
总结
位图，这一简洁而高效的数据结构，以其独特的二进制存储方式，在数据处理领域展现了强大的生命力。尽管存在局限性，它仍是解决特定问题的利器，并为更高级的数据结构，如布隆过滤器奠定了基础。在数据爆炸的时代，位图的思想将继续闪耀，为高效数据处理提供源源不断的灵感。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤