我们在上一节中学习了 位图,知道了位图可以用来快速判断某个数据是否在一个集合中,但是位图有如下的缺点:
其中位图只能针对整形这一缺陷我们可以想办法解决,其中最常见的方法就是针对某一种特定类型定义一个 HashFunc 函数,将其转化为整形;比如当数据是 string 类型时,我们可以使用字符串哈希算法将字符串转化为整形,然后再将这个整形映射到位图中;
但是这种方法存在一种很大的缺陷 – 不同的字符串通过同一个 HashFunc 函数转换出来的值可能是一样的,也就是说,可能会发生误判 (哈希冲突),在这种情况下:
同时,由于通过字符串哈希函数转换出来的值的范围是不确定的,所以我们通常会对结果进行取模,以此来节省空间,但是取模又会增加哈希冲突的概率,因为不同的整形取模后得到结果可能是一样的。
那么我们如何降低误判率呢?此时布隆过滤器就登场了。
布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,其特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
可以看到,布隆过滤器通过使用多个哈希函数的方法来降低误判率,即让同一个元素映射多个下标位置,在查询时只有当这些位置都为1时才表示该元素存在,而同一元素通过不同哈希函数映射出的不同下标同时被误判的概率肯定是比一个下标位置被误判的概率要低很多的。[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WrhcapPx-1681382089012)(https://picgo-tian1.oss-cn-beijing.aliyuncs.com/img/202304120044727.png)]
特别注意:布隆过滤器只能降低误判率,而不能彻底消除误判。
那么是不是映射的下标位置越多越好呢?当然不是,因为一个元素映射的下标位置越多,那么浪费的空间也就越多;所以有的大佬就针对如何选择哈希函数个数和布隆过滤器长度专门写了一篇博客,大家可以参考参考:详解布隆过滤器的原理,使用场景和注意事项 - 知乎 (zhihu.com)
其博客中给出了哈希长度、布隆过滤器长度、插入元素个数与误判率的关系图:
以及它们之间的关系式:
对上面的K取值进行带入可得:
结合关系图和关系表达式可以看出,哈希函数的个数取 3~5 个是比较合适的,取8的话空间消耗有点大,但是忍忍其实也能接受。
布隆过滤器的实现其实很简单,位图直接使用库中的 bitset 即可,字符串哈希算法可以从下面这篇博客介绍的算法里面挑选几个得分比较高的:各种字符串Hash函数 - clq - 博客园 (cnblogs.com);
代码实现如下:
#pragma once
#include <bitset>
#include <string>
using std::bitset;
using std::string;
struct BKDRHash {
size_t operator()(const string& s) {
size_t value = 0;
for (auto ch : s) {
value *= 131;
value += ch;
}
return value;
}
};
struct APHash {
size_t operator()(const string& s) {
size_t hash = 0;
for (size_t i = 0; i < s.size(); i++) {
if ((i & 1) == 0) {
hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
}
else {
hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
}
}
return hash;
}
};
struct DJBHash {
size_t operator()(const string& s) {
size_t hash = 5381;
for (auto ch : s) {
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N, //数据范围
size_t X = 5, //每个元素最多消耗的比特位的位数
class K = string, //数据类型
class HashFunc1 = BKDRHash, //哈希函数
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter {
public:
void set(const K& key) {
size_t hash1 = HashFunc1()(key) % (N * X);
size_t hash2 = HashFunc2()(key) % (N * X);
size_t hash3 = HashFunc3()(key) % (N * X);
//将三个位置的比特位都置1才表示插入key
_bs.set(hash1);
_bs.set(hash2);
_bs.set(hash3);
}
bool test(const K& key) {
size_t hash1 = HashFunc1()(key) % (N * X);
size_t hash2 = HashFunc2()(key) % (N * X);
size_t hash3 = HashFunc3()(key) % (N * X);
//key映射的三个下标位置都为真才表示key可能存在
//也可能不存在,此时映射的位置全部冲突,从而发生误判
if (_bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3)) {
return true;
}
return false;
}
private:
bitset<N* X> _bs;
};
在我们上面的实现中,第一个模板参数N为数据的范围,第二个X为每一个数据最多占用多少个比特位,它与哈希函数的个数有关,由于我们实现的版本中默认使用的是三个哈希函数,所以X的缺省值为5,但我们也可以显示传递X的值来增加/减少哈希冲突的概率,最后三个模板参数分别为三个哈希函数,这里我们使用的字符串哈希算法分别为BKDRHash、APHash 和 DJBHash;对程序进行简单测试结果如下:
在上面的测试程序中,由于每次产生的数是随机的,所以测试结果有时会发生误判,有时不会发生误判。
现在我们加大测试用例,并分别构造相似字符串集和不相似字符串集来分别测试其误判率,测试代码如下:
void BloomFilter_test2()
{
srand(time(0));
const size_t N = 100000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https://coder-yzpq.blog.csdn.net/?type=blog";
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 url = "https://coder-yzpq.blog.csdn.net/?type=blog";
url += std::to_string(999999 + i);
v2.push_back(url);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str))
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// v3跟v1是不相似字符串集
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string url = "csdn.com";
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;
}
n == 10 万, k == 3, X == 5 时,测试结果如下:
n == 10 万, k == 3, X == 8 时,测试结果如下:
n == 10 万, k == 3, X == 12 时,测试结果如下:
n == 100万, k == 3, X == 12 时,测试结果如下:
从这些测试结果中可以看出,布隆过滤器虽然存在误判的情况,但其误判率是可控的 – 我们可以根据具体的应用场景来测试调整哈希函数的个数以及布隆过滤器的长度,最终实现出最符合当前应用场景的布隆过滤器。
布隆过滤器的删除:布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素;但是我们也可以使用计数的方式强行让其支持删除操作,即使用多个位图来标记某一个元素出现的次数,其思路和 位图 中查找出现一次或两次的元素的思路一样,不过这里还存在一个问题 – 我们不知道元素最多的出现次数为几,所以无法确定要使用几个位图来标记一个元素;所以如果不是在某些特殊场景下布隆过滤器是不支持删除操作的。
布隆过滤器适用于不需要完全准确,允许出现一定误判的场景,例如如下场景:
在实际开发中布隆过滤器的应用场景还有许多,比如网站黑名单的设计等;所以布隆过滤器在实际开发中是比较重要的,在面试时被考察的也比较多,大家需要理解它的原理,特别是布隆过滤器到底是在是正确的还是不在是准确的,大家必须要能够正确回答并且清晰阐释这个问题。
布隆过滤器的引出:
布隆过滤器的优点:
布隆过滤器的缺点:
最后,给出一道与布隆过滤器相关的面试题:给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法。
解析:这道题和上一节 位图 中求IP地址个数那道题一样,都是考察哈希切割 – 使用相同的哈希函数分别对这两个文件进行切割,切割结果为 A0 ~ Ai,B0 ~Bi,因为哈希函数相同,所以 Ai 和 Bi 中相同的 query 及发生冲突的 query 都在同一个小文件中,此时我们只需要分别求出 Ai 和 Bi 相同下标小文件中的交集即可,需要注意的是,如果小文件很大,说明某一个或某几个 query 有大量重复,此时换一个哈希函数再分别对 Ai 和 Bi 小文件递归子问题进行哈希切割即可;
对于精确算法来说,我们需要先将 Ai 号小文件中的元素全部存入 set/map 中,再依次取 Bi 号小文件中的数据到 set/map 中查询即可得到交集,注意结果需要去重;
对于近似算法来说,我们可以先将 Ai 号小文件中的元素全部映射到一个布隆过滤器中,然后再依次取 Bi 号小文件中的数据到布隆过滤器中查询即可得到交集,注意结果也需要去重。