哈希应用之布隆过滤器及其实现

本文主要是介绍哈希应用之布隆过滤器及其实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 布隆过滤器
- - 模拟实现

布隆过滤器

我们在上一篇中主要说的是位图，是用于判断整形是否存在的一种应用，但是他不好的地方就是只能判断整形了，如果是字符串的话就难再应用了

在之前哈希表中，我们使用了一些哈希函数来将字符串转化成整形，再存入哈希表

这里我们是否可以使用同样的方法呢

其实我们讲，可以但是还不够，因为相似的字符串很容易就会产生哈希冲突，本质上来说还是因为字符串的数量太庞大，远远超出了整形能承受的范围，从而形成一种多对少的效果，产生了冲突

那么对于这样的冲突，也不能直接存字符串，因为使用位图本身就是为了节省空间的

这时候就有人想到了一个方法，既然一个关键字（哈希地址）容易产生冲突，那么我如果使用两种不同的哈希函数，每一个字符串对应两个哈希地址，只有当两个哈希地址都是1的时候，我们才认为该字符串是已经存在的

但是这种存在依旧是“不可靠”的，在数据量特别巨大的时候，可能是别的字符串，恰好占用了这两个地址，此时就会误判，但是判断不存在的时候就是可靠的了，因为只要有一个是0，就说明这个字符串并不存在

这也就是为什么我们称之为过滤器，简单说一种应用就是用户注册时不允许重复名称，当我们查询时，发现不存在，这时就不需要再额外消耗资源去数据库中进行对比了，直接就可以确认，而当布隆过滤器发现，他是有可能存在的时候，再到数据库中对比，如果真的存在，再说不允许重复名称即可，这样就能节省大量的服务器资源，还能提高查询效率

模拟实现

struct BKDRHash {size_t operator()(const string& key) {size_t hash = 0;for (auto e : key) {hash *= 32;hash += e;}return hash;}
};struct APHash {size_t operator()(const string& key) {size_t hash = 0;for (auto e : key) {if ((e & 1) == 0) {hash ^= (hash << 7) ^ e ^ (hash >> 3);}else {hash ^= (~(hash << 11) ^ e ^ (hash >> 5));}}return hash;}
};struct DJBHash {size_t operator()(const string& key) {size_t hash = 0;for (auto e : key) {hash += (hash << 5) + e;}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);}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;
};