哈希的应用——位图
目录
一，引入
二，问题引入
三，std里的位图
四，位图的实现
1.成员
2.初始化
3.set成员函数（如果一个数出现便将对应的比特位改为1）
4.reset函数（如果一个数出现便将对应的比特位改为0）
5.test函数（检验数字存不存在）
5.检验
详细代码：
一，引入
首先介绍一下位图，位图是啥呢？所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用 来判断某个数据存不存在的。首先在这里解释一下：
1.位图的位是比特位。
2.位图面对的海量数据是整形的海量数据。
所以这里便暴露了位图的一个局限性，位图只能用来查找整形数据。
二，问题引入
第一道题是一道面试题，题目如下：
1. 面试题
给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。【腾讯】这道题便是要使用位图来解决的一道经典题目。首先40亿个数字绝对算得上是海量数据，其次我们要查找的是整数。使用位图的两个条件都有了，所以这道题可以使用位图。那我们为什么不使用其它的数据结构来解决这道题呢？比如红黑树，哈希表，AVL树这些高效率的数据结构？其实主要在一个点： 海量数据光是存储都能把内存折腾光了。所以使用这些数据结构是万万不能的。所以我们只能用位图了。
三，std里的位图
传送门：std里的bitset
在手撕位图之前，先来把std库里的位图的样子看一遍，如下图：
首先我们可以知道位图叫：bitset，其次位图是一个非类型参数的模板类（参数的类型已确定是一个size_t类型）。
其次我们再来看看这个N是啥意思：
通过这个解释我们知道了，N是number of bits。所以N就代表比特位的数量。好了现在我们把位图的大概样子摸清楚了，现在就来实现一下吧。
四，位图的实现
1.成员
在实现这个位图时，为了简单一点。我的成员就直接采用vector<int>了。定义如下：
template<size_t N>//非类型模板参数 class bitset { private: vector<char>bits; };
2.初始化
一个类要初始化，我们使用的肯定是构造函数。但是要开多少个比特位，表示的数的范围是多少这些都是要我们传进去的。所以我们在初始化时一定要使用带有参数的构造函数，并且这个参数就是我们的N（N是非类型模板参数） 。在初始化时便可以复用vector里面的resize()函数，但是resize()函数里面传的个数代表的整型的个数，而我们要的个数确是比特位的个数所以在这里便要处理一下：N/32+1（表示要开的整型的个数）代码如下：
bitset() { bits.resize(N /32 + 1,0);//开空间，开的是整型值的空间，并且要初始化为0 }
3.set成员函数（如果一个数出现便将对应的比特位改为1）
首先我们要明确的是每一个比特位对应着一个数。那我们的映射关系该如何处理呢？
其实也简单，要分两步：
1.找到你所在的整数下标，int i = x/32。
2.找到你在这个整数的第几个比特位,int j = x%32。
比如我开了100个比特位。那我对应的整数的个数便是n = 100/32+1，一共有4个整数0。
那如果我插入一个40，40映射的位置是多少呢？
1.整数下标：i = 40/32 ==1。
2.所在比特位：j = 40%32 == 8。
然后我们要做的便是将40映射的位置的值改为1，其它位置不变。如何搞呢？其实也简单，就是将所在的整数或等（|=）(i<<j)。如下代码所示：
void set(size_t x)//把对应整数的比特位置为1 { int i = x / 32;//表示在第几个整数。i表示下标 int j = x % 32;//对应的整数的比特位。 bits[i] |= (1 << j); }
4.reset函数（如果一个数出现便将对应的比特位改为0）
在写完set函数 以后，我们已经知道了如何找到映射的比特位了。所以在这里要做的便是将映射的比特位上的数字改为0，其它位置不变。如何操作呢，其实也简单。如下：
void reset(size_t x)//把对应整数的比特位置为0 { int i = x / 32;//表示在第几个整数。i表示下标 int j = x % 32;//对应的整数的比特位。 bits[i] &= ~(1 << j); }
5.test函数（检验数字存不存在）
如何检验一个数字存不存在呢？还是一样，先找到这个数字的映射比特位。然后让这再让这个数字映射的比特位所在的整数做&（1<<j）的操作。如在就得到一个非零数，如不在便得到一个0。代码如下：
bool test(size_t x)//检查是否出现 { int i = x / 32;//表示在第几个整数。i表示下标 int j = x % 32;//对应的整数的比特位。 return bits[i] & (1 << j); }
5.检验
现在我们得想一想了，我们要开多大的数据呢？多少个比特位呢？是40亿个比特位吗？
1.首先我们要明确：不是40亿个比特位。而是42亿九千万....个比特位（无符号整型的最大值个）。
2.那我们该如何开呢？用INT_MAX行吗？不行因为INT_MAX是有符号整型的最大值。那2*INT_MAX呢？还是不行，因为溢出然后被截断。
3.我们应该使用的是-1或者0xffffffff，来开空间。因为我们在类里面使用到的是size_t类型的参数，传入-1会被识别为最大的无符号整型值。
验证如下：
详细代码：
template<size_t N>//非类型模板参数
class bitset
{
public:
bitset()
{
bits.resize(N /32 + 1,0);//开空间，开的是整型值的空间，并且要初始化为0
}
void set(size_t x)//把对应整数的比特位置为1
{
int i = x / 32;//表示在第几个整数。i表示下标
int j = x % 32;//对应的整数的比特位。
bits[i] |= (1 << j);
}
void reset(size_t x)//把对应整数的比特位置为0
{
int i = x / 32;//表示在第几个整数。i表示下标
int j = x % 32;//对应的整数的比特位。
bits[i] &= ~(1 << j);
}
bool test(size_t x)//检查是否出现
{
int i = x / 32;//表示在第几个整数。i表示下标
int j = x % 32;//对应的整数的比特位。
return bits[i] & (1 << j);
}
private:
vector<char>bits;
};