我要评论目录
一、概念
原理分析：
我们来进行分析，为什么不存在是一定的，而存在是可能的，以及为什么要这样做。
首先来解释为什么要用多个哈希函数。
我们知道，字符串可以通过哈希函数转换成整数，但是哈希冲突是避免不了的，可能存在多个字符串通过哈希函数都得到了一样的整数，所以，为了尽量的减少哈希冲突，可以使用多个哈希函数，让字符串通过多个哈希函数得到多个映射位置，只要不是多个映射位置都相同，就不会冲突，这样大大提高了效率。至于要用几个哈希函数是适合的。
这里有一份研究：（转载详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)）
其中误报率就是哈希冲突率
其中k、m、n满足：
其中k、m、p满足：
我们可以发现，哈希函数用的越多，哈希冲突率就越低，但是哈希函数到3之后，误报率已经很低了，其次，当哈希函数、插入元素固定，所开空间越大，误报率也越低。
用一张图来表示通过哈希函数映射到位图中：
那么综上，即使采用了多个哈希函数，也依然可能会存在哈希冲突，所以在判断东西在不在时，若返回的是存在，这有可能是误判，说明映射的位置依然可能完全相同，而不存在时，说明映射的位置不完全相同，这是正确的结果，为了确保冲突率，我们在模拟实现的时候就采用3个哈希函数。
二、模拟实现
#include "mybitset.h"//在上一篇章已实现
struct bkdrhash
{
size_t operator()(const string& key)
{
size_t hash = 0;
for (auto e : key)
{
//bkdr
hash *= 31;
hash += e;
}
return hash;
}
};
struct aphash
{
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;
}
};
struct djhash
{
size_t operator()(const string& key)
{
register size_t hash = 5381;
for(auto e : key)
{
hash += (hash << 5) + e;
}
return hash;
}
};
namespace bit
{
template<size_t n,
class k = string, //默认输入的是字符串
class hashfunc1 = bkdrhash,
class hashfunc2 = aphash,
class hashfunc3 = djhash>
class bloomfilter
{
public:
void set(const k& key)
{
//获取三个映射位置
int hash1 = hashfunc1()(key) % n;
int hash2 = hashfunc2()(key) % n;
int hash3 = hashfunc3()(key) % n;
_blf.set(hash1);
_blf.set(hash2);
_blf.set(hash3);
}
bool test(const k& key)
{
//key不存在是准确的。
int hash1 = hashfunc1()(key) % n;
if (_blf.test(hash1) == false)
return false;
int hash2 = hashfunc2()(key) % n;
if (_blf.test(hash2) == false)
return false;
int hash3 = hashfunc3()(key) % n;
if (_blf.test(hash3) == false)
return false;
//key存在可能有误判
return true;
}
private:
bitset<n> _blf;
};
}
void testbf1()
{
bit::bloomfilter<100> bf;
bf.set("猪八戒");
bf.set("沙悟净");
bf.set("孙悟空");
bf.set("二郎神");
cout << bf.test("猪八戒") << endl;
cout << bf.test("沙悟净") << endl;
cout << bf.test("孙悟空") << endl;
cout << bf.test("二郎神") << endl;
cout << bf.test("二郎神1") << endl;
cout << bf.test("二郎神2") << endl;
cout << bf.test("二郎神 ") << endl;
cout << bf.test("太白晶星") << endl;
}
void testbf2()
{
srand(time(0));
const size_t n = 100000;
bit::bloomfilter<n * 10> bf;
std::vector<std::string> v1;
//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
std::string url = "猪八戒";
for (size_t i = 0; i < n; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
// v2跟v1是相似字符串集（前缀一样），但是不一样
std::vector<std::string> v2;
for (size_t i = 0; i < n; ++i)
{
std::string urlstr = url;
urlstr += std::to_string(9999999 + i);
v2.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str)) // 误判
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)n << endl;
// 不相似字符串集
std::vector<std::string> v3;
for (size_t i = 0; i < n; ++i)
{
//string url = "zhihu.com";
string url = "孙悟空";
url += std::to_string(i + rand());
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)n << endl;
}测试：
#include <string>
#include "mybloomfilter.h"
int main()
{
testbf2();
return 0;
}输出结果：
三、布隆过滤器扩展应用
1.给两个文件，分别由100亿个字符串，只有1g内存，如何找到两个文件交集？
假设每个字符串占50个字节，那么100亿就是5000字节，约等于500g，内存肯定存不下，此时可以采用哈希切分。如图：
2.给一个超过100g大小的log file，log中存着ip地址，设计算法找到出现次数最多的ip地址？
与第一题类似，先进行哈希切分，然后通过map统计每个小文件中ip地址出现的次数进行比较即可。
发表评论