【数据结构取经之路】布隆过滤器BloomFilter原理、误判率推导、代码实现

news/2024/9/16 7:31:56/ 标签: 数据结构, c++

目录

背景介绍 

简介

布隆过滤器的实现思路

布隆过滤器的作用

布隆过滤器误判率推导过程

布隆过滤器的实现

布隆过滤器的删除问题 

 布隆过滤器的优缺点

布隆过滤器的应用


背景介绍 

在一些场景下面,有大量数据需要判断是否存在,而这些数据不是整形,导致位图就派不上用场。这时,时代无比呼唤一种新的解决方案,布隆过滤器也就应运而生了。

简介

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(哈希函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好得多,缺点是有一定的误判率和删除困难。

布隆过滤器的实现思路

BloomFilter的实现思路就是把key通过哈希函数转换成整型后在映射一个二进制位。也就是说,BloomFilter = bitset(位图) + Hash函数。考虑到只映射一个位的话哈希冲突的概率较大,所以可以通过几个哈希函数转换出几个整型,然后映射多个二进制位,降低冲突率。

布隆过滤器的作用

布隆过滤器可以告诉我们“某样东西一定不存在或者可能存在”。换句话说,它判断一个值key在是不准确的,但是判断一个值key不在是准确的。下面对这句话做出解释。

判断一个值在是不准确的。原因在于布隆过滤器存在误判,也就是说不同的key映射的3个位置上都恰好与其他元素冲突,而且这些位置都被置为了1,返回结果就是在——这就是误判。

判断一个值不在是准确的。首先,导致返回结果为不存在有两种情况,第一:元素key本来就存在,但是由于误判,导致返回结果为不存在。第二:元素key本来就不存在,然后返回结果为不存在。针对第一种情况,因为布隆过滤器保证元素不被错误的删除,元素存在的话它映射的3个二进制位一定为1,所以这种情况不可能发生。只能是第二种情况,即只有不存在的值返回结果才是不存在,证明了判断一个值不在是准确的。

布隆过滤器误判率推导过程

数据量:n

误判率:p

bit数组的大小:m

哈希函数的个数:k

针对某个二进制位:

经过1次哈希函数映射后,不被置为1的概率:1 - \frac{1}{m}

经过k个哈希函数映射后该bit位仍未被置为1的概率:(1 - \frac{1}{m})^{k}(某一个二进制位被置为1后,后面还是有可能会再次映射到该位置,故总的二进制位数还是m)

该二进制位在插入n个值后依旧未被置为1的概率:(1 - \frac{1}{m})^{kn}

则某个二进制位在插入n个值后被置为1的概率:1 - (1 - \frac{1}{m})^{kn}

故误判的概率:(1 - (1 - \frac{1}{m})^{kn})^{k} ①

根据 lim(1 + \frac{1}{x})^{x}= e(x\rightarrow \Join ) 

①式可化为:(1 - (1 - \frac{1}{m})^{kn})^{k}=  (1 - (1 + \frac{1}{-m})^{-m\cdot \frac{kn}{-m}})^{k}= (1 - e^{-\frac{kn}{m}})^{k}

b= e^{\frac{n}{m}},则②式可化为:(1 - b^{-k})^{k}

误判率为k的函数,有 f(k)= (1 - b^{-k})^{k}

两边同时取对数,有 lnf(k)= kln(1 - b^{-k})

两边同时求导,有 \frac{1}{f(k)}\cdot {f(k)}'= ln(1 - b^{-k})+k\cdot \frac{1}{1-b^{-k}}\cdot b^{-k}\cdot lnb

f(k)取最值时,{f(k)}'= 0(最值点的导数为0,除了端点),则③式可化为: ln(1 - b^{-k})+k\cdot \frac{1}{1-b^{-k}}\cdot b^{-k}\cdot lnb= 0

下面对④式进行化简:

ln(1 - b^{-k})+k\cdot \frac{1}{1-b^{-k}}\cdot b^{-k}\cdot lnb= 0

(1 - b^{-k})ln(1 - b^{-k})+kb^{-k}lnb= 0(两边同时乘(1 - b^{-k})

(1 - b^{-k})ln(1 - b^{-k})= -kb^{-k}lnb(移项)

(1 - b^{-k})ln(1 - b^{-k})= b^{-k}lnb^{-k}(把-k移到lnb内)

观察等式两边的形式,可以得到 1 - b^{-k}= b^{-k}

从⑤式中,推出b^{-k}= \frac{1}{2}

在⑥式中,把b换成e^{\frac{n}{m}},有 e^{-\frac{n}{m}k}= \frac{1}{2}

两边同时取对数,推出最佳的哈希函数个数 k= ln2 \frac{m}{n}

根据上述描述,误判概率也可写成p= (1-b^{-k})^{k}

把⑥式代入⑦式,有p= 2^{-k}

上面已推出k= ln2 \frac{m}{n}p=2^{-ln2\frac{m}{n}}

两边同时取对数,有lnp=ln2^{-ln2\frac{m}{n}}

可化简为lnp={-ln2\frac{m}{n}}ln2

进一步化简lnp={-\frac{m}{n}}(ln2)^{2}

进而推出bit数组的大小m=-\frac{nlnp}{(ln2)^{2}}

\frac{}{}由误判率公式可知,在k⼀定的情况下,当n增加时,误判率增加,m增加时,误判率减少。

布隆过滤器的实现

经过上述大篇幅的推导,终于得于推出BloomFilter的误判率,接下来我们着手实现。

各种字符串Hash函数——这是一篇关于各种字符串Hash函数分析的博客,我们选出3个效率较好的来作为我们布隆过滤器的Hash函数。前面在BloomFilter的实现思路中提到,BloomFilter = bitset(位图) + Hash函数,我们的BloomFilter将基于标准库里的位图(当然,你也可以基于自己实现的位图)。

#pragma once
#include <bitset>
#include <string>
#include <iostream>//字符串Hash函数
struct HashFuncBKDR
{size_t operator()(const std::string& str){size_t hash = 0;for (auto ch : str){hash += hash * 31 + ch;}return hash;}
};//字符串Hash函数
struct HashFuncAP
{size_t operator()(const std::string& str){size_t hash = 0;for (size_t i = 0; i < str.size(); i++){if ((i & 1) == 0)hash ^= ((hash << 7) ^ (str[i]) ^ (hash >> 3));elsehash ^= (~((hash << 11) ^ (str[i]) ^ (hash >> 5)));}return hash;}
};//字符串Hash函数
struct HashFuncDJB
{size_t operator()(const std::string& str){size_t hash = 5381;for (auto ch : str){hash = hash * 33 ^ ch;}return hash;}
};template <size_t N,size_t X = 6,class K = std::string,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>class BloomFilter
{
public:void set(const K& key){size_t hash1 = HashFuncBKDR()(key) % M;size_t hash2 = HashFuncAP()(key) % M;size_t hash3 = HashFuncDJB()(key) % M;//映射多个位_bs->set(hash1);_bs->set(hash2);_bs->set(hash3);}bool test(const K& key){//有一个为0,则不存在size_t hash1 = HashFuncBKDR()(key) % M;if (_bs->test(hash1) == 0)return false;size_t hash2 = HashFuncAP()(key) % M;if (_bs->test(hash2) == 0)return false;size_t hash3 = HashFuncDJB()(key) % M;if (_bs->test(hash3) == 0)return false;return true;}
private:static const size_t M = X * N;std::bitset<M>* _bs = new std::bitset<M>;
};void TestBloomFilter()
{BloomFilter<10> bf;std::string arr[] = { "百度", "字节", "腾讯" };for (auto& str : arr){bf.set(str);}std::cout << bf.test("百度") << std::endl;std::cout << bf.test("摆度") << std::endl;std::cout << bf.test("摆渡") << std::endl;
}

布隆过滤器的删除问题 

先说结论,布隆过滤器默认是不支持删除的。下面我们来分析原因。

请看上图,我们发现,obj1和obj2都映射到了3号位上(哈希冲突),当我们删除obj1时,3号位会被置为0,导致我们再去查找obj2时会找不到,这就相当于间接的把obj2删除了。关于这个问题,有这样一个解决方案:引用计数!一个位置用多个位标记,记录映射这个位的计数值,删除时仅仅减减计数值。我们思考一下,这个方案能完美解决布隆过滤器不好删除的问题吗?这个问题不着急回答,我们先来看看下面的场景。

当我们删除一个值key时,本来key是不在布隆过滤器里的,但由于误判(假设其中冲突的一个位置为上图的4号位),结果认为是key在,然后我们删除它。此时, 4号位的计数值减减,由1减为了0,这样也间接删除了tencent。上述问题的答案就不言而喻了。还有人提出这样一种思路,支持计数方式删除,但是定期重建布隆过滤器。

 布隆过滤器的优缺点

优点:

1)空间效率高。

2)查询速度快。

3)保密性强。因为布隆过滤器不存储数据本身。

