【数据结构进阶】位图

🌟🌟作者主页：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)，且相比传统哈希表更加节省空间，适用于海量数据处理的场景。

缺点：只能对整形数据做出处理，无法表示浮点数或其他类型数据的状态。

小技巧：如果需要用表示数据的多种状态（如重复出现的个数等），可以考虑将多个位图配合起来使用。

总结

         位图，这一简洁而高效的数据结构，以其独特的二进制存储方式，在数据处理领域展现了强大的生命力。尽管存在局限性，它仍是解决特定问题的利器，并为更高级的数据结构，如布隆过滤器奠定了基础。在数据爆炸的时代，位图的思想将继续闪耀，为高效数据处理提供源源不断的灵感。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