文章目录
- 1.布隆过滤器
- 1.1.布隆过滤器的基本概念
- 1.2.代码实现
- 1.3.测试代码分析误判率
- 1.4.布隆过滤器的优点
- 1.5.关于几道面试题
关于位图：往期分析的 博客链接
1.布隆过滤器
1.1.布隆过滤器的基本概念
布隆过滤器的引出
位图使用1个比特位 + 直接定址法，来存储整数，但是如果用位图来存放字符串甚至是对象，那么它就无法胜任！假设下面的两个字符串通过计算映射到相同的位置，这里是两个字符串还好，万一是很多的字符串都冲突，这样位图就处理不了。
这时候可以使用布隆过滤器，布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，可以用来告诉你"某样东西一定不存在或者可能存在"，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
要完全的避免冲突，导致误判是行不通的，布隆过滤器是要降低误判。
通过多个哈希函数进行映射，这样如一个冲突没有关系，要三个位置都冲突才是真正的冲突，这样能降低冲突，减少误判。
1.2.代码实现
代码实现
关于字符串哈希算法：博客链接
关于布隆过滤器删除的问题
一般而言布隆过滤器不支持删除，可以定期的更新布隆过滤器。当然也有布隆过滤器是支持删除的。博客链接
关于查找时，在和不在的问题
什么意思呢，当一个位置为0说明还没有字符串，说明该字符一定不在（该位置都为空了，那肯定是没有）！当一个位置为1说明还有字符串，说明字符串是可能存放！这样我们在判断字符串在或不在的时候一旦发现一个位置上有0（添加的时候我们通过哈希计算将其位置设置成1，查找的时候也是通过相同的哈希计算找到相同的位置），肯定该字符串不存在。
完整实现代码
#pragma once
#include<iostream>
#include<bitset>
namespace xiYan
{
struct BKDRHash
{
size_t operator()(const std::string& str)
{
size_t hash = 0;
for (auto 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));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash
{
size_t operator()(const std::string& str)
{
size_t hash = 5381;
for (auto ch : str)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<
size_t N,
class K = std::string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash
>
class BlommFilter
{
public:
void set(const K& key)
{
size_t hash1 = Hash1()(key) % N;
_bs.set(hash1);
size_t hash2 = Hash2()(key) % N;
_bs.set(hash2);
size_t hash3 = Hash3()(key) % N;
_bs.set(hash3);
}
bool test(const K& key)
{
size_t hash1 = Hash1()(key) % N;
if (_bs.test(hash1) == false) return false;
size_t hash2 = Hash2()(key) % N;
if (_bs.test(hash2) == false) return false;
size_t hash3 = Hash3()(key) % N;
if (_bs.test(hash3) == false) return false;
return true;
}
private:
std::bitset<N> _bs;
};
}
1.3.测试代码分析误判率
布隆过滤器应该开多大空间，哈希函数应该用多少个
参考博客链接
误判率和哈希函数个数、布隆过滤器长度、n 为插入的元素个数关系
k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误判率
关于布隆过滤器应该开多大空间，哈希函数应该用多少个的计算公式：
通过下面的测试可以看出，当布隆过滤器开辟的空间，越大误判率就越小，哈希个数越多也会降低误判率。
void TestBloomFilter()
{
srand(time(0));
const size_t N = 100000;
xiYan::BloomFilter<N * 8> bf;
std::vector<std::string> v1;
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 = "select * from student";
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;
}
1.4.布隆过滤器的优点
-
布隆过滤器可以降低服务器的负载，比如：注册游戏时判断用户名时候存在，就可以套一层布隆过滤器。如果用户名不存在，布隆过滤器可以肯定地判断不存在。如果用户名存在，为了精确地查找再去查找数据库。这减少服务器地IO查询。
-
增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
-
哈希函数相互之间没有关系，方便硬件并行运算
-
布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
-
在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
-
数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
-
使用同一组散列函数的布隆过滤器可以进行交、并、差运算
1.5.关于几道面试题
如何扩展BloomFilter使得它支持删除元素的操作
多标记一个值用于，计数删除。
给两个文件，分别有100亿个query（数据库的查询SQL），我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
近似算法：将文件A和文件B数据分别存放在两个过滤器中（有过滤的功能），通过两个过滤器求交集。和位图求交集的思路相似。
精确算法：
通过哈希切割（i = Hash(query) % 1000（这里假设切成1000份）），分别对文件A和文件B切分到不同的文件。通过哈希切割相同和冲突的数据会对应下标的文件下。由于哈希切割不是等分切割，如果有大量重复或冲突的的数据，会落入到相同的下标的文件中导致小文件也是过大的。就会有两种情况，经过切分后一个文件有5G有两种情况；情况1.假设有4G是相同的1G是冲突的，情况2.大部分冲突的
解决方法：
把切分的i下标的query读取到一个set中，如果set的inset抛异常（bad_alloc），说明数据大部分是冲突的，更换哈希函数，经行二次切分。如果没有抛异常，说明数据中有大量相同的query那么set是去重的自然就能inset，成功操作。
然后A小文件和B小文件对应求交集，然后合并。
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址
就行哈希切割，相同的和冲突的IP都落入对应的下标文件中，然后使用map统计次数，在对每个小文件中最多的进行比较。
