【C++】哈希思想的两种应用实例

两种应用实例"/>

【C++】哈希思想的两种应用实例

位图

所谓位图，就是用一个bit位来标识数据的状态，通常是用于判断某个数据存不存在。
如果有40亿个不重复的无符号整数，没排过序。再给你一个无符号整数，如何快速判断这个数是否存在于这40亿个数中呢？
位图一般就能很好地处理这种海量数据，且无重复的情景。

// 位图的简单实现
// N 表示有N个数据要标识
template<size_t N>
class bit_set
{
public:// 构造bit_set(){_bits.resize(N / (8 * sizeof(char)) + 1, 0);}// 插入void set(size_t x){size_t i = x / (8 * sizeof(char));size_t j = x % (8 * sizeof(char));_bits[i] |= (1 << j);}// 删除void reset(size_t x){size_t i = x / (8 * sizeof(char));size_t j = x % (8 * sizeof(char));_bits[i] &= ~(1 << j);}// 查找bool test(size_t x){size_t i = x / (8 * sizeof(char));size_t j = x % (8 * sizeof(char));return _bits[i] & (1 << j);}
private:vector<char> _bits;
};

还有一些问题如下：
给定100亿个整数，如何找到只出现一次的整数？
给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
这些问题可以考虑使用两个位图来解决。

template<size_t N>
class double_bit_set
{
public:// 插入void set(size_t x){bool test1 = _bs1.test(x);bool test2 = _bs2.test(x);if (false == test1 && false == test2){_bs2.set(x);}else if (false == test1 && true == test2){_bs1.set(x);_bs2.reset(x);}}
private:bit_set<N> _bs1;bit_set<N> _bs2;
};

位图除了可以快速查找某个数据是否在一个集合中，还可以用于排序+去重；求两个集合的交集、并集等。
虽然位图的效率高，节省空间；但作用相对局限，只能用于映射处理整形。

布隆过滤器

布隆过滤器是一种紧凑型的，比较巧妙的概率型数据结构。
特点是高效的插入和查找。可以用于确定某个数据的不存在状态，但只能提供其可能存在的状态。
布隆过滤器是一种哈希与位图的结合。它使用多个哈希函数，将一个数据映射到位图结构中。
对于哈希函数个数和布隆过滤器长度之间的关系有如下公式供参考：
k = m n l n 2 k = \frac{m}{n}ln2 k=nm​ln2
k表示哈希函数个数，m表示布隆过滤器长度，n表示插入的数据个数。
满足上面公式的选择，可以尽量降低布隆过滤器的误判率。

#include <bitset>class HashBKDR
{
public:size_t operator()(const string& key){size_t hash = 0;for (char c : key){hash *= 131;hash += c;}return hash;}
};class HashAP
{
public:size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); ++i){if ((i & 1) == 0){hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));}}return hash;}
};class HashDJB
{
public:size_t operator()(const string& key){size_t hash = 5381;for (char c : key){hash += (hash << 5) + c;}return hash;}
};// 这里给出三种字符串哈希算法
template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:// 插入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);}// 查找// 布隆过滤器的查找，如果有一个bit映射为0，可以确定这个数据不存在；如果bit映射的都为1，表示这个数据可能存在，即也可能不存在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; // 可能存在误判}
private:const static size_t _ratio = 5; // 由公式大致确定布隆过滤器的长度和插入数据个数的关系bitset<_ratio*N>* _bits = new bitset<_ratio*N>;
};

传统的布隆过滤器是不支持删除操作的。因为删除一个数据时，其所有bit映射都被置为0，可能会影响其它数据，使其它并未被删除的数据，也连带被删除了。

布隆过滤器的优势与缺陷

1. 布隆过滤器的优势：
   布隆过滤器增加和查找数据的时间复杂度都为O(K)，K为哈希函数的个数。
   布隆过滤器不需要存储具体数据，在某些对保密性要求比较高的场合会有优势。
   如果能够承受一定结果的误判，布隆过滤器相比其它数据结构会有更大的空间优势。
2. 布隆过滤器的缺陷：
   布隆过滤器的缺陷主要在于其存在误判且不可避免。同时一般情况下是不支持删除数据的。