在《unordered_map 和 unordered_set》 中提到过：
哈希是一种思想，通过哈希函数将数据转化为一个或多个整型 —— 映射关系；通过这种映射关系，可以做到以 O(1) 的时间复杂度查找数据。
本文即将介绍的 位图 和 布隆过滤器 就是两个非常典型的哈希思想的应用成果，可以在应对海量数据问题 且 做到极大程度节省空间的同时，快速判断 一个元素 是否在 位图 或 布隆过滤器 中。
一、位图
1.1 位图的概念
在直接给出位图的概念之前，我们先温习几个常识：
- 1 int == 4 byte；
- 1 byte == 8 bit ——> 1 int == 32 bit
也就是说，假设我们有 10 个位于 [0, 32) 的整数，仅需 1 个 int 就可以将这些数据标记（在保证数据范围的情况下，即使数据量更大一些也没问题）。
位图的概念：
各个比特位上的数据默认为 0 —— 不存在，遍历数据的过程中，将数据对应位置的 0 修改为 1 —— 存在；再判断某个整数是否存在时，仅须根据其对应位置上的状态（0 或 1）即可得出。
图中 “53 在 32 右边” 的情形并不绝对，与机器的大小端有关。无论你的设备是大端机还是小端机，“1 << 21” —— 左移 都能保证把 “1” 往数据高位移动。
进一步延伸，面对这样一个场景：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
试图通过 排序 + 二分 的办法解决，显然不靠谱 —— 仅存下 40 亿个整数大约需要 16 GB 内存。
在 面对海量整型数据，判断某个整数存在与否 的场景下，位图具有无可比拟的优势 —— 占用的空间小且能够快速查找。
一个非常重要的问题：位图应该开多大的空间？ 具体要开多大，不是由数据的个数决定，而是由数据的范围决定。
代码：
template<size_t N> // 非类型模板参数 class bitset { public: bitset() { _bs.resize(N/32 + 1); // 开 (N/32 + 1) 个 int 类型空间 } void set(size_t n) // 将 n 对应的位置状态修改为 1 { size_t i = n / 32; size_t j = n % 32; _bs[i] |= (1 << j); } void reset(size_t n) // 将 n 对应的位置状态修改为 0 { size_t i = n / 32; size_t j = n % 32; _bs[i] &= ~(1 << j); } bool test(size_t n) // 判断 n 是否存在 { size_t i = n / 32; size_t j = n % 32; return _bs[i] & (1 << j); } private: vector<int> _bs; };
位图代码逻辑本身很简单，诸位读者要理解各个函数中位运算的经义。
PS： STL 库中 bitset 是在栈区上开空间，我们实现的位图在堆区上开空间。
1.2 切分思想
还是上面那个的场景（40 亿个不重复整数），我们进一步对可使用内存的大小进行限制 —— 只能使用 256 MB 。
这会带来一个结果：我们无法一次性把这么多整数存入位图 —— 40 亿个不重复整数大约 500 MB。
把这 40 亿个整数分成两个区间：[0, 2 ^ 31) 和 [2 ^ 31, 2 ^ 32) 。（2 ^ 31 与 2 ^ 32 均为数学运算，C++ 中 ^ 为 异或）
先对 [0, 2 ^ 31) 范围内的整数进行 set() 和 test() ，处理完后将位图置空，再处理 [2 ^ 31, 2 ^ 32) 部分。
