第十八讲：哈希2
目录
1、位图
1.1、位图的概念
1.2、位图的模拟实现
1.3、位图的应用
1.3.1、问题
1.3.2、模拟实现
1.4、库中的bitset
1.4.1、访问
1.4.2、比特操作
1.4.3、位图操作
2、布隆过滤器
2.1、概念
2.1.1、查找
2.1.2、删除
2.1.3、优缺点
2.1.4、问题
2.2、模拟实现
哈希是一种思想，把一个值与另一个值建立某种关系；哈希表、位图和布隆过滤器都是这种思想的一个具体实例。
1、位图
比如：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
注：40亿个整数需要的空间是很大的，内存是开不出这么大的连续空间的。
1.1、位图的概念
所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。
上面的问题就可以使用位图来解决，数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。
1.2、位图的模拟实现
// 这里的N是指需要多少比特位
template<size_t N>
class bitset
{
public:bitset(){//_bits.resize(N / 32 + 1, 0); // 用下面的这个和用左边的这个是一样的。_bits.resize((N >> 5) + 1, 0);}void set(size_t x) // 把x所在位置的比特位置成1{size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x) //把x所在位置的比特位置成0{size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x) // 判断值是否存在{size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;
};1.3、位图的应用
1.3.1、问题
1、给定100亿个整数，设计算法找到只出现一次的整数？
解决办法：使用两个比特位来记录状态。分三种状态，其中00表示出现0次的整数，01表示出现一次的整数，10表示出现两次及以上的整数。
2、给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
解决办法：各自映射到一个位图，一个值在两个位图中都存在，则是交集。
3、位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数？
解决办法：使用两个比特位来记录状态。分四种状态，其中00表示出现0次，01表示出现一次，10表示出现2次，11表示出现3次及以上。
1.3.2、模拟实现
用两个比特位记录状态的位图。
template<size_t N>
class twobitset
{
public:void set(size_t x){if (_bs1.test(x) == false && _bs2.test(x) == false) // 00->01{_bs2.set(x); }else if (_bs1.test(x) == false && _bs2.test(x) == true) // 01->10{_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) == true && _bs2.test(x) == false) // 10->11{_bs2.set(x);}}void PrintOnce() // 打印01的情况{for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout << i << endl;}}cout << endl;}void PrintTwice() // 打印10的情况{for (size_t i = 0; i < N; i++){if (_bs1.test(i) == true && _bs2.test(i) == false){cout << i << endl;}}cout << endl;}private:bitset<N> _bs1;bitset<N> _bs2;
};1.4、库中的bitset
bitset参考文档
template <size_t N>
class bitset;bitset的使用比较简单，下面仅仅只介绍简单常见的一些接口。
1.4.1、访问
bool operator[] (size_t pos) const;
reference operator[] (size_t pos);size_t size() const; // 返回比特位的个数bool test (size_t pos) const; // 判断pos位置的比特位的状态1.4.2、比特操作
bitset& set(); // 设置所有的比特位为1
bitset& set (size_t pos, bool val = true); // 设置pos位置比特位的状态bitset& reset(); // 设置所有的比特位为0
bitset& reset (size_t pos); // 设置pos位置的比特位的状态1.4.3、位图操作
template <class charT, class traits, class Alloc>
basic_string<charT,traits,Alloc> to_string() const; // 将位图转化为字符串例如：
void test03()
{std::bitset<100> bs;bs.set(40);bs.set(39);cout << bs.test(38) << endl;cout << bs.test(39) << endl;cout << bs.test(40) << endl;cout << bs.test(41) << endl;cout << bs.test(42) << endl << endl;cout << bs.to_string() << endl;
}2、布隆过滤器
位图一般只能处理整形数据，如果内容是字符串，就无法处理了。
2.1、概念
布隆过滤器是由布隆，在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。简单来说，布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中。如下图所示：
2.1.1、查找
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特 位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为 零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为存在一定的误判。
注：位图空间开的比较大，可以降低误判率。
2.1.2、删除
布隆过滤器不能直接支持删除，因为在删除一个元素时，可能会影响其他元素。
一种支持删除的方法（也就是使用引用计数来实现删除操作）：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的k个计数器)加一，删除元素时，给k个计数器减一，通过多占用几倍的存储空间的代价来增加删除操作。
2.1.3、优缺点
优点：
1、增加和查询元素的时间复杂度为：O(K)，(K为哈希函数的个数，一般比较小)，与数据量大小无 关。
2、布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
3、在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。
缺点：
1、有误判率，即不能准确判断元素是在集合中的。
2、不能获取元素本身。
3、一般情况下不能从布隆过滤器中删除元素。
2.1.4、问题
1、给两个文件，分别有100亿个字符串，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。
近似算法：使用布隆过滤器。
精确算法：假设平均一个字符串的长度为50字节，100亿字符串约为500G，内存肯定是存不下的。假设两个文件分别叫A和B，对于A文件我们将其分为500个小文件，读取A文件中的每一个字符串，然后通过哈希函数（i = Hash(字符串) % 500）计算出 i ，i 为几就将A中对应的字符串放入第几个小文件；B文件也是如此。如下图所示：
最后Ai和Bi都分别找出交集后，合在一起就是A文件和B文件的交集。
上面这种将大文件通过哈希函数切割成小文件的方式，就叫做哈希切割。
如果经过哈希切割出的小文件中有的还是很大怎么办？我们可以分为两种情况：
第一种情况：原文件中有很多重复的内容，导致后面切割出的有的小文件很大。解决办法，仍向位图中插入，重复插入的会失败。
第二种情况：原文件中有很多不同的内容，但是哈希冲突的比较严重，所导致的小文件很大。解决办法，换一个哈希函数，进行二次切分，再找交集。
2、给一个超过100G大小的日志文件，日志文件中存着IP地址，设计算法找到出现次数最多的IP地址？更进一步的如何找到前k个出现次数最多的的IP地址？
解决办法：通过哈希切割将该日志文件切割成数个小文件（相同IP一定进入了相同的小文件），然后用map对小文件依次进行统计即可；对于统计前k个出现次数最多的，使用堆对小文件进行依次处理即可。
2.2、模拟实现
struct BKDRHash
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};struct APHash
{size_t operator()(const string& key){size_t hash = 0;size_t ch;for (size_t i = 0; i < key.size(); i++){char ch = key[i];if ((i & 1) == 0){hash ^= ((hash << 7) ^ ch ^ (hash >> 3));}else{hash ^= (~(hash << 11) ^ ch ^ (hash >> 5));}}return hash;}
};struct DJBHash
{size_t operator()(const string& key){size_t hash = 5381;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}
};template<size_t N, class K = string, class HashFunc1 = BKDRHash, class HashFunc2 = APHash, class HashFunc3 = DJBHash>
class BloomFilter
{
public:void Set(const K& key){size_t hash1 = HashFunc1()(key) % N;size_t hash2 = HashFunc2()(key) % N;size_t hash3 = HashFunc3()(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}// 一般是不支持删除的，因为删除一个值可能会影响其他值。非要支持删除也是可以的，使用引用计数void Reset(const K& key);bool Test(const K& key){// 判断不存在是准确的size_t hash1 = HashFunc1()(key) % N;if (_bs.test(hash1) == false)return false;size_t hash2 = HashFunc2()(key) % N;if (_bs.test(hash2) == false)return false;size_t hash3 = HashFunc3()(key) % N;if (_bs.test(hash3) == false)return false;return true; // 可能存在误判}private:bitset<N> _bs;
};