当前位置: 首页 > news >正文

C++ 布隆过滤器

1. 布隆过滤器提出

我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉 那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用 户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那 些已经存在的记录。 如何快速查找呢?

1. 用哈希表存储用户记录,缺点:浪费空间

2. 用位图存储用户记录,缺点:位图一般只能处理整形,如果内容编号是字符串,就无法处理了。

3. 将哈希与位图结合,即布隆过滤器

2. 布隆过滤器概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

3. 布隆过滤器的实现代码

#include<iostream>
#include<bitset>
using namespace std;
//哈希函数
struct BKDRHash
{size_t operator()(const string& s){// BKDRsize_t value = 0;for (auto ch : s){value *= 31;value += ch;}return value;}
};
struct APHash
{size_t operator()(const string& s){size_t hash = 0;for (long i = 0; i < s.size(); i++){if ((i & 1) == 0)hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));elsehash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));}return hash;}
};
struct DJBHash
{size_t operator()(const string & s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};
//第一个参数为插入的个数,第二个参数为容器要开空间为插入个数的倍数大小,
//第三个参数为插入的元素类型,后三个参数为哈希函数
template<size_t N,size_t X = 5,class K = string,class Hash1= BKDRHash,class Hash2 = APHash, class Hash3 = DJBHash >
class BloomFilter
{
public:void set(const K& key){size_t len = N * X;size_t index1 = Hash1()(key) % len;size_t index2 = Hash2()(key) % len;size_t index3 = Hash3()(key) % len;_bitset.set(index1);_bitset.set(index2);_bitset.set(index3);}bool test(const K& key){size_t len = N * X;size_t index1 = Hash1()(key) % len;if (_bitset.test(index1) == false)return false;size_t index2 = Hash2()(key) % len;if (_bitset.test(index2) == false)return false;size_t index3 = Hash3()(key) % len;if (_bitset.test(index2) == false)return false;return true;}private:bitset<N* X> _bitset;
};

3.1 布隆过滤器的插入

假设我们要插入元素x,使用个哈希函数分别计算元素x,得到个位置。将这三个位置的值从0改为1。

3.2 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1 。所以可以按照以下方式进行查找: 分别计算每个哈希值对应的比特位置存储的是否为 零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可
能存在,因为有些哈希函数存在一定的误判。

3.3 布隆过滤器删除 

布隆过滤器(Bloom Filter)的一个重要特性是它不支持删除操作。这是因为布隆过滤器使用哈希函数将元素映射到位数组中,当一个元素被插入到布隆过滤器时,它会将与该元素对应的多个位设置为1。一个位可能被多个元素的哈希函数命中。如果删除一个元素时将这些位设置回0,这可能会破坏其他元素的表示,导致原本正确的存在性检查变为误报。
一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给 k 个计数器(k 个哈希函数计算出的哈希地址 ) 加一,删除元素时,给 k 个计数器减一,通过多占用几倍存储
空间的代价来增加删除操作。

4.布隆过滤器的优缺点

布隆过滤器优点
1. 增加和查询元素的时间复杂度为 :O(K), (K 为哈希函数的个数,一般比较小 ) ,与数据量大小无关
2. 哈希函数相互之间没有关系,方便硬件并行运算
3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
布隆过滤器缺陷
1. 有误判率,即存在假阳性 (False Position) ,即不能准确判断元素是否在集合中 ( 补救方法:再建立一个白名单,存储可能会误判的数据)
2. 不能安全地删除元素,因为多个元素可能会映射到同一个位置。一旦位被设置为1,就无法确定是哪个元素造成的。
3. 如果采用计数方式删除,可能会存在计数回绕问题。

5.布隆过滤器的应用场景

布隆过滤器广泛应用于各种计算机系统中,用于提高数据处理的效率和减少不必要的磁盘或网络I/O操作。一些典型的应用场景包括:

  • 缓存穿透防护:在分布式缓存系统中,布隆过滤器可以用来检测一个请求的键是否可能存在于缓存中,从而避免不必要的数据库查询。

  • 网络爬虫:布隆过滤器可以帮助网络爬虫避免重复访问同一个URL。

  • 垃圾邮件过滤:通过维护一个包含已知垃圾邮件特征的布隆过滤器,可以快速过滤掉疑似垃圾邮件。

  • 社交网络内容过滤:布隆过滤器可以用来避免向用户推荐他们已经查看过的内容。

