目录
文章结尾附有大厂经典面试题
位图
引入
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中，只有1G内存可以使用。【腾讯】
这是一道腾讯的面试题，对于查找方法有暴力查找O(N)，二分查找(O(logN),但是二分查找要有序），哈希表或红黑树...
查找数据的方法有很多，但是对于海量数据的查找这些容器是无法存储的，所以在查找之前要先对数据进行切分，40亿数据就需要拆分成许多份，十分麻烦且效率也不高。
思考：有没有什么方法能够记录数据是否存在且不需要按照数据的个数开辟空间？？？
此时哈希表的直接定值法好像刚好满足：通过数据大小与数据位置关系建立关系，空间的开辟依靠的是最大数和最小数的差。
但是哈希表用每一个字节来存储数据是否存在，这样的话40亿个整形需要大约3.8GB的空间，这空间还是太大了，用一个字节太大了，能不能用比特位来表示一个数据是否存在？？？
如果使用比特位来表示的话就只需要大约0.5G内存就可以实现。
每一个比特位有两种状态：0或1，那不就可以用其分别表示两种状态吗！0表示数据不存在，1表示数据存在。
位图概念
位图：所谓位图就是用每一位来存放数据的状态，适用于海量数据，无法重复数据。通常是用来判断某个数据是否存在的。
在STL库中位图对应的容器时bitset，其常用的成员函数有3个：set用来标记数据存在；reset用来删除标记的数据；test用来检查一个数据是否存在。
位图用位来表示数据状态，所以可以采用vector容器作为数组来存放每一个位的状态。
template<size_t N> //用N来表示儿科存储的位数
class bitset
{
public:
bitset()
{
bs.resize(N / 32 + 1);
}
private:
vector<int> bs;
};位图的模拟实现
设置数据
在对一个位图的二进制位进行标记的时候，要先找到对应的二进制位。
比如一个数据val在x86环境下进行标记：1）找到在哪一个字节中x=val/32；2）在这一个字节的哪一个位置y=val%32；
//位图数据的标记
void set(const int& val)
{
int x = val / 32;
int y = val % 32;
bs[x] |= (1 << y); //通过按位或|来对二进制位进行标记
}删除设置的数据
与设置数据存在一样，找到位置将二进制位设置为0；
//删除位图数据的标记
void reset(const int& val)
{
int x = val / 32;
int y = val % 32;
bs[x] &= ~(1 << y); //通过~取反和按位与恢复数据的标记
}检查数据是否存在
bool test(const int& val)
{
int x = val / 32;
int y = val % 32;
return (bs[x] >> y) & 1;
}位图的引用
1）快速查找数据是否在一个集合内；
2）排序+去重；
3）求两个集合的交集，并集等；
4）操作系统中磁盘块的标记。
布隆过滤器
引入
位图实现了对于整形的快速查找，但是对于如果需要在众多字符串中进行查找使用位图就无法再实现了，此时就需要引入布隆过滤器来实现了。
布隆过滤器概念
布隆过滤器是通过哈希函数来将字符串映射为整形再进行存储的。
将字符串通过哈希函数映射为整形，必然会出现两个不同字符串映射到同一个整形上的情况，这也就导致了在检查一个字符串是否存在的时候可能会出现误判。
为了降低布隆过滤器的误判率的方法：将一个字符串通过不同函数映射出不同位置，在检查一个数据是否穿在的时候，对多个位置进行检查。但是这种方法需要将空间扩大，否则误判的概率还是不小的。
以上是别人研究得出的误判率与哈希函数，空间大小以及插入元素个数之间的关系。
布隆过滤器的实现
布隆过滤器的底层使用位图+哈希函数实现。
其参数包含两种：位图的位数和哈希函数。
template<size_t N,class Hash1= BKDRHash,class Hash2= APHash,class Hash3= DJBHash>
class BloomFilter
{
public:
private:
bitset<N> bf;
};设置数据
对于插入使得哈希函数，此处采用以上三个进行演示。
struct BKDRHash
{
size_t operator()(const string& s)
{
// BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long i = 0; i < s.size(); i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};插入是只需将数据映射到相应位置即可。
void set(const string& s)
{
size_t hash1 = Hash1()(s) % N; //通过仿函数将字符串转化为整形，注意此处需要%N防止标记位置越界
bf.set(hash1);
size_t hash2 = Hash2()(s) % N;
bf.set(hash2);
size_t hash3 = Hash3()(s) % N;
bf.set(hash3);
}删除设置的数据
布隆过滤器是不支持对数据的删除的，因为如果一个位置有多个字符串同时映射，对其中一个字符串进行删除后会影响到另一个字符串。
如果想要对数据进行删除的话，需要使用引用计数来保留该位置被映射的此处，此时使用多个位图来记录数据个数即可。
检查数据是否存在
检查后如果返回false，则说明其一定不存在；但是如果返回的是true，其不一定准确，可能是误判。
bool test(const string& s)
{
size_t hash1 = Hash1()(s) % N;
if (bf.test(hash1) == 0)
return false;
size_t hash2 = Hash2()(s) % N;
if (bf.test(hash2) == 0)
return false;
size_t hash3 = Hash3()(s) % N;
if (bf.test(hash3) == 0)
return false;
return true;
}布隆过滤器的优点
1）在能接受一定误判的情况下，其查找效率极高；
2）插入数据的时间复杂度是O(K)，K表示哈希函数的个数，插入效率极高；
3）每一个哈希函数没有关联，方便硬件并行计算；
4）不存储数据实际类型，具有一定的保密功能；
5）数据量大的时候，布隆过滤器可以表示全集，其他容器空间不够；
6）布隆过滤器可以实现对不同集合求交，并，补集。
布隆过滤器缺点
1）对数据查找有误判；
2）不能删除数据；
3）不能存储数据本身。
海量数据面试题
1.只出现过一次的数据
1. 给定100亿个整数，设计算法找到只出现一次的整数？
找出只出现一次的数据，就需要对数据个数进行记录；此处可以采用两个位图来实现，每个数据用两个位存储；也就是原本存储的状态有0和1，现在的存储状态有3种：00和01和10；其中只有01表示只出现过一次。
template<size_t N>
class TwoSet
{
public:
//对数据进行标记
void set(const int& val)
{
if (bs1.test(val) == 0 && bs2.test(val) == 0)
{
//此处表示00存储成01
bs2.set(val);
}
else if (bs1.test(val) == 0 && bs2.test(val) == 1)
{
//此处表示01存储成10
bs1.set(val);
bs2.reset(val);
}
}
//检查是否只出现了一次
bool test(const int& val)
{
return bs1.test(val) == 0 && bs2.test(val);
}
private:
bitset<N> bs1;
bitset<N> bs2;
};2.两个文件求交集
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
思路：将第一个文件先用位图存储，再遍历第二个文件，找到了就是交集，同时将该数据从位图中删除，防止交集出现重复。
代码与上面类似，此处就不演示了。
3.出现此处不超过2的数据
3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数；
与第一个题一样，采用两个位图，此处使用4种状态：00，01，10，11。代码与第一题相同。
4.找两个query文件交集
1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出
精确算法和近似算法
query就是字符串。
近似算法：使用布隆过滤器，先将一个文件放入布隆过滤器中存放，再遍历另一个文件，在布隆过滤器中检查是否存在。
精确算法：不去使用布隆过滤器；先对文件进行切分，不是简单的均衡，而是使用哈希函数得出每个字符串对应的整形val，再创建多个文件进行存放，比如创建1000个文件，将val%1000来确定其存放到哪一个文件中，这样使得相同字符串必定在对应编号的文件中；即A1文件的字符串去B1文件中查找，A2文件的字符串去B2文件中查找，An件的字符串去Bn文件中查找。
查找的时候使用set进行查找的效率比较高，但是如果一个文件中有大量字符串映射就可能导致set不够存储。
出现大量数据的可能性有两种：1）一个文件中重复数据太多；2）重复数据不多，映射到文件中的字符串太多。
对于第一种情况，set对自动过滤掉重复数据，所以不会出现问题；但是第二种却不行。
所以对于第二种：进程会抛异常，再抛异常后，会数据进行重新切分，用其他的哈希函数即可。
5.找出出现此处最多的字符串
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
还是使用哈希切分，相同的字符串被切分到一个文件中去，再使用map对每个文件的字符串进行计数即可。