C++ 实现布隆过滤器(BloomFilter)

代码如下:

#include <iostream> #include <vector> using namespace std;class BitMap { public:BitMap(size_t range) :_bit(range / 32 + 1) {}void set(const size_t num){int idx = num / 32;//idx 数组下标int bitIdx = num % 32;_bit[idx] |= 1 << bitIdx;}bool find(const size_t num){int idx = num / 32;int bitIdx = num % 32;return (_bit[idx] >> bitIdx) & 1;}void reset(const size_t num){int idx = num / 32;int bitIdx = num % 32;_bit[idx] &= ~(1 << bitIdx);}private:vector<int>_bit; };//哈希函数的个数: k = m/(n*ln(2))，其中m为位图需要的bit的大小，n为元素个数，k为哈希函数的个数struct HashFun1 {size_t operator()(const string & str){size_t hash = 0;for (const auto & ch : str){hash = hash * 131 + ch;}return hash;} };struct HashFun2 {size_t operator()(const string & str){size_t hash = 0;for (const auto & ch : str){hash = hash * 65599 + ch;}return hash;} };struct HashFun3 {size_t operator()(const string & str){size_t hash = 0;for (const auto & ch : str){hash = hash * 1313131 + ch;}return hash;} };template<typename T, typename HashFun1, typename HashFun2, typename HashFun3> class BloomFilter { public:BloomFilter(const size_t num) :_bit(5 * num), _bitCount(5 * num) {}void set(const T & val){HashFun1 h1;HashFun2 h2;HashFun3 h3;int idx1 = h1(val) % _bitCount;int idx2 = h2(val) % _bitCount;int idx3 = h3(val) % _bitCount;_bit.set(idx1);_bit.set(idx2);_bit.set(idx3);}bool find(const T & val){HashFun1 h1;HashFun2 h2;HashFun3 h3;int idx1 = h1(val) % _bitCount;int idx2 = h2(val) % _bitCount;int idx3 = h3(val) % _bitCount;if (!_bit.find(idx1)) return false;if (!_bit.find(idx2)) return false;if (!_bit.find(idx3)) return false;return true;//可能存在}private:BitMap _bit;size_t _bitCount; };

总结

以上是生活随笔为你收集整理的C++ 实现布隆过滤器(BloomFilter)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。