深圳定制网站制作厂家,青岛网站建设电话,什么网站可以在线做高中题目,网站运营需要 做哪些工作内容目录
一、布隆过滤器的简介
二、布隆过滤器的实现
2.1 - BloomFilter.h
2.2 - test.cpp 一、布隆过滤器的简介
布隆过滤器#xff08;Bloom Filter#xff09;是由 Burton Howard Bloom 在 1970 年提出的一种紧凑型的、比较巧妙的概率型数据结构#xff08;probabilist…目录
一、布隆过滤器的简介
二、布隆过滤器的实现
2.1 - BloomFilter.h
2.2 - test.cpp 一、布隆过滤器的简介
布隆过滤器Bloom Filter是由 Burton Howard Bloom 在 1970 年提出的一种紧凑型的、比较巧妙的概率型数据结构probabilistic data structure特点是高效地插入和查询可以用来告诉你 某样东西一定不存在或者可能存在。
布隆过滤器的原理当插入一个数据时通过 K 个哈希函数将这个数据映射到位图结构中的 K 个比特位并把它们都置为 1。检索时如果 K 个比特位中的任何一个为 0则被检索的数据一定不存在如果都为 1则被检索的数据可能存在之所以说 可能 是误差的存在。 二、布隆过滤器的实现
2.1 - BloomFilter.h
#pragma once
#include bitset.h
#include string
namespace yzz
{struct BKDRHash{size_t operator()(const std::string str){size_t hash 0;for (const char ch : str){hash hash * 131 ch;}return hash;}};
struct APHash{size_t operator()(const std::string str){size_t hash 0;for (size_t i 0; i str.size(); i){size_t ch str[i];if ((i 1) 0)hash ^ (hash 7) ^ ch ^ (hash 3);elsehash ^ (~(hash 11)) ^ ch ^ (hash 5);}return hash;}};
struct DJBHash{size_t operator()(const std::string str){size_t hash 5381;for (const char ch : str){hash hash * 33 ^ ch;}return hash;}};
templatesize_t N, class K std::string, class Hash1 BKDRHash, class Hash2 APHash, class Hash3 DJBHashclass BloomFilter{public:void set(const K key){_bs.set(Hash1()(key) % N);_bs.set(Hash2()(key) % N);_bs.set(Hash3()(key) % N);}
bool test(const K key) const{if (_bs.test(Hash1()(key) % N) 0)return false;if (_bs.test(Hash2()(key) % N) 0)return false;if (_bs.test(Hash3()(key) % N) 0)return false;return true;}private:bitsetN _bs;};
} 各种字符串Hash函数 - clq - 博客园 (cnblogs.com)。 注意传统的布隆过滤器不支持删除操作因为删除一个数据可能同时删除了其它数据例如 删除 dantezhao 的同时也删除了 yyj。 Counting Bloom Filter 的出现解决了上述问题它将 Bloom Filter 的位数组的每一位扩展为一个小的计数器Counter。插入数据时给对应的 KK 为哈希函数的个数个 Counter 的值分别加 1删除数据时给对应的 K 个 Counter 的值分别减 1。Counting Bloom Filter 通过多占用几倍的存储空间的代价给 Bloom Filter 增加了删除操作。 2.2 - test.cpp
#include BloomFilter.h
#include iostream
using namespace std;
int main()
{yzz::BloomFilter100 bf;bf.set(唐三藏);bf.set(白龙马);bf.set(孙悟空);bf.set(猪八戒);cout bf.test(唐三藏) endl; // 1cout bf.test(白龙马) endl; // 1cout bf.test(孙悟空) endl; // 1cout bf.test(猪八戒) endl; // 1cout bf.test(沙悟净) endl; // 0return 0;
}
