一、位图的引入
我们先来看一道题。
题目描述：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
思路一：遍历
拿到这道题，我们最先想到的方法就是直接遍历了。从头到尾遍历一遍，一定可以判断出一个数是否在其中。时间复杂度为 o(N)。
思路二：排序+二分查找
时间复杂度为 排序 o(N*logN) + 二分查找 o(logN)。
思路三：位图
上面两种方法很常用，但是在面对40亿个数据时，无论是空间复杂度还是时间复杂度都很大。那么有没有比它们更加优秀的方法呢？
这里，我们就可以用位图去帮助我们解决这个问题：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
二、概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用
来判断某个数据存不存在的。
如下图就是一个位图
三、位图的实现
在标准库里也是实现了位图的。
上图只截取了它的三个主要操作。下面我们分别来讲一讲它的三个操作。
1、set
set的作用是将x对应的比特位置设为1，表示其存在。相当于插入的作用。
void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); }
2、reset
reset的作用是将x对应的比特位置设为0，用来表示删除。
void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~(1 << j); }
3、test
test的作用是用来查看x在不在。
bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 << j); }
4、位图实现
#pragma once #include<iostream> #include<vector> using namespace std; namespace zdl { template<size_t N> class bitset { public: bitset() { _bits.resize(N / 8 + 1, 0); } void set(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] |= (1 << j); } void reset(size_t x) { size_t i = x / 8; size_t j = x % 8; _bits[i] &= ~(1 << j); } bool test(size_t x) { size_t i = x / 8; size_t j = x % 8; return _bits[i] & (1 << j); } private: vector<char> _bits; }; void test01() { bitset<100> bs; bs.set(8); bs.set(9); bs.set(20); cout << bs.test(8) << endl; cout << bs.test(17) << endl; bs.reset(8); cout << bs.test(8) << endl; } }
四、位图的应用
我们直接来看相关的题。
1、给定 100 亿个整数，设计算法找到只出现一次的整数。
我们首先来分析一下：我们需要从100亿个整数中，找到只出现一次的整数，数据量很大，那么我们就可以考虑使用位图的思想。而且这些数有三种状态，即：出现0次，1次以及1次以上。所以说我们只要保存一个数是否是三种状态的一种。但是，位图只能有两种状态：存在或者不存在。那么我们应该怎么解决这个问题呢？
这里我们就可以使用两个位图来帮助我们存储三种状态。如下图： 
template<size_t N> class twobitset { public: void set(size_t x) { if (!_bs1.test(x) && !_bs2.test(x))//00 { _bs2.set(x);//01 } else if (!_bs1.test(x) && _bs2.test(x))//01 { _bs1.set(x); _bs2.reset(x);//10 } //10不变 } private: bitset<N> _bs1; bitset<N> _bs2; };
2、给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？
思路：将两个文件中的整数分别映射到两个位图中，然后将两个位图按位与，得到一个位图，如果这个位图的某个位上是1，那这个就是交集。
五、布隆过滤器
我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？
1、布隆过滤器的引入
针对上面的问题，我们有如下的解决方法：
1、用哈希表存储用户记录，缺点：浪费空间。
2、用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。（不同的字符串，转化成整型后，可能会映射到相同的位置）
而解决这类问题的最好方法，就是使用布隆过滤器。将哈希与位图结合，即布隆过滤器。
2、概念
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
根据上图，我们可以简单总结一下布隆过滤器的思想：同一个数据，根据不同的哈希函数转换成不同的整型，来映射到不同的位。也就是说同一个数据会映射多个位。这样就可以区分不同的字符串了。当然，也不排除不同字符串任然会映射到完全相同位置的可能。但是，哈希函数越多，可能性越小。
我们首先根据大佬们总结出来的算法，来确定几个哈希函数（这里我们确定三个）。
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; } };
3、实现
* 基本框架
template<size_t N, class K = string, class HashFunc1 = BKDRHash, class HashFunc2 = APHash, class HashFunc3 = DJBHash> class BloomFilter { public: private: const static size_t _ratio = 5; bitset<_ratio* N> _bits; };
* 插入：set
void Set(const K& key) { size_t hash1 = Hash1()(key) % (_ratio * N); _bits.set(hash1); size_t hash2 = Hash2()(key) % (_ratio * N); _bits.set(hash2); size_t hash3 = Hash3()(key) % (_ratio * N); _bits.set(hash3); }
* 查找：test
bool Test(const K& key) { size_t hash1 = Hash1()(key) % (_ratio * N); if (!_bits.test(hash1)) return false; size_t hash2 = Hash2()(key) % (_ratio * N); if (!_bits.test(hash2)) return false; size_t hash3 = Hash3()(key) % (_ratio * N); if (!_bits.test(hash3)) return false; return true; }
* 删除
布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。
4、布隆过滤器的优点
1、增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关。
2、哈希函数相互之间没有关系，方便硬件并行运算。
3、布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
4、在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。
5、布隆过滤器的缺点
1、有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)。
2、不能获取元素本身。
3、一般情况下不能从布隆过滤器中删除元素。
4、如果采用计数方式删除，可能会存在计数回绕问题。
六、哈希切割
我们直接来看一个问题
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？如何找到top K的IP？
思路：读取每个ip，算哈希值 i = hash(ip) % 100，这个ip进入第i个小文件（相同的ip，一定进入相同的文件），利用 map<string, int>，对每个小文件统计次数。
若要寻找top K 的 ip，建一个K个值为<ip, cout>的小堆，去解决top K问题。
