基本思想
当直接使用 int / long 等存储某个元素时，所占用的内存为 4 / 8 字节，而 BitMap 则采用的是一个 bit 位标记某个元素，当对应 bit 位为 1 时表示该元素存在，此时该 bit 位所在的 index 即为该元素的值。
注意：布隆过滤器就是利用了 BitMap 算法思想，但是 BitMap 只能接收 int / long 类型的数据，而布隆过滤器则是通过哈希算法，将输入数据转换为了整数类型
算法
BitMap 一般使用数组表示，一个字节占用 8 个 bit 位，通过数组的组合，即可容纳足够大的数据。
比如说要存储 1, 2, 5, 7, 11 这五个数，其中最大的数是 11，即所需要的位数至少为 11 位，因此我们可以使用 2 个字节来表示
// 示例要存储 1, 2, 5, 7, 11 ,最大值为11,因此至少需要11位,而一个字节对应8位,因此需要2个字节.
#include <iostream>
#include <bitset>
int main()
{
int nums[] = {1, 2, 5, 7, 11};
char bytes[2]; // 共16位
for (auto& num : nums)
{
int index = num / 8;
bytes[index] |= (1 << (num % 8));
}
for (auto& byte : bytes)
{
std::bitset<8> b(byte);
std::cout << "byte = " << b.to_string() << std::endl;
/*
byte = 10100110
byte = 00001000
*/
}
}
通过这种方式，假设要存储 10亿 个 int 数据，那么占用的内存为 1000000000 * 4 / 1024 / 1024 / 1024 = 3.75G，而通过转换为 BitMap，则只需要占用 1000000000 / 8 / 1024 / 1024 / 1024 = 119MB，极大的节省了空间
优点
- 面对海量数据，可以极大的节省空间
- 运行效率高
缺点
- 只能统计不重复数据
- 当数据间隔过大时，如（1， 100， 1000000），那么所需要开辟的 BitMap 空间会很大，反而更加浪费内存空间
应用
排序
【问题】：需要对海量个不重复的数进行排序输出，如何快速排序，而且内存空间有限
【分析】：
-
如果数据量大，但是内存空间有限，且数据存在重复，那么应该采用 分而治之 的思想，将数据分块，然后将数据逐块加载到内存中，使用高效的内排序策略进行排序，再把每块已经排完序的数据写回磁盘。最后使用 归并排序 的思想对所有块进行排序 示例：有 1G 的磁盘文件量，可用内存是 100M。首先将文件分成 10 个 100M 的文件，依次加载到内存中进行排序（使用空间复杂度为 O(1) 的排序方法，如冒泡排序，简单选择排序，堆排序，直接插入排序，希尔排序），排完序之后再写回到磁盘中。此时我们拥有了 10 个已有序的文件，使用 归并排序 法，每次从 10 个 100M 的文件中加载 9M 到内存中，余下的 10M 作为算法运算过程中的缓冲区，当缓冲区满了之后把缓冲区写回到磁盘，再继续排序。这样逐步排序最终就可以实现对所有文件进行排序了。
-
如果数据不含重复值，那么可以先通过一次遍历确认数据的最大值，再利用 BitMap 进行排序（桶排序的思想）。首先根据数据最大值计算出 BitMap 数组的大小，然后逐步把数据加载到内存并映射到 BitMap 数组上，最后再遍历 BItMap 数组，顺序输出位为 1 对应的下标，即可完成排序。
去重
【问题】：有海量数据，数据有重复值，问如何统计只出现一次的数据，且内存空间有限
【分析】：
- 我们可以把每个数映射为 2个bit位，这样初始时每个数对应的bit位为 00，当第一次遍历到该数时，将bit位置为 01，当第二次遍历到时置为 10，后面再遍历到该值时则保持 10 的bit位不变。在把所有的数都计算过之后，统计bit位为 01 的数量，即可算出不重复值的数量。
【问题】：有海量数据，数据有重复值，问如何统计不同数的个数，且内存有限
【分析】：
- 计算出数据的最大值，然后确定 BitMap 数组的大小，将所有数据都映射到 BitMap 数组，最后统计bit位为1的数量，即可计算出不同数的数量