1 位图
首先我们来看看一个腾讯的面试题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
分析：
40亿个不重复整形数据，大概有160亿字节，也就是16GB大小左右的数据，直接放在内存肯定是行不通的，一般内存没有那么大的空间，所以我们不能够用set/unoedered_set等容器来存放数据，那我们应该如何处理呢？
我们可以用哈希的思想来处理：将每一个数据映射一个比特位，比特位为1就表示该数据存在，为0就表示该数据不存在，这样40亿个数据就表示40亿个比特位，算下来就5亿字节左右的样子，也就是0.5GB，内存里面完全可以存下。
所谓位图，就是用每一个比特位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据是否存在。所以这种场景我们可以用位图来处理。
我们如何自己实现一个位图结构呢？大家可以参考下面这种方式：
template<size_t N> class bitset { public: bitset() { _bits.resize(N/8+1, 0); } void set(size_t num) { size_t i = num / 8; size_t j = num % 8; _bits[i] |= (1 << j); } void reset(size_t num) { size_t i = num / 8; size_t j = num % 8; _bits[i] &= ~(1 << j); } bool test(size_t num) { size_t i = num / 8; size_t j = num % 8; return _bits[i] & (1 << j); } private: vector<char> _bits; };
注意：
这里面给了一个非类型模板参数N，表示我们要开辟数据最大值（注意并不是数据有多少个）；
由于vector里面套用的是char,所以实际resize大小时/8，当然大家也可以用int,不过其他地方(像set/reset/test)也得做出相应的调整。
这个是我们自己实现的一份位图，不过STL里面也提供了一个位图结构：
【STL的bitset】
大家有兴趣可以下去看看这个结构，这里面提供的接口还是挺多的。
那位图还有哪些应用呢？
大家来看看下面这几道题，能不能找到些思路：
给定100亿个整数，设计算法找到只出现一次的整数？
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数?
我们首先来看看第一个问题：给定100亿个整数，设计算法找到只出现一次的整数？
分析：
100亿个整数，由于无符号整数最大才42亿多，所以里面肯定有大量重复数据，由于数据量过大，之前学过的红黑树/哈希表的方式根本行不通，所以只有通过位图来处理，那么我们究竟如何表示数据出现了一次和不是出现了一次呢？我们不妨用两个位图来表示一个数据，00表示没有数据，01表示只出现了一次，10表示出现了2次及以上。这样我们就能够快速判断出是否只出现了一次。我们可以自己在像上面一样设计一个2个比特位表示一个数据的位图结构，只不过里面数据处理就是/4 %4了，只不过这样做又得重新实现一份，我们不妨复用刚才实现的bitset,用两个bitset来标识。
实例代码：
template<size_t N> class twobits { private: bitset<N> _bits1; bitset<N> _bits2; public: void set(size_t num) { //00->01 if (_bits1.test(num) == false && _bits2.test(num) == false) { _bits2.set(num); } //01->10 else if (_bits1.test(num) == false && _bits2.test(num) == true) { _bits1.set(num); _bits2.reset(num); } } void print_one_cnt() { for (size_t i = 0; i < N; ++i) { if (_bits1.test(i) == false && _bits2.test(i) == true) cout << i << " "; } } };
我们可以直接打印出来所有只出现一次的数据并且排好了序。
我们在来看看问题2：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
分析：
思路一：两个文件中分别有100亿个整数，我们可以将其中一个文件放在位图结构中加载到内存，然后再从另外一个文件中一个一个读取数据在位图结构中test。
但是这样处理会有一个问题，大家想想是什么？这样处理的话非位图结构中的重复数据也就被保留了下来，也就是找到的文件交集会包含重复数据，那这样肯定是不行的。我们可以在找的时候第一次找到了就将位图结构的对应映射位置置空，这样下次找的时候就不会找到重复数据了。
思路二：将两个文件都放进位图中，然后在遍历整张位图看是否数据存在。
注意这种方式我们是要遍历到数据最大值的也就是0XFFFFFFFF,我们也可以将-1转换为size_t类型。因为我们并不知道最大数据是多少，所以必须开这么大(0XFFFFFFFF)的空间。
这里由于是有100亿的数据，所以我们选用第二种方式是可行的，假如数据量不是很大，比如10亿左右的话，我们就可以选用第一种方式，因为我们并不需要遍历整张位图，而是只遍历文件中数据即可。
再来看看问题3：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数?
分析：
相信解决了问题一后问题三的处理也会变得很简单了。00表示没有数据，01表示只出现了一次，10表示出现了2次，11表示出现了2次以上，这样我们就能够统计出不超过两次的所有整数。
我们可以浅浅总结下位图的应用：
1. 快速查找某个数据是否在一个集合中 2. 排序 + 去重 3. 求两个集合的交集、并集等 4. 操作系统中磁盘块标记
位图的优点是啥捏？
速度快，节省空间
那有啥缺点呢？
只能够映射整形，像浮点型，字符串等类型不能够映射。
像我们常用的字符串类型那应该怎么办呢？只是单纯的位图结构肯定是处理不了了，所以就引出了我们下面要讲的内容：布隆过滤器.
2 布隆过滤器
字符串不能够直接转化为整形，但是字符串可以间接的转换为整形，这就是字符串哈希，大家可以去看看下面的文章，介绍了比较常用的字符串哈希算法：【字符串哈希算法】
那我们可以将字符串通过字符串哈希算法转换为整形再来映射，但是这样做也引出了另外的问题，就是可能存在冲突：
假设通过某种哈希函数，出现了下面的这种情况：
我们发现了阿里和腾讯通过某种哈希算法映射到了同一个位置，那不就冲突了吗？有啥办法可以降低冲突吗？（注意：哈希冲突是无法避免，只能通过某种手段来降低冲突的概率)
我们不妨多给集中哈希算法，让每一个字符串映射多个位置，比如这里让每一个字符串用3中不同的哈希算法映射：
这样的话当我们判断时如果有其中一个哈希函数映射的位置不存在，那就说明该字符串一定是不存在的，而3个哈希函数映射的位置都存在的话是不能够一定确定该字符串一定是存在的，有可能存在误判（由于其他的字符串可能通过哈希函数映射到相同的位置）
所以这种方式我们可以得出结论：判断不在一定是准确的，判断在可能会存在误判。
此外布隆过滤器的长度也会直接影响误判的概率，一般来说，布隆过滤器越长，冲突的概率就越小，但是布隆过滤器也不能够太长，否则节省空间的优势就没有了，那么我们究竟如何权衡布隆过滤器的长度和哈希函数的个数呢？
有人专门做了这样的统计：参考自这篇文章【详解布隆过滤器的原理，使用场景和注意事项】
其中里面贴了一个公式：
其中k为哈希函数的个数，m为布隆过滤器的长度，n为插入元素的个数。
所以m=knln2
假设我们给了3个哈希函数，算下来m大概是5*n左右
我们可以自己来实现一个简易版的布隆过滤器：
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; } }; template<size_t N,class K=string,class Hash1= BKDRHash,class Hash2= APHash,class Hash3= DJBHash> class bloomfilter { private: static const int m = 5; bitset<N*m> _bit; public: void set(const K& key) { size_t len = N * m; size_t hashi1 = Hash1()(key) % len; size_t hashi2 = Hash2()(key) % len; size_t hashi3 = Hash3()(key) % len; _bit.set(hashi1); _bit.set(hashi2); _bit.set(hashi3); } bool test(const K& key) { size_t len = N * m; size_t hashi1 = Hash1()(key) % len; size_t hashi2 = Hash2()(key) % len; size_t hashi3 = Hash3()(key) % len; if (!_bit.test(hashi1)) return false; if (!_bit.test(hashi2)) return false; if (!_bit.test(hashi3)) return false; return true;//存在误判 } };