缺点:

1)存在误判。

2)删除困难。

布隆过滤器的应用

1)爬虫系统中的URL去重

在爬虫系统重,为了避免重复的爬取相同的URL,可以使用布隆过滤器来进行URL的去重。爬取到的URL可以通过布隆过滤器进行判断,已经存在的URL可以直接忽略,避免重复的网络请求和数据处理。

2)垃圾邮件过滤

在垃圾邮件过滤系统中,布隆过滤器可以用来判断邮件是否为垃圾邮件。系统可以将已知的垃圾邮件特征信息存储在布隆过滤器中,当新的邮件到达时,可以通过布隆过滤器快速判断是否为垃圾邮件,从而提高过滤的效率。

3)预防缓存穿透

在分布式缓存系统中,布隆过滤器可以用来解决缓存穿透的问题。缓存穿透是指恶意用户大量请求不存在的数据,导致请求直接访问数据库,造成数据库压力过大。布隆过滤器可以先判断请求的数据是否在布隆过滤器中,如果不在,直接返回不存在,避免对数据库的无效查询。

4)对数据库查询提效

在数据库中,布隆过滤器可以用来加速查询操作。例如:一个APP要快速判断一个电话号码是否注册过,可以用布隆过滤器来判断一个用户的电话号码是否存在,如果不存在,可以直接返回不存在,避免对数据库的无效查询。如果在,再去数据库进行二次确认。


