零、前言
本章主要讲解C++中对哈希的应用有关方面的内容，位图，布隆，海量数据处理
一、位图
1、位图概念
- 位图概念：
位图其实就是哈希的变形，同样通过映射来处理数据，只不过位图本身并不存储数据，而是存储标记
通过一个比特位来标记这个数据是否存在，1代表存在，0代表不存在
位图通常情况下用在数据量庞大，且数据不重复的情景下判断某个数据是否存在
相关面试题描述：
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中
注意：
遍历时间复杂度O(N)；排序(O(NlogN))利用二分查找: logN；这两种方式除了效率不够高，还有个问题是内存无法完全同时加载这给40亿个不重复的无符号整数
10亿个整数为40亿字节，而10亿字节为1G，所以40亿个整数需要16G大小空间
位图解决方案：
数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态
那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在
示图：小端平台上
2、位图接口的介绍以及实现
bitset中常用的成员函数如下：
成员函数 功能
set 设置指定位或所有位
reset 清空指定位或所有位
flip 反转指定位或所有位
test 获取指定位的状态
count 获取被设置位的个数
size 获取可以容纳的位的个数
any 如果有任何一个位被设置则返回true
none 如果没有位被设置则返回true
all 如果所有位都被设置则返回true
使用示例：
#include <iostream> #include <bitset> using namespace std; int main() { bitset<8> bs; bs.set(2); //设置第2位 bs.set(4); //设置第4位 cout << bs << endl; //00010100 bs.flip(); //反转所有位 cout << bs << endl; //11101011 cout << bs.count() << endl; //6 cout << bs.test(3) << endl; //1 bs.reset(0); //清空第0位 cout << bs << endl; //11101010 bs.flip(7); //反转第7位 cout << bs << endl; //01101010 bs.reset(); //清空所有位 cout << bs.none() << endl; //1 bs.set(); //设置所有位 cout << bs.all() << endl; //1 return 0; }
注：使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位
位图的简单实现：
对于底层来说一个位代表一个数的映射，那么我们以char类型来开辟对应需要空间，同时用vector进行管理
对于开辟空间，一个char类型有8个位，所以需要个数/8即为需要开辟的大小，但是整数相除为向下取整，所以需要我们多开一个空间出来
实现代码：
template<size_t N> class bitset { public: bitset() { _bits.resize(N / 8 + 1,0);//开辟空间并置为0 //_bits.resize((N >> 3) + 1,0); } bool test(size_t x) { size_t i = x / 8;//处于的该数组的第几个空间 size_t j = x % 8;//处于的该空间的第几个比特位 return _bits[i] & (1 << j); } void set(size_t x) { size_t i = x / 8;//处于的该数组的第几个空间 size_t j = x % 8;//处于的该空间的第几个比特位 _bits[i] |= (1 << j);//该位置置为1 } void reset(size_t x) { size_t i = x / 8;//处于的该数组的第几个空间 size_t j = x % 8;//处于的该空间的第几个比特位 _bits[i] &= (~(1 << j));//该位置置为0 } private: vector<char> _bits; };
3、位图的应用
- 快速查找某个数据是否在一个集合中
- 排序
- 求两个集合的交集、并集等
- 操作系统中磁盘块标记
