苏州网站建设 网络推广公司,番禺网站开发企业,北京网站建设哪家好,关于建设网站的报告✨个人主页#xff1a; 北 海 #x1f389;所属专栏#xff1a; C修行之路 #x1f383;操作环境#xff1a; Visual Studio 2022 版本 17.6.5 文章目录 #x1f307;前言#x1f3d9;️正文1、字符串比较2、布隆过滤器的概念3、布隆过滤器的实现3.1、基本结构3.2、插入… ✨个人主页 北 海 所属专栏 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
{templatesize_t N,class K,class Hash1,class Hash2,class Hash3class BloomFilter{public://……private:Yohifo::bitsetN _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 7) ^ (size_t)e ^ (hash 3));}else{hash ^ (~((hash 11) ^ (size_t)e ^ (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 5) (size_t)e;}return hash;}
};因为 布隆过滤器 中最常存储的数据类型是 字符串并且三个 哈希函数 我们也已经有了所以可以将 布隆过滤器 中模板添加上 缺省值
templatesize_t N,class K std::string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHash如何创建一个布隆过滤器
BloomFilter100 bf; //最大值为 100 的布隆过滤器3.2、插入
插入 无非就是利用三个 哈希函数 计算出三个不同的 哈希值然后利用 位图 分别进行 设置 就好了
void set(K key)
{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);
}注意 布隆过滤器的插入操作是一定会成功的因为不管是什么字符串都可以在其对应的位置留下痕迹
3.3、查找
查找 某个字符串时需要判断它的每个 哈希值 是否都存在如果有一个不存在那么这个字符串必然是不存在的 bool test(const K key){//过滤不存在的情况至于是否存在还得进一步判断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;}查找 函数可以很好的体现 过滤 的特性 如何判断一个人是否存在 不能盲目去查找而是应该根据姓名查询身份证号、住址等个人信息如果这些信息都没有那么就说明这个人不存在因为这些信息足够过滤出结果了如果出现重名或信息重复的情况则需要进一步判断这就是说明 通过过滤判断 “存在” 是不准确的但判断 “不存在” 是准确的 布隆过滤器判断 “不在” 是准确的判断 “在” 是不准确的
比如字符串1映射了 1、6、7 号位置字符串2映射了 2、4、5 号位置字符串3映射了 1、3、4 号位置虽然这三个字符串不会相互影响但如果此时字符串4映射的是 1、2、3 号位置会被误断为 存在理论上 字符串存储位置越密集误判率越高 所以对于一些敏感数据如果要判断是否存在不能只依靠 布隆过滤器而是使用 布隆过滤器 数据库 的方式进行双重验证
当然如果 布隆过滤器 判断字符串不存在那么就是真的不存在因为这是绝对准确的
布隆过滤器 能容忍误判的场景注册时判断昵称是否存在
3.4、删除
一般的 布隆过滤器 不支持删除一旦进行了删除重置会影响其他字符串 表面上只删除了 “腾讯”但实际上影响了 “百度”在验证 “百度” 是否存在时会被判断为 不存在此时只有三个字符串如果有更多呢造成的影响是很大的所以对于一般的 布隆过滤器是不支持删除操作的
如何让布隆过滤器支持删除 关于共用同一份资源这个问题我们以前就已经见过了比如 命名管道当我们试图多次打开同一个 命名管道 时操作系统实际上并不会打开多次因为这样是很影响效率的实际每打开一次 命名管道其中的 计数器当关闭 命名管道 时计数器--直到 计数器 为 0 时命名管道 才会被真正关闭
这不就是 引用计数 的思想吗
我们可以给每一个 比特位 带上一个 引用计数器用来表示当前位置存在几个映射关系这样 布隆过滤器 就能支持 删除 操作了
但这未免也太本末倒置了位图 的优点是 高效且空间利用率高如果给每一个 比特位 都挂上一个 引用计数器会导致 位图 占用的内存资源膨胀浪费很多不必要的空间并且 删除 操作需求不大没必要添加
3.5、测试
接下来测试一下 布隆过滤器 是否有用
void TestBloomFilter1()
{BloomFilter100 bf; //最大值为 100 的布隆过滤器bf.set(aaaaa);bf.set(bbbbb);bf.set(ccccc);bf.set(ddddd);bf.set(eeeee);std::cout bbbbb: bf.test(bbbbb) std::endl;std::cout ddddd: bf.test(ddddd) std::endl;std::cout std::endl;std::cout aaaa: bf.test(aaaa) std::endl; //相似字符串std::cout CCCCC: bf.test(CCCCC) std::endl;std::cout zzzzz: bf.test(zzzzz) std::endl; //不相似字符串std::cout wwwww: bf.test(wwwww) std::endl;
}可以正确进行判断接下来看看 设置 的每个字符串的 哈希值 是多少 同时在三个 哈希值 的叠加下误判 的概率被大大降低了尽管如此在判断字符串存在时仍然存在较高的 误判率可以通过下面的程序计算 误判率
测试方法插入约 10 w 个字符串原生对原字符串进行微调后插入近似最后插入等量的完全不相同的字符串不同分别看看 原生 与 近似原生 与 不同 字符串之间的误判率
void TestBloomFilter2()
{//测试误判率//构建一组字符串 一组相似字符串 一组完全不同字符串//通过 test 测试误判率const size_t N 100000; //字符串数std::string str https://blog.csdn.net/weixin_61437787?spm1000.2115.3001.5343;//构建原生基本的字符串std::vectorstd::string vsStr(N);for (size_t i 0; i N; i){std::string url str std::to_string(i);vsStr[i] url; //保存起来后续要用}//构建相似的字符串std::vectorstd::string vsSimilarStr(N);BloomFilterN bfSimilarStr;for (size_t i 0; i N; i){std::string url str std::to_string(i * -1);vsSimilarStr[i] url;bfSimilarStr.set(url);}//构建完全不一样的字符串str https://leetcode.cn/problemset/all/;std::vectorstd::string vsDiffStr(N);BloomFilterN bfDiffStr;for (size_t i 0; i N; i){std::string url str std::to_string(i);vsDiffStr[i] url;bfDiffStr.set(url);}//误判率检测原生 --- 近似double missVal 0;for (auto e : vsStr){if (bfSimilarStr.test(e) true)missVal;}//误判率检测原生 --- 不同double diffVal 0;for (auto e : vsStr){if (bfDiffStr.test(e) true)diffVal;}std::cout 原生 --- 近似 误判率 missVal / N * 100 % std::endl;std::cout 原生 --- 不同 误判率 diffVal / N * 100 % std::endl;
}显然此时存在很高的误判率
3.6、优化方案
可以从两个方面进行优化
增加哈希函数的个数不是很推荐扩大布隆过滤器的长度使数据更分散
因此我们可以控制 布隆过滤器 的长度降低 误判率 如何理解空间扩大后误判率会降低 想想 地广人稀的西伯利亚 和 地狭人稠的香港人口越稠密找人时越有可能发生误判 那么如何选择 布隆过滤器 的长度做到 平衡误判率与空间占用呢
《详解布隆过滤器的原理使用场景和注意事项》 经过计算得出长度为 3~8 时效果最好
实际位图的大小为 N * _len
对原来的 布隆过滤器 进行修改结合 误判率 与 空间选择较为折中的 6 作为 布隆过滤器 的长度
templatesize_t N,class K std::string,class Hash1 BKDRHash,class Hash2 APHash,class Hash3 DJBHash
class BloomFilter
{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_size _bits; //位图结构
};此时再来看看之前的测试 误判率降至 5% 左右
对于 用户登录时检测昵称是否存在 这件事上已经足够用了
如果想要最求更高的准度可以使用 布隆过滤器 数据库 双重验证 4、布隆过滤器小结
总的来说作为 哈希思想 的衍生品布隆过滤器 实现了字符串的 快速查找与极致的空间利用在需要判断字符串是否存在的场景中判断 “不在”是值得信赖的
优点
查找效率极高为 O(K)其中 K 表示哈希函数的个数哈希函数之间并没有直接关系方便进行硬件计算数据量很大时布隆过滤器可以表示全集可以利用多个布隆过滤器进行字符串的 交集、并集、差集运算在可以容忍误判率的场景中布隆过滤器优于其他数据结构布隆过滤器中存储的数据无法逆向复原具有一定的安全性
缺点
存在一定的误判性无法对元素本身进行操作仅能判断存在与否一般不支持删除功能采取计数删除的方案时可能存在 计数回绕 的问题
实际应用场景
注册时对于 昵称、用户名、手机号的验证减少磁盘 IO 或者网络请求因为一旦一个值必定不存在的话我们可以不用进行后续昂贵的查询请求
总之能被 布隆过滤器 拦截过滤下来的数据一定是不存在的 5、海量数据面试题哈希切割
5.1、题目一 给两个文件分别有 100 亿个 query我们只有 1 GB 内存如何找到两个文件交集分别给出 精确算法和近似算法 query 指 查询语句比如 网络请求、SQL 语句等假设一个 query 语句占 50 Byte单个文件中的 100 亿个 query 占 500 GB 的空间两个文件就是 1000 GB
下面来看看解法
近似解法借助布隆过滤器先存储其中一个文件的 query 语句这里给每个 query 语句分配 4 比特位100 亿个就占约 1 GB 的内存可以存下存储完毕后再从另一个文件读取 query 语句判断是否在 布隆过滤器 中“在” 的就是交集。因为 布隆过滤器 判断 “在” 不准确符合题目要求的 近似算法
精确解法对于这种海量数据需要用到哈希分割我们这里把单个文件500 GB 数据分割成 1000 个小文件平均每个文件大小为 512 Mb再将小文件读取到内存中另一个文件也是如此读取两个大文件中的小文件后可以进行交集查找再将所有小文件中的交集统计起来就是题目所求的交集了 此时存在一个问题如果我们是直接平均等分成 1000 个小文件的话我们也不知道小文件中相似的 query 语句位置是能把每个小文件都进行匹配对比这样未免为太慢了
所以不能直接平均等分需要使用 哈希分割 进行切分
i HashFunc(query) % 1000
不同的 query 会得到不同的下标 i这个下标 i 决定着这条 query 语句会被存入哪个小文件中显然一样的 query 语句计算出一样的下标也就意味着它们会进入下标相同的小文件中经过 哈希切割 后只需要将 大文件 A 中的小文件 0 与 大文件 B 中的小文件 0 进行求 交集 的操作就行了这样能大大提高效率 但是此时存在一个 问题如果因哈希值一致而导致单个小文件很大呢
此时如果小文件变成了 1GB、2GB、3GB 甚至更大就无法被加载至内存中算法还有消耗
解决方法很简单借助不同的哈希函数再分割
即使在同一个小文件中不同的 query 语句经过不同的 哈希函数 计算后仍可错开怕的是 存在大量重复的 query此时 哈希函数 就无法 分割 了因为计算出的 哈希值 始终一致 所以面对小文件过大的问题目前有两条路可选
大多都是相同、重复的 query无法分割只能按照大小放到其他小文件中大多都是不相同的 query可以使用 哈希函数 再分割
这两条路都很好走关键在于如何选择 小文件中实际的情况我们是无法感知的但可以通过特殊手段得知探测
对于大于 512 Mb 的小文件我们可以对其进行读取判断属于情况1、还是情况2
首先准备一个 unorder_set目的很简单去重读取文件中的 query 语句存入 unordered_set 中如果小文件读取结束后没有发生异常情况说明属于情况1大多都是相同、重复的 query 语句把这些重复率高的数据打散放置其他 512 Mb 的小文件中如果小文件读取过程中出现了一个异常捕获结果为 bad_alloc说明读取到的大多都是不重复的 query 语句因为我们内存只有 1 GB抛出的异常是 内存爆了异常的抛出意味着这个小文件属于情况2可以使用其他的 哈希函数 对其进行再分割分成 512 Mb 的小文件
如此一来这个文件就被解决了核心在于利用哈希切割将数据分为有特性的小文件、利用抛异常得知小文件的实际情况
5.2、题目二 给一个超过 100 GB大小的 log file, log 中存着 IP 地址, 设计算法找到出现次数最多的 IP 地址 这题本质上也是在考 哈希分割将 log file 文件中的 IP 地址看作上一题中的 query 语句得知文件大小约为 500 GB
因为这里没有内存限制我们可以将其分为 500 个小文件每个小文件大小为 1 GB 这里分为小文件的目的是 让相同的 IP 分至同一个小文件中
针对较大的小文件依然采取 其他哈希函数继续分割 或 分给其他小文件的做法
读取单个小文件时利用 unordered_map 统计 IP 地址的出现次数读取完毕后遍历 unordered_map 即可得知出现次数最多的 IP 地址 与上题条件相同如何找到 Top K 的 IP 如何直接用 Linux 系统命令实现 涉及 Top K 的问题都可以通过 优先级队列堆 解决在第一问的基础上构建一个大小为 K 的 小堆将高频出现的 IP 地址入堆筛选出 Top K 个 IP 即可
至于如何利用 Linux 命令解决
sort log_file | uniq -c | sort -nrk1,1 | head -K解释
sort log_file 表示对 log_file 文件进行排序uniq -c 表示统计出其中每个 IP 的出现次数sort -nrk1,1 表示按照每个 IP 的出现次数再进行排序head -k 表示选择前 k 个 IP 地址显示
注意 以上操作都需要借助管道 | 因为它们都是有关联性的 总结
以上就是本次关于 C 哈希的应用【布隆过滤器】的全部内容了在本文中我们主要学习了布隆过滤器的相关知识再一次对哈希思想有了更深层次的理解多组映射在简单模拟实现布隆过滤器之后顺便解决了几道海量数据面试题从中学到了哈希分割这一重要思想哈希是一个被高频使用的工具因为它实在是太香了想要玩的更溜还需要勤加练习 相关文章推荐 C 进阶知识 C 哈希的应用【位图】 C【哈希表的完善及封装】 C【哈希表的模拟实现】 C【初识哈希】 C【一棵红黑树封装 set 和 map】
