动漫网站建设意义,重庆app定制,win2003搭建wordpress,网站建设及推广衬胶蝶阀目录
布隆过滤器
完整代码
布隆过滤器应用
布隆过滤器的查找 布隆过滤器删除 布隆过滤器优点
布隆过滤器缺陷 布隆过滤器海量数据处理 布隆过滤器
位图只能映射整形#xff0c;而对于字符串却无能为力。
把字符串用哈希算法转成整形#xff0c;映射一个位置进行标…目录
布隆过滤器
完整代码
布隆过滤器应用
布隆过滤器的查找 布隆过滤器删除 布隆过滤器优点
布隆过滤器缺陷 布隆过滤器海量数据处理 布隆过滤器
位图只能映射整形而对于字符串却无能为力。
把字符串用哈希算法转成整形映射一个位置进行标记
下面就是布隆过滤器设计思路 位图是直接定址法不存在冲突而字符串可能转成整形后会有重合的地方发生下面这种冲突误判。 布隆过滤器存在误判如这里如果美团不存在而B站存在此时美团的位置被B站占据有可能会误判为美团此时存在。
这种误判不可能完全去掉但我们可以通过优化降低误判率。
优化方法让每个值多映射几个位如美团映射好几个位就能减少上面误判的概率。理论而言一个值映射的位越多误判冲突的概率就越低但如果映射过多空间消耗就会增大。 判断某邮箱是否在黑名单中可用布隆过滤器进行简单的过滤 完整代码
struct HashBKDR
{// BKDRsize_t operator()(const string key){size_t val 0;for (auto ch : key){val * 131;val ch;}return val;}
};
struct HashAP
{// BKDRsize_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;}
};struct HashDJB
{// BKDRsize_t operator()(const string key){size_t hash 5381;for (auto ch : key){hash (hash 5) ch;}return hash;}
};//N表示准备要映射N个值
templatesize_t N,class Kstring,class Hash1HashBKDR, class Hash2HashAP, class Hash3HashDJB
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);}bool Test(const K key)//只要有一个位为0就return false。{size_t hash1 Hash1()(key) % (_ratio * N);if (!_bits.set(hash1))return false;size_t hash2 Hash2()(key) % (_ratio * N);if (!_bits.set(hash2))return false;size_t hash3 Hash3()(key) % (_ratio * N);if (!_bits.set(hash3))return false;return true;//返回真也可能存在误判}
private:const static size_t ratio 5;//比例bitset_ratio*N _bits;
}; void TestBloomFilter1()
{BloomFilter10 bf;string arr1[] { 苹果, 西瓜, 阿里, 美团, 苹果, 字节, 西瓜, 苹果, 香蕉, 苹果, 腾讯 };for (auto str : arr1){bf.Set(str);}for (auto str : arr1){cout bf.Test(str) endl;}cout endl endl;string arr2[] { 苹果111, 西瓜, 阿里2222, 美团, 苹果dadcaddxadx, 字节, 西瓜sSSSX, 苹果 , 香蕉, 苹果$, 腾讯 };for (auto str : arr2){cout str : bf.Test(str) endl;}
} 上半部分是进行Set下半部分是TestSet
测试用例2
void TestBloomFilter2()
{srand(time(0));const size_t N 100000;BloomFilterN bf;cout sizeof(bf) endl;std::vectorstd::string v1;std::string url https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html;for (size_t i 0; i N; i){v1.push_back(url std::to_string(1234 i));}for (auto str : v1){bf.Set(str);}// 相似std::vectorstd::string v2;for (size_t i 0; i N; i){std::string url http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html;url std::to_string(rand() i);v2.push_back(url);}size_t n2 0;for (auto str : v2){if (bf.Test(str)){n2;}}cout 相似字符串误判率: (double)n2 / (double)N endl;std::vectorstd::string v3;for (size_t i 0; i N; i){string url zhihu.com;url std::to_string(rand()i);v3.push_back(url);}size_t n3 0;for (auto str : v3){if (bf.Test(str)){n3;}}cout 不相似字符串误判率: (double)n3 / (double)N endl;
} 这里的比例越大开的空间越多误判率就会降低。 对于库中的布隆过滤器若开的空间过大会导致栈溢出我们可以把空间转移到堆上去以下是转移到堆上的代码
用我们上面自己写的代码就不会栈溢出因为开的空间很小
templatesize_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);//cout hash1 endl;_bits-set(hash1);size_t hash2 Hash2()(key) % (_ratio*N);//cout hash2 endl;_bits-set(hash2);size_t hash3 Hash3()(key) % (_ratio*N);//cout hash3 endl;_bits-set(hash3);}bool Test(const K key){size_t hash1 Hash1()(key) % (_ratio*N);//cout hash1 endl;if (!_bits-test(hash1))return false; // 准确的size_t hash2 Hash2()(key) % (_ratio*N);//cout hash2 endl;if (!_bits-test(hash2))return false; // 准确的size_t hash3 Hash3()(key) % (_ratio*N);//cout hash3 endl;if (!_bits-test(hash3))return false; // 准确的return true; // 可能存在误判}// 能否支持删除-void Reset(const K key);private:const static size_t _ratio 5;std::bitset_ratio*N* _bits new std::bitset_ratio*N;
};布隆过滤器应用 布隆过滤器的查找 布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中因此被映射到的位置的比特 位一定为1。所以可以按照以下方式进行查找分别计算每个哈希值对应的比特位置存储的是否为 零只要有一个为零代表该元素一定不在哈希表中否则可能在哈希表中。 注意布隆过滤器如果说某个元素不存在时该元素一定不存在如果该元素存在时该元素可 能存在因为有些哈希函数存在一定的误判。 比如在布隆过滤器中查找alibaba时假设3个哈希函数计算的哈希值为1、3、7刚好和其 他元素的比特位重叠此时布隆过滤器告诉该元素存在但实该元素是不存在的。 布隆过滤器删除 布隆过滤器不能直接支持删除工作因为在删除一个元素时可能会影响其他元素。 比如删除上图中tencent元素如果直接将该元素所对应的二进制比特位置0“baidu”元素也 被删除了因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。 一种支持删除的方法将布隆过滤器中的每个比特位扩展成一个小的计数器插入元素时给k个计 数器(k个哈希函数计算出的哈希地址)加一删除元素时给k个计数器减一通过多占用几倍存储 空间的代价来增加删除操作。 缺陷 1. 无法确认元素是否真正在布隆过滤器中 2. 存在计数回绕 布隆过滤器优点 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数一般比较小)与数据量大小无 关 2. 哈希函数相互之间没有关系方便硬件并行运算 3. 布隆过滤器不需要存储元素本身在某些对保密要求比较严格的场合有很大优势 4. 在能够承受一定的误判时布隆过滤器比其他数据结构有这很大的空间优势 5. 数据量很大时布隆过滤器可以表示全集其他数据结构不能 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 布隆过滤器缺陷 1. 有误判率即存在假阳性(False Position)即不能准确判断元素是否在集合中(补救方法再 建立一个白名单存储可能会误判的数据) 2. 不能获取元素本身 3. 一般情况下不能从布隆过滤器中删除元素 4. 如果采用计数方式删除可能会存在计数回绕问题 布隆过滤器海量数据处理
1. 给两个文件分别有100亿个query字符串我们只有1G内存如何找到两个文件交集分别给出精确算法和近似算法
精确算法哈希切分
步骤1.假设每个查询需要30byte空间100亿个查询需要3000亿byte约等于300G 2.假设俩个文件叫A和B依次读取文件A中的query(查询)然后转成整形并取模这个query就进入编号为Ai的小文件 之后开始找交集对编号相同的找交集 为什么要对应相同编号找交集
相同的query一定进入了相同编号的小文件因为是同哈希函数转出来的然后对这个值取模一系列操作都一样只不过是放到了不同的文件中虽然文件不同但编号相同。 近似算法把一个文件放到布隆过滤器里面再通过另一个文件来看数据在不在在就是交集不在则不是。 2. 如何扩展BloomFilter使得它支持删除元素的操作 布隆过滤器一般不支持删除如果有共同映射的地方则会影响其它值。我们在这里可以使用引用计数用多个位表示一个位置做计数就可以支持删除但是布隆为了支持删除空间消耗更多优势就削弱了 删除百度 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 与上题条件相同如何找到top K的IP