本文到这就结束啦,感谢支持!


http://www.ppmy.cn/news/1520355.html

相关文章

redroid搭建云手机学习笔记(一)

参考链接 通过Redroid搭建自己的云手机 docker安装 docker官网目前打不开了&#xff0c;通过官网安装的方式无法实现&#xff0c;这里需要借助镜像网站来实现docker的安装 参考链接&#xff1a;https://developer.aliyun.com/mirror/docker-ce # step 1: 安装必要的一些系统…

AI写作保姆级方法论第六节-AI的终极调教心法(问题+解决方案)

效果是什么 大象基于大量的实战经验&#xff0c;总结出了AI prompt调教的终极杀手锏&#xff1a;【终极调教心法&#xff1a;1个原则和3个技巧】 一个原则&#xff0c;是指AI的【角色扮演法】&#xff0c;openai官方基于AI原理给出的让AI听话的技巧。所有AI的使用玩法&#xff…

力扣面试150 旋转链表 闭链成环

Problem: 61. 旋转链表 &#x1f468;‍&#x1f3eb; 力扣官解 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode nex…

LVS Keepalived nginx haproxy 区别

LVS、Keepalived、Nginx 和 HAProxy 都是常用的负载均衡和高可用性解决方案&#xff0c;但它们之间存在一些显著的区别。下面我将逐一介绍这些工具的特点和适用场景&#xff1a; 1. LVS (Linux Virtual Server) 定义&#xff1a; LVS 是一种 Linux 内核模块&#xff0c;用于实…

计算机毕业设计选题推荐-博客平台-博客系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…

设计模式——行为模式

注意&#xff0c;设计模式的实现并不唯一。 责任链模式 将请求顺序的传递给每一个接收者&#xff0c;直到有一个接收者做出处理。或者一个接收者处理之后继续传递给下一个接收者。 例如 QT 的信号机制。 与装饰器模式的不同&#xff1a; “责任链的管理者可以相互独立地执行…

Cornerstone3D Tools对影像进行交互(上篇)-基础交互工具及同步器

⛳️ 前言 在我们日常需求中&#xff0c;除了需要对影像进行可视化展示外&#xff0c;大多数场景下还需要对影像进行调整、注释、分割等操作。Cornerstone3DTools库则支持大多数需要的交互功能。CornerstoneTools支持的工具类型主要分为以下4类&#xff1a; 基础交互类工具&am…

k8s-pod 实战五 (Startup Probe 详细分析)

一、Startup Probe 详细分析 Startup Probe Startup Probe 用于检测容器是否完成启动。它的目的是取代 Liveness Probe,在容器启动时提供一个更长的检测时间窗口。Startup Probe 是为了处理启动时间较长的应用程序,避免在启动过程中因 Liveness Probe 失败而导致容器重启。…

【系统架构设计师-2021年】综合知识-答案及详解

