C++ -- 哈希扩展

目录

位图

位图概念

位图的实现

位图应用

布隆过滤器

布隆过滤器的提出

布隆过滤器概念

布隆过滤器的插入

 布隆过滤器的查找

布隆过滤器的删除

---

位图

        给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中？

• 遍历，时间复杂度O(N)
• 排序O(NlogN)，再利用二分查找logN
• 位图解决：数据是否在给定的整型数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果为1代表存在，为0代表不存在

使用位图可以大大减少空间的占用，40亿个无符号整数如果都要存储起来需要160亿字节，约为16G，如果要使用map和set来实现判断底层结构还需要消耗更多的空间。但如果使用位图，判断在不在只需要一个比特位,甚至只需要约0.5个G。

位图概念

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

位图的实现

基本框架：

set用于将存在的数据位置1，reset用于将原本存在而现在不存在的数据位置0，test用于判断某个数据位存不存在。

这里需要注意，位图概念上来说是以bit为单位的，但是我们编写代码时最小的单位并不是bit，而是char。这里我们直接用int来开辟空间，一个int为32个比特位，开辟N/32+1的空间即可。

namespace hx
{template<size_t N>class bitset{public:bitset(){_a.resize(N / 32 + 1);}void set(size_t x){//...}void reset(size_x){//...}bool test(size_t x){//...}private:vector<int> _a;};
}

set实现：

i -- x位于第几个整型

j -- x位于该整型的第几位

要将某一位置1，我们用按位或实现即可，即将1左移j位与该整型值相或，这样既不会影响该整型的其他数据位又可以把指定的数据位置1.（任何数据与0相或都不影响原来的值）

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

reset实现：

用按位与实现，将1左移j位后按位取反，再与原来的数据相与（任何数据与1相与都不影响原来的值）。

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

test实现：

假设该数据位位于整型的第二位，即j=2的情况，

1<<j 就是 00000100

此时若该数据存在，这个整型的第二位也为1，与1<<j相与后的结果不为0，返回真；

若该数据不存在，这个整型的第二位为0，与1<<j相与后的结果为0，返回假。

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

位图应用

1.给定100亿个整数，设计算法找到只出现一次的整数

        找到只出现一次的整数与判断在与不在不同的地方在于判断在不在只需要一个比特位，1代表存在，0代表不存在。而现在有不出现、出现1次、出现多次多种可能，所以我们可以用两个比特位来标识出现的次数。00 -- 出现0次，01 -- 出现1次，10 -- 出现两次或以上。代码实现：

template<size_t N>
class twobitset
{
public:void set(size_t x){// 00 -> 01if (!_bs1.test(x) && !_bs2.test(x)){_bs2.set(x);}// 01 -> 10else if (!_bs1.test(x) && _bs2.test(x)){_bs1.set(x);_bs2.reset(x);// 10代表出现两次及以上，不再发生改变}}bool is_once(size_t x){return !_bs1.test(x) && _bs2.test(x);}
private:bitset<N> _bs1;bitset<N> _bs2;
};

2.给两个文件，分别有100亿个整数，只有1G内存，如何找到两个文件的交集？

        假如我们将一个文件的所有值映射到一个位图，再去另一个文件判断在不在，这样的话得出的交集还需要去重。我们直接将两个文件分别映射到两个位图，对应的位置相与，如果为1这个值就是交集。

3.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数。

        该问题类似问题1，用两个位图解决。01 -- 出现1次，10 -- 出现2次， 11 -- 出现2次及以上。

布隆过滤器

布隆过滤器的提出

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

        用哈希存储用户记录非常浪费空间；而位图一般只能处理整型，如果内容编号是字符串，就无法处理了。因此我们需要把哈希和位图结合一下，即布隆过滤器。

        举个例子，我们将张三、李四、王五这些字符串通过哈希算法映射为某个整型值，存储在位图中。就可以实现快速判断某个人的名字在不在了。但是如下图所示的映射方法存在一个问题：当字符串很多时，所有字符串映射到一个值非常容易发生哈希碰撞。这样的查询结果是不准确的——如果查询结果为不存在，那么这个字符串确实一定不存在；但如果查询结果为存在，这个字符串不一定存在（有可能其他字符串与该字符串的映射结果相同）。

        因此我们做出相应的改进，同一个字符串不仅映射到一个位置而是多个位置，这样虽然无法消除误判，但却能一定程度降低误判率。

        这种方法存在的应用场景是不需要很精确的查询结果的，比如一个网站快速判断昵称是否被注册过。 

布隆过滤器概念

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

布隆过滤器的插入

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

 

        如图所示，字符串会通过不同的哈希算法映射不同的值，选用多种哈希算法映射多个值再在位图中置位可以降低误判率，以下是几种常见的字符串哈希算法：

struct BKDRHash
{size_t operator()(const string& s){// BKDRsize_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;}
};

 布隆过滤器的查找

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

        布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

布隆过滤器的删除

        布隆过滤器器不能直接支持删除工作，因为在删除一个元素时可能会影响其他元素。有些比特位会跟别的字符串映射位置重叠，删除一个元素会导致另一个元素也被“删除”了。

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

总结：

布隆过滤器优点：

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

布隆过滤器缺陷：

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

代码实现：

template<size_t N, 
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash, 
class HashFunc1 = DJBHash>
class BloomFilter
{
public:void Set(const K& key){size_t index1 = HashFunc1()(key) % N;size_t index2 = HashFunc2()(key) % N;size_t index3 = HashFunc3()(key) % N;_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool Test(const K& key){size_t index1 = HashFunc1()(key) % N;if (_bs.test(index1) == 0)return false;size_t index2 = HashFunc2()(key) % N;if (_bs.test(index2) == 0)return false;size_t index2 = HashFunc3()(key) % N;if (_bs.test(index3) == 0)return false;return true;}// 布隆过滤器不支持删除，删除可能会影响其他值
private:bitset<N> _bs;
};