【数据结构】哈希应用

目录

一、位图

1、位图概念

2、位图实现

2.1、位图结构

2.2、比特位置1

2.3、比特位置0

2.4、检测位图中比特位

3、位图例题

3.1、找到只出现一次的整数

3.2、找到两个文件交集

3.3、找到出现次数不超过2次的所有整数

二、布隆过滤器

1、布隆过滤器提出

2、布隆过滤器概念

3、布隆过滤器实现

3.1、布隆过滤器的插入

3.2、布隆过滤器的查找

3.3、布隆过滤器删除

4、布隆过滤器例题

4.1、找到两个存贮query的文件的交集

4.2、哈希切割

---

一、位图

1、位图概念

 所谓位图，就是用每一个比特位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的优点：

• 速度快
• 节省空间

位图的缺点：

• 只能映射整型 ，其他类型如：浮点数、string等等不能存储映射。

2、位图实现

2.1、位图结构

位图类的结构如下：

template<size_t N>
class bitset
{
public:bitset(){_bits.resize(N / 8 + 1, 0);}//将某个比特位置1void set(size_t x){}//将某个比特位置0void reset(size_t x){}//检查位图中某个比特位是否为1bool test(size_t x){}private:vector<char> _bits;
};

2.2、比特位置1

实现代码：

	void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (1 << j);}

 用除法计算 x 映射的位在数组的第 i 个 char 类型内。 用取模计算 x 映射的位在第 i 个 char 类型的第 j 个比特位。然后用按位或运算把指定比特位置1。

 需要注意的是在进行按位或运算时，使用的是 1 左移 j 位，而不是右移。这是因为在我们人类的主观认识上，数位的排列是下面这样的：

 但实际上，在计算机的虚拟层储存逻辑上，数位的保存是这样的：

 我们所说的左移与右移，并不是向左移动或者向右移动，而是向高位移动与向低位移动。因此为了找到目标位置，需要使用左移，而不是右移。

2.3、比特位置0

实现代码：

	void reset(){size_t i = x / 8;size_t j = x % 8;_bits[i] &= ~(1 << j);}

 用除法计算 x 映射的位在数组的第 i 个 char 类型内。 用取模计算 x 映射的位在第 i 个 char 类型的第 j 个比特位。然后用按位非与运算把指定比特位置1。

2.4、检测位图中比特位

实现代码：

	bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);}

3、位图例题

3.1、找到只出现一次的整数

设置状态：出现 0 次，状态是 00 。出现 1 次，状态是 01 。出现 2 次及以上，状态是 10 。

template<size_t N>
class twobitset
{
public:void set(size_t x){// 00->01if (_bs1.test(x) == false&& _bs2.test(x) == false){_bs2.set(x);}// 01->10else if (_bs1.test(x) == false&& _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}//10}void Print(){for (size_t i = 0; i < N; ++i){if (_bs2.test(i)){cout << i << endl;}}}
public:bitset<N> _bs1;bitset<N> _bs2;
};

测试结果如下： 

3.2、找到两个文件交集

 方法一：把其中一个文件的值读取到位图中，再读取另一个文件，判断在不在上面的位图中，在就是交集，取出该值，并把对应位图置0。

 方法二：创建两个位图，读取文件1的数据映射到位图1，读取文件2的数据映射到位图2。然后让位图1与位图2按位与。最终结果是交集。

3.3、找到出现次数不超过2次的所有整数

 设置状态：出现 0 次，状态是 00 。出现 1 次，状态是 01 。出现 2 次，状态是 10 。出现 3 次及以上，状态是 11 。

实现代码与 3.1 中类似。

二、布隆过滤器

1、布隆过滤器提出

 我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1.  用哈希表存储用户记录，缺点：浪费空间。
2.  用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3.  将哈希与位图结合，即布隆过滤器。

2、布隆过滤器概念

 布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

 布隆过滤器可以降低冲突的概率。一个值映射到一个位置，容易误判，映射到多个位置，就可以降低误判率。

布隆过滤器的优点：

• 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关。
• 哈希函数相互之间没有关系，方便硬件并行运算。
• 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。
• 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。
• 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能。
• 使用同一组散列函数的布隆过滤器可以进行交、并、差运算。

 布隆过滤器的缺点：

• 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)。
• 不能获取元素本身。
• 一般情况下不能从布隆过滤器中删除元素。
• 如果采用计数方式删除，可能会存在计数回绕问题。

3、布隆过滤器实现

3.1、布隆过滤器的插入

 向布隆过滤器中插入："baidu"：

 向布隆过滤器中插入："tencent"： 

 

 实现代码：

struct BKDRHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};struct DJBHash
{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};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;}
};template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter
{
public:void set(const K& key){size_t len = N * _X;size_t hash1 = Hash1()(key) % len;_bs.set(hash1);size_t hash2 = Hash2()(key) % len;_bs.set(hash2);size_t hash3 = Hash3()(key) % len;_bs.set(hash3);}
private:static const size_t _X = 4; // 布隆过滤器的长度与数据数量的倍数关系bitset<N*_X> _bs;  //这样可以有效的减少不同数据间的冲突
};

3.2、布隆过滤器的查找

 布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

实现代码：

bool test(const K& key)
{size_t len = N * _X;size_t hash1 = Hash1()(key) % len;if (!_bs.test(hash1))return false;size_t hash2 = Hash2()(key) % len;if (!_bs.test(hash2))return false;size_t hash3 = Hash3()(key) % len;if (!_bs.test(hash3))return false;return true;//依然存在误判，有可能把不在的判断成在
}

 需要注意的是，即使使用了三个哈希函数进行判断，仍然存在误判的可能性。如果判断该数据不存在，则该数据一定不存在。如果判断该数据存在，则该数据有一定的可能性其实不存在。

 因此，布隆过滤器只能运用于能够容忍误判的场景，比如视频推送等等。而对于一些不容忍误判的场景下，布隆过滤器也有相应的解决方法：如果判断出数据存在，就到数据库中进行二次确认，依然存在就返回存在，不存在就返回不存在。

 哈希函数个数，代表一个值映射几个位，哈希函数越多，误判率越低，但是哈希函数越多，平均占的空间就越大。

3.3、布隆过滤器删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

  一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中。
2. 存在计数回绕。

4、布隆过滤器例题

4.1、找到两个存贮query的文件的交集

使用哈希切分，把一个大文件分割成多个小文件，再让小文件之间取交集：

 使用这种方法，因为不是平均切分，可能会出现冲突多，某一个Ai、Bi小文件过大的问题。出现这种问题无非两种情况：

1. 单个文件中，有某个大量重复的query。
2. 单个文件中，有大量不同的query。

可以直接使用一个unordered_set/set，依次读取文件query，插入set中：

1. 如果读取了整个小文件的query，都可以成功插入set，说明是情况一。
2. 如果读取了整个小文件的query，插入过程中出现抛异常，说明是情况二。换成其他哈希函数，再次分割，再求交集。

说明：set插入key，如果已经有了，返回false。如果内存用完了就会抛bad_alloc异常，剩下的都会成功。

4.2、哈希切割

 给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址。

依然使用哈希切割的方法：

 依次处理每一个小文件，使用unordered_map 或 map 统计ip出现的次数。

1.  如果统计过程中，没有抛异常则正常统计。统计完一个小文件，记录最多的那一个。clear内存，再统计下一个小文件。
2.  如果统计过程中，出现抛异常现象，说明单个文件过大，冲突太多。换成其他哈希函数，再次分割。

 建立一个k个数据的小堆，每统计一次，就插入小堆，转换成topK问题，最终可以解决。