哈希表——位图
- 基本概念
- 一道面试题
- 位图实现
- 设置存在或不存在
- 检查存在
- 解决一开始的问题
之前我们已经了解了哈希表的底层实现，今天我们来了解一下哈希表思想的衍生产物——位图。
基本概念
在了解位图之前，我们先来了解一些简单的概念。
我们都知道，计算机的数据和指令都是二进制的：
二进制里面只有0,1两个数字，这就意味着这两个数字可以表示两个不同的状态，位图的基础也是基于这一点。
所以，我们利用这一点。假设我们现在有一堆海量的数据，我可以通过某种方式让数字对应到相应的二进制的数位上，同时规定0表示该数字不存在，1表示存在。这本质上也是一种哈希的思想。
一道面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】
如果我们硬来，先将这40亿个数存起来，然后二分查找。这无疑是不行的。因为，光是把数据存起来就要用掉16GB的内存，而且要求空间连续。
但是这时候我们用位图，让位图的每一位对应一个数字，1表示存在，0表示不存在。这样可以大大降低内存的消耗：
大概我们想要是这样的：
我们所有的位是用来映射存在关系的。
位图实现
我们先来搭搭架子：
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace My_bitmap
{
//N是需要多少bit位
template<size_t N>
class bitmap
{
public:
private:
vector<int> _bmp;
};
}
现在我们来计算需要多少内存，然后通过构造函数，开出来相应的空间：
#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace My_bitmap
{
//N是需要多少bit位
template<size_t N>
class bitmap
{
public:
bitmap()
{
_bmp.resize(N / 32 + 1, 0); //开出相对应的空间，初始化所有位均为0
}
private:
vector <int> _bmp;
};
}
设置存在或不存在
现在我们有一个数假设为241，我们要把它设置到位图中，将相应的位设置为1。
因为我们以32位为一组，我们把241 / 32 ，可以得到241被分到了哪一个组，然后241 % 32 的到的是241在第几组的第几位：
现在我们找到了相应的位置，现在我们要将这个位从0变成1，表示241已经存在，但是我们不能影响其他位的状态，这个时候我们要想起来我们的位运算：
我们来实现一下：
bool set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bmp[i] |= (1 << j);
}
好了，我们现在完成了设置，但是现在我想把它又变为0，表示241又不存在了，该怎么办呢？
其实大同小异：
bool unset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bmp[i] &= (~(1 << j));
}
检查存在
检查存在和设置存在其实都差不多，只不过把或换成了与：
bool check(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return _bmp[i] & (1 << j);
}
我们来测试一下：
#include"bitmap.h"
int main()
{
My_bitmap::bitmap<10000> _bt;
_bt.set(241);
cout << "是否存在：" << _bt.check(241) << endl;
_bt.unset(241);
cout << "是否存在：" << _bt.check(241) << endl;
return 0;
}
解决一开始的问题
现在我们封装好了一个位图，但是我们只是解决了数据的储存，我们还没有解决如何只找出出现一次的数。
其实我们发现，这里面有三种状态：一次都没有出现的，出现一次，出现一次及其以上。
我们发现，这也表示状态，这样我们可以用我们上面位图再封装一个位图，这个位图用来寻找只出现了一次的数：
要表示三种状态，我们需要两个位图：
//N是需要多少bit位
template<size_t N>
class twobit_map
{
public:
void set(size_t x)
{
if (_bt1.check(x) == false && _bt2.check(x) == false)
{
_bt2.set(x);
}
else if (_bt1.check(x) == false && _bt2.check(x) == true)
{
_bt1.set(x);
_bt2.unset(x);
}
}
void Print()
{
for (size_t i = 0; i < N; i++)
{
if (_bt1.check(i) == false && _bt2.check(i) == true)
cout << "出现一次:" << i << endl;
}
}
private:
bitmap<N> _bt1;
bitmap<N> _bt2;
};
测试一下：
My_bitmap::twobit_map<241> _bt;
int a[] = { 12,34,45,67,12,90,90,45 };
for (auto e : a)
{
_bt.set(e);
}
_bt.Print();
我们依次类推，还可以找出出现了一次和两次的数：
template<size_t N>
class twobit_map
{
public:
void set(size_t x)
{
if (_bt1.check(x) == false && _bt2.check(x) == false)
{
_bt2.set(x);
}
else if (_bt1.check(x) == false && _bt2.check(x) == true)
{
_bt1.set(x);
_bt2.unset(x);
}
else if (_bt1.check(x) == true && _bt2.check(x) == false)
{
_bt2.set(x);
}
}
void Print()
{
for (size_t i = 0; i < N; i++)
{
if (_bt1.check(i) == false && _bt2.check(i) == true)
cout << "出现一次:" << i << endl;
else if (_bt1.check(i) == true && _bt2.check(i) == false)
cout << "出现两次" << i << endl;
}
}
private:
bitmap<N> _bt1;
bitmap<N> _bt2;
};
这样，我们可以灵活运用位图完成数据的查找，对于40亿的数据我们只需要开足够大的空间即可：
My_bitmap::twobit_map<0xffffff> _bt;
或者
My_bitmap::twobit_map<-1> _bt;
不过这个方法的保证自己写的代码中都使用的是无符号数，不然会有一点问题。