【第1题】 某计算机系统页面大小为4K&#xff0c;进程P1的页面变换表如下图所示&#xff0c;看P1要访问数据的逻辑地址为十六进制1B1AH,那么该逻辑地址经过变换后,其对应的物理地址应为十六进制&#xff08; &#xff09;。 答案解析 本题考查页式存储中的逻辑地址转物理地…

力扣632.最小区间

力扣632.最小区间 贪心 最小堆 用一个小根堆维护K个数其中最小的算完结果后弹出&#xff0c;再补一个进去 class Solution {public:vector<int> smallestRange(vector<vector<int>>& nums) {int l0,rINT_MAX;int n nums.size();//记录下一个位置的下…

git服务搭建

纯git server 软件安装 环境:ubuntu16.0.4 安装Git-Core:sudo apt-get install python-setuptools 安装openssh-server和openssh-client:sudo apt-get install openssh-server openssh-client安装python tool:sudo apt-get install python-setuptools安装gitosis: git clon…

时间格式--cotroller传递时间参数

时间格式–cotroller传递时间参数 我们的前端控制器controller代码&#xff0c; package com.forge.controller;import com.forge.common.Result; import com.forge.entity.Doctor; import com.forge.service.TestService; import lombok.extern.slf4j.Slf4j; import org.spr…

Android使用addr2line分析Native Crash

NDK提供的工具将函数地址解析为具体的函数名和行数才能进一步分析问题。 常用的地址转换工具有addr2line、ndk-stack等&#xff0c;个人比较喜欢addr2line&#xff0c;所以接下来介绍下该工具的基本使用方式 日常使用过程中&#xff0c;只需要关注-C -f -e三个参数即可 // -…

浅析JVM invokedynamic指令和Java Lambda语法|得物技术

一、导语 尽管近年来JDK的版本发布愈发敏捷&#xff0c;当前最新版本号已经20&#xff0c;但是日常使用中&#xff0c;JDK8还是占据了统治地位。 你发任你发&#xff0c;我用Java8&#xff1a;【Jetbrains】2023 开发者生态系统现状 - https://www.jetbrains.com/zh-cn/lp/dev…

都2024年了你还缺客源?十分钟教你如何获取!

你是否还在为如何找到精准的客源而烦恼&#xff1f;别担心&#xff0c;今天我们就来分享一些客源采集方法&#xff0c;让你十分钟内掌握技巧&#xff0c;轻松获取全国各地各行各业的客源。 精准采集客源 1. 拓客工具 专业的拓客工具可以帮助你精准地采集到全国各地的客源信息。…

无人机之遥控器防水性能篇

无人机遥控器的防水性能是评估其耐用性和适应不同环境能力的重要指标。随着无人机技术的不断发展&#xff0c;越来越多的遥控器在设计时融入了防水元素&#xff0c;以满足用户在不同天气条件下的使用需求。以下是对无人机遥控器防水性能的详细探讨&#xff1a; 一、防水等级与…

Redis 入门到精通1

一、String&#xff08;字符串&#xff09; 特点&#xff1a; 最基本的数据类型&#xff0c;二进制安全&#xff0c;可以存储任何数据&#xff0c;比如图片或者序列化的对象。一个 key 对应一个 value。 常用命令及示例&#xff1a; SET key value&#xff1a;设置一个键值对。…

实战项目:俄罗斯方块(六)

文章目录 &#x1f34a;自我介绍&#x1f34a;图像界面绘制界面绘制界面显示代码运行结果 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以&#xff1a;点赞关注评论收藏&#xff08;一键四连&#xff09;哦~ &#x1f34a;自我介绍 Hello,大家好&#xff0c;我是小珑也…

C语言典型例题60

《C程序设计教程&#xff08;第四版&#xff09;——谭浩强》 习题4.1 统计全单位人员的平均工资。单位的人数是不固定的&#xff0c;工资数从键盘先后输入&#xff0c;当输入-1时&#xff0c;表示输入结束(前面输入的都是有效数字)。 代码&#xff1a; //《C程序设计教程&…

论文《Improving your graph neural networks:A High-Frequency Booster》笔记

【CLAR 2022 ICDMW】作者指出&#xff0c;现有的GNN模型主要关注于消息传递机制&#xff0c;但这些模型往往受限于低通滤波器的局限&#xff0c;导致在多层堆叠时性能下降。为了解决这个问题&#xff0c;论文提出了一种新的正则化方法&#xff0c;称为补全拉普拉斯正则化&#…