【数据结构与算法】布隆过滤器
【数据结构与算法】布隆过滤器
🥕个人主页：开敲🍉
🔥所属专栏：数据结构与算法🍅
🌼文章目录🌼
1. 布隆过滤器
1.1 什么是布隆过滤器
有一些场景下面，有大量数据需要判断是否存在，但是这些数据并不是整型，因此位图就无法使用，使用红黑树 / 哈希表等内存空间可能不够。在这种场景下面就需要使用布隆过滤器来解决。
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效的插入和查询，可以用来告诉你 "某样东西一定不存在或者可能存在"，它是用多个哈希函数，将一个数据映射到位图结构中。这种方式不仅可以提高效率，还极大地节省了空间。
布隆过滤器的思路就是把key先映射转成哈希整型值，通过多个哈希函数映射到多个位上，如果只映射一个位的话，冲突率会比较高，映射多个位可以一定程度上降低冲突率。
布隆过滤器这里跟哈希表不⼀样，它无法解决哈希冲突的，因为他压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的，判断⼀个值key不在是准确的。
1.2 布隆过滤器误判率推导
推导过程：
2. 布隆过滤器代码实现
参考代码
struct HashFuncBKDR
{
/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
// ⼀书被展⽰⽽得 名，是⼀种简单快捷的hash算法，也是Java⽬前采⽤的字符串的Hash算法累乘因⼦为31。
size_t operator()(const string& str)
{
size_t ret = 0;
for (auto ch : str)
{
ret *= 13;
ret += ch;
}
return ret;
}
};
struct HashFuncAP
{
// 由Arash Partow发明的⼀种hash算法。
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 HashFuncDJB
{// 由Daniel J. Bernstein教授发明的⼀种hash算法。
size_t operator()(const string & s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash = hash * 33 ^ ch;
}
return hash;
}
};
namespace gjk
{
template <size_t N
,size_t X = 5
,class K = string
,class hash1 = HashFuncBKDR
,class hash2 = HashFuncAP
,class hash3 = HashFuncDJB
>
class BloomFilter
{
public:
void Insert(const K& val)
{
int ret1 = hash1()(val) % M;
int ret2 = hash2()(val) % M;
int ret3 = hash3()(val) % M;
_bm.Insert(ret1);
_bm.Insert(ret2);
_bm.Insert(ret3);
}
bool Find(const string& val)
{
int ret1 = hash1()(val) % M;
if (!_bm.Find(ret1)) return false;
int ret2 = hash2()(val) % M;
if (!_bm.Find(ret2)) return false;
int ret3 = hash3()(val) % M;
if (!_bm.Find(ret3)) return false;
return true;
}
// 获取公式计算出的误判率
double getFalseProbability()
{
double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
return p;
}
private:
static const size_t M = X * N;
gjk::BitMap<M> _bm;
};
}测试用例参考代码
void TestBloomFilter1()
{
string strs[] = { "百度","字节","腾讯" };
gjk::BloomFilter<10> bf;
for (auto& s : strs)
{
bf.Insert(s);
}
for (auto & s : strs)
{
cout << bf.Find(s) << endl;
}
for (auto & s : strs)
{
cout << bf.Find(s + 'a') << endl;
}
cout << bf.Find("摆渡") << endl;
cout << bf.Find("百渡") << endl;
cout << bf.Find("藤讯") << endl;
}
void TestBloomFilter2()
{
srand(time(0));
const size_t N = 10000000;
gjk::BloomFilter<N> bf;
//BloomFilter<N, 3> bf;
//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 = "https://www.baidu.com/s?ie=utf-8 & f = 8 & rsv_bp = 1 & rsv_idx = 1 & tn = 65081411_1_oem_dg & wd = ln2 & fenlei = 256 & rsv_pq = 0x8d9962630072789f & rsv_t = ceda1rulSdBxDLjBdX4484KaopD % 2BzBFgV1uZn4271RV0PonRFJm0i5xAJ % 2FDo & rqlang = en & rsv_enter = 1 & rsv_dl = ib & rsv_sug3 = 3 & rsv_sug1 = 2 & rsv_sug7 = 100 & rsv_sug2 =0 & rsv_btype = i & inputT = 330 & rsv_sug4 = 2535";
//std::string url = "猪⼋戒";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto & str : v1)
{
bf.Insert(str);
}
// v2跟v1是相似字符串集（前缀⼀样），但是后缀不⼀样
v1.clear();
for (size_t i = 0; i < N; ++i)
{
std::string urlstr = url;
urlstr += std::to_string(9999999 + i);
v1.push_back(urlstr);
}
size_t n2 = 0;
for (auto& str : v1)
{
if (bf.Find(str)) // 误判
{
++n2;
}
}
cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集 前缀后缀都不⼀样
v1.clear();
for(size_t i = 0; i < N; ++i)
{
//string url = "zhihu.com";
string url = "孙悟空";
url += std::to_string(i + rand());
v1.push_back(url);
}
size_t n3 = 0;
for (auto& str : v1)
{
if (bf.Find(str))
{
++n3;
}
}
cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}
int main()
{
//TestBloomFilter1();
TestBloomFilter2();
return 0;
}2.1 布隆过滤器删除问题
布隆过滤器是不支持删除的，因为比如 "猪八戒" 和 "孙悟空" 都映射在布隆过滤器中：
它们映射时有共同的映射位(冲突位)，如果我们把 "猪八戒" 删去，此时会把第 7 个位置置为 0。而当我们之后去找孙悟空时，会因为第 7 位为 0 ，而判定孙悟空不在，但是实际上孙悟空是在的。因为删除 "猪八戒" 而导致 "孙悟空" 间接的被删去了。
解决方案：可以考虑计数标记的方式，一个位置用多个位标记，记录映射这个位的计数值，删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果一个值不在布隆过滤器中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，一个确定存在的值，可能会变成不存在，这里就很坑。当然也有人提出，我们可以考虑计数方式支持删除。还有人提出可以定期重建⼀下布隆过滤器，这样也是一种思路。
3. 布隆过滤器的应用
首先我们分析一下布隆过滤器的优缺点：
优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤
缺点：存在误判(在是不准确的，不在是准确的)，不好支持删除
布隆过滤器在实际中的⼀些应用：
① 爬虫系统中的 URL 去重：
在爬虫系统中，为了避免爬取相同的 URL，可以使用布隆过滤器进行 URL 去重。爬取到的URL可以通过布隆过滤器进行判断，已经存在的URL则可以直接忽略，避免重复的网络请求和数据处理。
② 垃圾邮件过滤：
在垃圾邮件过滤系统中，布隆过滤器可以用来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从而提高过滤的效率。
③ 预防缓存穿透：
在分布式缓存系统中，布隆过滤器可以用来解决缓存穿透的问题。缓存穿透是指恶意用户请求一个不存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的无效查询。
④ 对数据库查询提效：
在数据库中，布隆过滤器可以用来加速查询操作。例如：一个app要快速判断⼀个电话号码是否注册过，可以使用布隆过滤器来判断⼀个用户电话号码是否存在于表中，如果不存在，可以直接返回不存在，避免对数据库进行无用的查询操作。如果在，再去数据库查询进行二次确认。
创作不易，点个赞呗，蟹蟹啦~
原文地址：https://blog.csdn.net/2301_78022459/article/details/143880695
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！