本篇博文,旨在介绍一种可以快速检索元素是否存在的数据结构 --- 布隆过滤器;本文从位图和布隆过滤器的对比,讨论了使用这两种数据结构的不同情况;并介绍了布隆过滤器的几种主要使用场景
布隆过滤器的引入
之前学习了位图,可以快速的判断一个整数是否存在于一个集合中
然而,现实生活中我们用的很多是字符串,单用位图处理不了字符串,由此引来了位图
布隆过滤器的思想
学过了哈希表后我们知道字符串哈希算法,可以将字符串转换为一个key值,然后存入位图
但是,通过字符串哈希算法后,也很有可能会造成哈希冲突(多个字符串映射成同一个key值),这样误判率就会很高
布隆过滤器的实现
于是,布隆过滤器就是采用同时进行多个字符串哈希算法,进行映射;
假设我们用5个字符串哈希算法进行映射,那么在判断一个字符串是否存在时,只需判断对应的五个位是否同时存在即可
布隆过滤器的代码实现
- #pragma once
- #include<iostream>
- using namespace std;
- //包我们自己定义的位图头文件
- #include"BitMap.h"
- //定义五个字符串哈希算法
- template<class T>
- struct BKDRHash
- {
- size_t operator()(const T str)
- {
- register size_t hash = 0;
- for (size_t i = 0; i < str.size(); ++i)
- {
- hash = hash * 131 + str[i];
- }
- return hash;
- }
- };
- template<class T>
- struct SDBMHash
- {
- size_t operator()(const T str)
- {
- register size_t hash = 0;
- for (size_t i = 0; i < str.size(); ++i)
- {
- hash = 65599 * hash + str[i];
- }
- return hash;
- }
- };
- template<class T>
- struct RSHash
- {
- size_t operator()(const T str)
- {
- register size_t hash = 0;
- size_t magic = 63689;
- for (size_t i = 0; i < str.size(); ++i)
- {
- hash = hash * magic + str[i];
- magic *= 378551;
- }
- return hash;
- }
- };
- template<class T>
- struct APHash
- {
- size_t operator()(const T str)
- {
- register size_t hash = 0;
- for (long i = 0; i < str.size(); ++i)
- {
- if ((i & 1) == 0)
- {
- hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));
- }
- else
- {
- hash ^= (~((hash << 11) ^ str[i] ^ (hash >> 5)));
- }
- }
- return hash;
- }
- };
- template<class T>
- struct JSHash
- {
- size_t operator()(const T str)
- {
- if (str.empty())
- return 0;
- register size_t hash = 1315423911;
- for (size_t i = 0; i < str.size(); ++i)
- {
- hash ^= ((hash << 5) + str[i] + (hash >> 2));
- }
- return hash;
- }
- };
- //定义布隆过滤器,5个HashFunc是五种不同的字符串哈希算法,用来辅助实现布隆过滤器
- template<typename K = string,typename HashFunc1 = BKDRHash<K>,typename HashFunc2 = SDBMHash<K>,typename HashFunc3 = RSHash<K>,typename HashFunc4 = APHash<K>,typename HashFunc5 = JSHash<K>>
- class BoolmFilter
- {
- public:
- BoolmFilter(size_t num)
- :_bp(num*2*5)
- {}
- size_t HashFunC1(const K& num)
- {
- HashFunc1 hf;
- size_t index = hf(num);
- return index;
- }
- size_t HashFunC2(const K& num)
- {
- HashFunc2 hf;
- return hf(num);
- }
- size_t HashFunC3(const K& num)
- {
- HashFunc3 hf;
- return hf(num);
- }
- size_t HashFunC4(const K& num)
- {
- HashFunc4 hf;
- return hf(num);
- }
- size_t HashFunC5(const K& num)
- {
- HashFunc5 hf;
- return hf(num);
- }
- void Set(const K &num)
- {
- //用五中不同的字符串哈希算法求出五个不同的值
- size_t hf1 = HashFunC1(num);
- size_t hf2 = HashFunC2(num);
- size_t hf3 = HashFunC3(num);
- size_t hf4 = HashFunC4(num);
- size_t hf5 = HashFunC5(num);
- //测试五个哈希值
- //cout << hf1 << " " << hf2 << " " << hf3 << " " << hf4 << " " << hf5 << endl;
- //将五个值都放入位图中
- _bp.Set(hf1);
- _bp.Set(hf2);
- _bp.Set(hf3);
- _bp.Set(hf4);
- _bp.Set(hf5);
- }
- //Reset可以用引用计数来实现
- //void Reset();
- bool Find(K &num)
- {
- //分别判断num对应的五个值是否存在于位图中
- //若有一个不存在,则返回FALSE,num必定不存在
- //若都存在,则返回TRUE,但是不能确定一定存在
- int hf1 = HashFunC1(num);
- if(_bp.Find(hf1) == false)
- return false;
- int hf2 = HashFunC2(num);
- if (_bp.Find(hf2) == false)
- return false;
- int hf3 = HashFunC3(num);
- if (_bp.Find(hf3) == false)
- return false;
- int hf4 = HashFunC4(num);
- if (_bp.Find(hf4) == false)
- return false;
- int hf5 = HashFunC5(num);
- if (_bp.Find(hf5) == false)
- return false;
- return true;
- }
- protected:
- //定义位图 _bp;
- BitMap _bp;
- };
布隆过滤器和位图的对比
位图的优点:
可以快速的判断一个整数是否存在于集合中
位图的缺点:
就如同其优点中说的,只能判断整数,无法处理其他类型的数据
布隆过滤器的优点:
1、在位图的基础上利用哈希算法进行扩充,使之可以处理字符串类型的数据
2、时间复杂度O(k),【K表示字符串哈希算法的个数】,其效率远高于其他的算法
布隆过滤器的缺点:
由于哈希冲突,布隆过滤器有一定的误判性,如何使用适量的字符串哈希算法是需要考虑的问题
布隆过滤器的误区:
使用字符串哈希算法的数量越多越好?(错)
这里要说明,字符串哈希算法过多,就会导致一个字符串会占好多个位,冲突的概率还会增大
所以,要使用适量的字符串哈希算法
布隆过滤器的几种主要应用场景:
(2)在爬虫中,如何快速的判断一个网页是否爬过也是布隆过滤器的使用场合之一