  • 数据库优化:在数据库中,布隆过滤器可以用来减少对不存在的行或列的查找,从而提高查询效率。

相关文章:

C++ 布隆过滤器

1. 布隆过滤器提出 我们在使用新闻客户端看新闻时&#xff0c;它会给我们不停地推荐新的内容&#xff0c;它每次推荐时要去重&#xff0c;去掉 那些已经看过的内容。问题来了&#xff0c;新闻客户端推荐系统如何实现推送去重的&#xff1f; 用服务器记录了用 户看过的所有历史…...

使用HTML创建用户注册表单

在当今数字化时代&#xff0c;网页表单对于收集用户信息和促进网站交互至关重要。无论您设计简单的注册表单还是复杂的调查表&#xff0c;了解HTML的基础知识可以帮助您构建有效的用户界面。在本教程中&#xff0c;我们将详细介绍如何使用HTML创建基本的用户注册表单。 第一步…...

Python零基础入门教程

Python零基础详细入门教程可以从以下几个方面进行学习和掌握&#xff1a; 一、Python基础认知 1. Python简介 由来与发展&#xff1a;Python是一种广泛使用的高级编程语言&#xff0c;由Guido van Rossum&#xff08;吉多范罗苏姆&#xff09;于1991年首次发布。Python以其简…...

成为git砖家(10): 根据文件内容生成SHA-1

文章目录 1. .git/objects 目录2. git cat-file 命令3. 根据文件内容生成 sha-14. 结语5. References 1. .git/objects 目录 git 是一个根据文件内容进行检索的系统。 当创建 hello.py, 填入 print("hello, world")的内容&#xff0c; 并执行 git add hello.py gi…...

园区导航小程序:一站式解决园区导航问题,释放存储,优化访客体验

随着园区的规模不断扩大&#xff0c;功能区划分日益复杂&#xff0c;导致访客和新员工在没有有效导航的情况下容易迷路。传统APP导航虽能解决部分问题&#xff0c;但其下载安装繁琐、占用手机内存大、且非高频使用导致的闲置&#xff0c;让许多用户望而却步。园区导航小程序的出…...

对于n进制转十进制的解法及代码(干货!)

对于p进制转十进制&#xff0c;我们有&#xff1a;(x)pa[0]*p^0a[1]*p^1a[2]*p^2...a[n]*p^n 举个例子&#xff1a;&#xff08;11001&#xff09;21*10*20*41*81*1625 &#xff08;9FA&#xff09;1610*16^015*16^19*16^22554 据此&#xff0c;我们可以编出c代码来解决问题 …...

当代互联网打工人的生存现状,看完泪流满面!

欢迎私信小编&#xff0c;了解更多产品信息呦~...

花几千上万学习Java,真没必要!(三十八)

测试代码1&#xff1a; package iotest.com; import java.nio.charset.StandardCharsets; import java.io.UnsupportedEncodingException; public class StringByteConversion { public static void main(String[] args) throws UnsupportedEncodingException { // 原始字…...

Zilliz 2025届校园招聘正式启动,寻找向量数据库内核开发工程师

为了解决非结构化数据处理问题&#xff0c;我们构建了向量数据库-Milvus! Milvus 数据库不仅是顶级开源基金会 LF AI&Data 的毕业项目&#xff0c;还曾登上数据库顶会SIGMOD、VLDB&#xff0c;在全球首届向量检索比赛中夺冠。目前&#xff0c;Milvus 项目已获得超过 2.8w s…...

TwinCAT3 新建项目教程

文章目录 打开TwinCAT 新建项目&#xff08;通过TcXaeShell&#xff09; 新建项目&#xff08;通过VS 2019&#xff09;...

大模型算法面试题(十九)

本系列收纳各种大模型面试题及答案。 1、SFT&#xff08;有监督微调&#xff09;、RM&#xff08;奖励模型&#xff09;、PPO&#xff08;强化学习&#xff09;的数据集格式&#xff1f; SFT&#xff08;有监督微调&#xff09;、RM&#xff08;奖励模型&#xff09;、PPO&…...

应用地址信息获取新技巧:Xinstall来助力

在移动互联网时代&#xff0c;应用获取用户地址信息的需求越来越普遍。无论是为了提供个性化服务&#xff0c;还是进行精准营销&#xff0c;地址信息都扮演着至关重要的角色。然而&#xff0c;如何合规、准确地获取这一信息&#xff0c;却是许多开发者面临的挑战。今天&#xf…...

图的最短路径算法:Dijkstra、Floyd-Warshall、Bellman-Ford

本文意在探讨图中最短路径算法 Dijkstra、Floyd-Warshall、Bellman-Ford 的对比和细节 整体分为如下四部分 总结性的比较了 Dijkstra、Floyd-Warshall、Bellman-FordDijkstra 算法介绍Floyd-Warshall 算法介绍Bellman-Ford 算法介绍 其中1、2、3 算法介绍部分会比较简洁&…...

Camera的pipline(TODO)

&#xff08;TODO&#xff09;...

非关系数据库-非关系数据库入门指南

非关系数据库入门指南 1. 引言&#xff1a;非关系数据库的兴起​ 在互联网技术飞速发展的今天&#xff0c;传统的关系型数据库面对海量数据和高并发访问时逐渐显得力不从心。于是&#xff0c;非关系数据库&#xff08;NoSQL&#xff0c;Not Only SQL&#xff09;应运而生&…...

看门狗IWDG、WWDG(速记版)

内置的看门狗有 独立看门狗 IWDG 和 窗口看门狗 WWDG 都用来在程序卡死的时候复位程序。 独立看门狗只有一个最晚时间界限。窗口看门狗有一个最早界限和最晚界限。独立看门狗有独立的时钟,一般设置来源时钟LSI40KHz。窗口看门狗挂靠在APB1总线上36MHz。 IWDG IWDG处于VDD供…...

ETL工程师角度下的SQL优化

作为ETL&#xff08;Extract, Transform, Load&#xff09;工程师&#xff0c;SQL优化是提高数据处理和分析效率的关键一环。优化SQL查询可以显著降低数据处理时间&#xff0c;提高ETL过程的性能。本文将从 合理设计数据模型&#xff1a;在ETL过程中&#xff0c;正确的数据模型…...

阿里云实时计算Flink在多行业的应用和实践

摘要&#xff1a;本文整理自 Flink Forward Asia 2023 中闭门会的分享。主要分享实时计算在各行业的应用实践&#xff0c;对回归实时计算的重点场景进行介绍以及企业如何使用实时计算技术&#xff0c;并且提供一些在技术架构上的参考建议。内容分为以下四个部分&#xff1a; 业…...

开源项目与工具:C++中的高性能并发库 - Intel Threading Building Blocks (TBB)

在C++的世界里,随着多核处理器成为常态,如何有效利用这些多核资源以实现高性能的并发编程成为了开发者们关注的焦点。Intel Threading Building Blocks (TBB) 作为一个专为并行编程设计的C++库,凭借其易用性、高效性和可扩展性,在高性能计算、游戏开发、金融分析等多个领域…...

Chapter 22 数据可视化——折线图

欢迎大家订阅【Python从入门到精通】专栏&#xff0c;一起探索Python的无限可能&#xff01; 文章目录 前言一、Pyecharts介绍二、安装Pyecharts三、全局配置项四、绘制折线图 前言 在大数据时代&#xff0c;数据可视化成为了分析和展示数据的重要手段。Pyecharts 是一个基于 …...

管理流创建schema流程源码解析

一、简析 schema是pulsar重要的功能之一&#xff0c;现在就一起从源码的视角看下管理流创建schema时客户端和服务端的表现 客户端 客户端主要经历以下四个步骤 创建Schema实例 根据数据类型创建相对应的实例&#xff0c;例如Avro创建AvroSchema、JSON创建JSONSchema等 获取…...

【iOS】iOS内存五大分区

iOS内存五大分区 总揽 iOS中&#xff0c;内存主要分为五大区域&#xff1a;栈区&#xff0c;堆区&#xff0c;全局区/静态区&#xff0c;常量区和代码区。总览图如下。 这个图我觉得更好记&#xff0c;因为下面是低地址&#xff0c;上面是高地址&#xff0c;是比较符合日常…...

【项目实战】—— 高并发内存池

文章目录 什么是高并发内存池&#xff1f;项目介绍一、项目背景二、项目目标三、核心组件四、关键技术五、应用场景六、项目优势 什么是高并发内存池&#xff1f; 高并发内存池是一种专门设计用于高并发环境下的内存管理机制。它的原型是Google的一个开源项目tcmalloc&#xff…...

二叉搜索树的第 k 大的节点

题目描述 给定一棵二叉搜索树&#xff0c;请找出其中第 k 大的节点。 解题基本知识 二叉搜索树&#xff08;Binary Search Tree&#xff09;又名二叉查找树、二叉排序树。它是一棵空树&#xff0c;或者是具有下列性质的二叉树&#xff1a; 若它的左子树不空&#xff0c;则左子…...

利用langchain 做大模型 Few-shot Learning 提示,包括固定和向量相似的动态样本筛选

文章目录 few-shotFixed Examples 固定样本Dynamic few-shot prompting 动态样本提示辅助参考资料 few-shot 相比大模型微调&#xff0c;在有些情况下&#xff0c;我们更想使用 Few-shot Learning 通过给模型喂相关样本示例&#xff0c;让模型能够提升相应任务的能力。 固定样…...

基于python的百度迁徙迁入、迁出数据分析(五)

终于在第五篇文章我们进入了这个系列的正题&#xff1a;数据分析 这里我选择上海2024年5月1日——5月5日的迁入、迁出数据作为分析的基础&#xff0c;首先选择节假日的数据作为分析的原因呢&#xff0c;主要是节假日人们出行目的比较单一&#xff08;出游、探亲&#xff09;&a…...

SpringBoot 如何处理跨域请求

SpringBoot 处理跨域请求&#xff0c;通常是通过配置全局的 CORS&#xff08;跨源资源共享&#xff09;策略来实现的。CORS 是一种机制&#xff0c;它使用额外的 HTTP 头部来告诉浏览器&#xff0c;让运行在一个 origin (domain) 上的 web 应用被准许访问来自不同源服务器上的指…...

大数据技术基础编程、实验和案例----大数据课程综合实验案例

一、实验目的 (1&#xff09;熟悉Linux系统、MySQL、Hadoop、HBase、Hive、Sqoop、R、Eclipse等系统和软件的安装和使用&#xff1b; (2&#xff09;了解大数据处理的基本流程&#xff1b; (3&#xff09;熟悉数据预处理方法&#xff1b; (4&#xff09;熟悉在不同类型数据库之…...

微信小程序-获取手机号:HttpClientErrorException: 412 Precondition Failed: [no body]

问题&#xff1a; 412 异常就是你的请求参数获取请求头与服务器的不符&#xff0c;缺少请求体&#xff01; 我的问题&#xff1a; 我这里获取微信手机号的时候突然给我报错142&#xff0c;但是代码用的是原来的代码&#xff0c;换了一个框架就噶了&#xff01; 排查问题&am…...

大数据核心概念与技术架构简介

大数据基本概念 大数据是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合&#xff0c;是具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。 大数据特征&#xff1a; 数据量大&#xff1a;一般以P&#xff08;1000个TB&a…...

企业如何做网站建站/指数函数和对数函数

Linux——匿名管道的详解1.进程间通信的概念2.匿名管道2.1匿名管道的本质2.2匿名管道的创建方法及其数据拷贝过程2.3管道中数据的生命周期2.4管道的存储数据的容量2.5将管道写端和读端分别设置为非阻塞属性1.进程间通信的概念 什么是进程间通信&#xff1f; 进程间通信就是在不…...

页面设计计划/北京seo业务员

LinkIt_for_RTOS_Firmware_Update_Developers_Guide--用于实时操作系统固件更新开发指南的MediaTek Linkit™开发平台 MediaTek Linkit™SDK v4支持固件空中更新(FOTA)更新&#xff0c;这是一种广泛采用的成本和时间高效的解决方案&#xff0c;用于更新连接设备上的固件。开发…...

做网站如何躲过网警/旅游网站网页设计

刚从山东回来&#xff0c;一堆麻烦事情。这不&#xff0c;快要下班了&#xff0c;客户说oracle rac挂了。 这是有两个节点和一个共享存储组成的rac系统&#xff0c;安装了oracle 11g r2.我试着登录系统查看&#xff0c;发现一个服务器不能联通。另一个上去了&#xff0c;执行df…...

网站备案还要买幕布/广东seo快速排名

#管理后台&#xff0c;付费酒店如果没有所属部门的话&#xff0c;就默认为“4营销中心”#库里查询没有所属部门的总共有7106多家&#xff0c;SELECT a.VHotelID,a.VHotelID,b.DepartmentIDFROMtable a LEFT JOIN table_info b ON a.vhotelid b.VHotelID WHERE a.BusinessState…...

做网站开发找哪家公司/排名优化公司口碑哪家好

tcp是流式传输 假设A给B通过TCP发了200字节&#xff0c; 然后又发了300字节&#xff0c; 此时B调用recv&#xff08;设置预期接受1000个字节&#xff09;&#xff0c;那么请问B实际接受到多少字节&#xff1f; 根据tcp粘包特性&#xff0c;可知&#xff0c; B端调用一次recv&am…...

wordpress中footer函数/google搜索引擎入口 镜像

内涵图转载于:https://www.cnblogs.com/jhcla/p/4390174.html...