✨个人主页： 北 海
🎉所属专栏： C++修行之路
🎃操作环境： Visual Studio 2022 版本 17.6.5
文章目录
- 🌇前言
- 🏙️正文
- 1、字符串比较
- 2、布隆过滤器的概念
- 3、布隆过滤器的实现
- 3.1、基本结构
- 3.2、插入
- 3.3、查找
- 3.4、删除
- 3.5、测试
- 3.6、优化方案
- 4、布隆过滤器小结
- 5、海量数据面试题（哈希切割）
- 5.1、题目一
- 5.2、题目二
- 🌆总结
🌇前言
注册账号是进行网络冲浪的第一步操作，而拥有一个具有个性且独一无二的用户昵称是非常重要的，很多人在填写昵称时，常常会看到 此昵称已存在 的提示，系统是如何快速知道当前昵称是否存在呢？总不能挨个去遍历对比吧，这时候就需要我们本文中的主角： 布隆过滤器
🏙️正文
1、字符串比较
常见的字符串比较方法是 按 ASCII 码值进行比较，直到两个字符串同时结束，说明两者一致
比如字符串1 abcdef 和字符串2 azbmcy
显然两个字符串不一样
这种比较方法很直接，也很可靠，但缺点也很明显：需要对字符串进行遍历
一个字符串还好，如果是几千万个字符串呢？不但需要消耗大量存储空间，查找效率也很低，此时填写个昵称，服务器都要跑一会才有反映，这是用户所无法容忍的
因此人们想出了另一个方法，利用哈希映射 的思想，计算出 哈希值，存储这个值即可，可以借此 标识字符串是否存在
在进行字符串（昵称）比较时，只需要计算出对应的 哈希值，然后看看该位置是否存在即可
哈希值 也是一个整数啊，可以利用 位图 进行 设置，查找字符串时，本质上是在 查找哈希值是否在位图中存在
字符串有千万种组合，但字符是有限的，难免会出现 误判 的情况（此处的 哈希函数 为每个字符相加）
为了尽可能降低 误判率，在 位图 的基础之上设计出了 布隆过滤器
接下来看看什么是 布隆过滤器 吧
2、布隆过滤器的概念
这里是 布隆 可不是 英雄联盟中的 弗雷尔卓德之心 布隆，毕竟他也不能解决字符串比较问题，他只是 召唤师峡谷 中的一个坦克，主要负责 过滤（吸收） 敌方的伤害
布隆过滤器 是由 布隆（Burton Howard Bloom） 在 1970 年提出的一种 紧凑型的、比较巧妙 的 概率型数据结构，特点是 高效地插入和查询
布隆过滤器 的核心在于通过添加 哈希函数 来 降低误判率
举个例子，如果每个人的名字都只有一个字，那么肯定存在很多重名的情况，但如果把名字字数增多，重复的情况就会大大缓解
所以 布隆过滤器 其实很简单，无非就是映射字符串时，多安排几个不一样的 哈希函数，多映射几个 比特位，只有当每个 比特位 的为 1 时，才能验证这个字符串是存在的
3、布隆过滤器的实现
3.1、基本结构
布隆过滤器 离不开 位图，此时可以搬出之前实现过的 位图结构
既然需要增加 哈希函数，我们可以在模板中添加三个 哈希函数 的模板参数以及待存储的数据类型 K
namespace Yohifo { template class BloomFilter { public: //…… private: Yohifo::bitset _bits; //位图结构 }; }显然，这三个 哈希函数 的选择是十分重要的，我们在这里提供三种较为优秀的 哈希函数（字符串哈希算法），分别是 BKDRHash、APHash 以及 DJBHash
函数原型如下（写成 仿函数 的形式，方便传参与调用）：
struct BKDRHash { size_t operator()(const std::string& str) { size_t hash = 0; for (auto e : str) { hash = hash * 131 + (size_t)e; } return hash; } }; struct APHash { size_t operator()(const std::string& str) { size_t hash = 0; for (auto e : str) { if (((size_t)e & 1) == 0) { hash ^= ((hash > 3)); } else { hash ^= (~((hash > 5))); } } return hash; } }; struct DJBHash { size_t operator()(const std::string& str) { if (str.empty()) return 0; size_t hash = 5381; for (auto e : str) { hash += (hash size_t HashI1 = Hash1()(key) % N; //% N 是为了避免计算出的哈希值过大 _bits.set(HashI1); size_t HashI2 = Hash2()(key) % N; _bits.set(HashI2); size_t HashI3 = Hash3()(key) % N; _bits.set(HashI3); } //过滤不存在的情况，至于是否存在，还得进一步判断 size_t HashI1 = Hash1()(key) % N; if (_bits.test(HashI1) == false) return false; size_t HashI2 = Hash2()(key) % N; if (_bits.test(HashI2) == false) return false; size_t HashI3 = Hash3()(key) % N; if (_bits.test(HashI3) == false) return false; //经过层层过滤后，判断字符串可能存在 return true; } BloomFilter //测试误判率 //构建一组字符串 + 一组相似字符串 + 一组完全不同字符串 //通过 test 测试误判率 const size_t N = 100000; //字符串数 std::string str = "https://blog.csdn.net/weixin_61437787?spm=1000.2115.3001.5343"; //构建原生基本的字符串 std::vector std::string url = str + std::to_string(i); vsStr[i] = url; //保存起来，后续要用 } //构建相似的字符串 std::vector std::string url = str + std::to_string(i * -1); vsSimilarStr[i] = url; bfSimilarStr.set(url); } //构建完全不一样的字符串 str = "https://leetcode.cn/problemset/all/"; std::vector std::string url = str + std::to_string(i); vsDiffStr[i] = url; bfDiffStr.set(url); } //误判率检测：原生 if (bfSimilarStr.test(e) == true) missVal++; } //误判率检测：原生 if (bfDiffStr.test(e) == true) diffVal++; } std::cout static const int _len = 6; //布隆过滤器的长度 static const int _size = N * _len; //位图的大小 public: void set(const K& key) { size_t HashI1 = Hash1()(key) % _size; //% N 是为了避免计算出的哈希值过大 _bits.set(HashI1); size_t HashI2 = Hash2()(key) % _size; _bits.set(HashI2); size_t HashI3 = Hash3()(key) % _size; _bits.set(HashI3); } bool test(const K& key) { //过滤不存在的情况，至于是否存在，还得进一步判断 size_t HashI1 = Hash1()(key) % _size; if (_bits.test(HashI1) == false) return false; size_t HashI2 = Hash2()(key) % _size; if (_bits.test(HashI2) == false) return false; size_t HashI3 = Hash3()(key) % _size; if (_bits.test(HashI3) == false) return false; //经过层层过滤后，判断字符串可能存在 return true; } private: Yohifo::bitset
