C++中布隆过滤器

🐶博主主页:@ᰔᩚ. 一怀明月ꦿ 

❤️‍🔥专栏系列:线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C++,linux

🔥座右铭:“不要等到什么都没有了,才下定决心去做”

🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀

目录

布隆过滤器

布隆过滤器的原理

添加元素

具体使用场景

BKDRHash

APHash

DJBHash

哈希分割


布隆过滤器

布隆过滤器(Bloom Filter)是一种数据结构,用于快速检查一个元素是否属于一个集合中。它通过使用一系列哈希函数和位数组来实现。当一个元素被添加到布隆过滤器时,将对其进行多次哈希,并将相应的位数组位置设置为1。当检查一个元素是否在集合中时,布隆过滤器会对该元素进行相同的哈希,并检查对应的位数组位置是否都为1,若其中有一个位置不为1,则可以确定该元素不在集合中;若都为1,则该元素可能在集合中(存在一定的误判率)。

布隆过滤器的主要优点是空间效率和查询速度高,因为它不需要存储实际的元素内容,只需要存储一系列位的数组。但是,布隆过滤器也有一定的缺点,主要是存在误判率(可能会判断一个不在集合中的元素为在集合中)以及不支持元素的删除操作。

常见的应用场景包括网络爬虫中的URL去重、数据库查询优化中的缓存、拼写检查等。

布隆过滤器的原理

一个值映射多个比特位,还是可能存在冲突,映射多个位,降低误判的概率,布隆过滤器的数据结构是一个位向量,也就是一个由0、1所组成的bit数组

添加元素

每个元素添加进布隆过滤器前,都会经过多个不同的哈希函数,计算出不同的哈希值,然后映射到位向量上,也就是对应的位"置1"

对元素进行多个不同的哈希运算,得到多个位下标,判断所有映射位置是否都为1,若是,则元素可能存在,否则一定不存在

注意:由于不同的值通过哈希函数之后可能会映射到相同的位置,因此如果一个不存在的元素对应的位都被其他元素所设置1,则查询时就会误判

具体使用场景

如果存在一个数据库,存储的都是都是用的昵称,我们用注册时,需要注册昵称,但是昵称不能和数据库存储的昵称重复,所以就需要在用户注册昵称时,去查询数据库是否存在该昵称。但是传统查询效率太低了,使用哈希表的方式查询的话,可以将字符串转为整形,进行映射但是会面临一个问题,整形开辟的最大空间是42亿多(因为最大的无符号整数是2^32或2^64),但是字符串接近无限大,例如,一个10长度的单词,就有19275223968000之多所以用整数完全存储不了字符串,而且单纯的哈希表,可能导致多个字符串对应一个整数。因此布隆过滤器非常有必要,布隆过滤器底层思想还是哈希,和传统的哈希表不一样。布隆过滤器使用了位图,用多个位置表示一个字符串,这里我们需要将字符串转成的方法。

BKDRHash
unsigned int BKDRHash(const std::string& key) {
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    for (char c : key) {
        hash = hash * seed + c;
    }
    return hash;
}

稳定性:较为稳定,具有良好的分布性。

APHash
unsigned int APHash(const std::string& key) {
    unsigned int hash = 0;
    for (char c : key) {
        hash ^= ((hash << 7) ^ c ^ (hash >> 3));
    }
    return hash;
}

稳定性:稳定,适用于大多数情况。

DJBHash
unsigned int DJBHash(const std::string& key) {
    unsigned int hash = 5381;
    for (char c : key) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

稳定性:非常稳定,被广泛使用。

一般使用三个转换方法效率就很高了(就是用三个比特位对应一个字符串)。使用布隆过滤器,我们就可以准觉的判断一个昵称是否在数据库已经存在,这样的时间效率O(1)

但是,布隆过滤器也有一定的缺点,主要是存在误判率(可能会判断一个不在集合中的元素为在集合中)以及不支持元素的删除操作。

哈希分割

1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

2. 如何扩展BloomFilter使得它支持删除元素的操作

假设平均一个query(查询字符)50byte

1G约等于10byte

100亿query 5000byte 约等于500G

哈希表/红黑树空间严重不足

1.

第一步:将两个文件分别哈希分割到多个小文件中

读取每个query,计算i=Hash(query)%500,i是几,query就进入到Ai小文件

读取每个query,计算i=Hash(query)%500,i是几,query就进入到Bi小文件

2.Ai和Bi分别插入到setA和setB,快速找交集

有一个问题,就是分割文件也挺大怎么办,例如:10G文件

情况有两种:

1)这个文件中有很多重复query

2))这个文件中有不同的query

解决方案:

其实很简单,Ai和Bi分别直接插入到setA和setB,如果是情况1),query大量重复,后面插入会失败(因为set不允许重复值插入),情况二,不断插入set以后,内存不足就会抛出异常,就需要换一个哈希函数,进行二次切分,再找交集

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址? 与上题条件相同,

如何找到top K的IP?

1.i=Hash(ip)%100

这个ip就进入同一个文件,相同的ip一定会进同一个文件,不同的ip也会进同一个文件,但是同一个ip不会进不同的文件

2.用map依次统计每个文件ip次数,然后比较每个文件最多的ip

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区,我们共同探讨,共同学习,共同进步。谢谢大家! 🌸🌸🌸 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/575962.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

获取boss直聘城市地区josn数据

获取boss直聘城市地区josn数据 当我需要爬取多个城市的地区的时候&#xff0c;只能手动点击&#xff0c;然后一个一个看 结果&#xff1a; 能看到所有区域所有子地区的地区代码 解析该JSON数据 import pandas as pd import requests code[] area[] 城市代码101210100 res…

微信小程序使用 Vant Weapp 中 Collapse 折叠面板 的问题!

需求&#xff1a;结合Tab 标签页 和 Collapse 折叠面板 组合成显示课本和章节内容&#xff0c;并且用户体验要好点&#xff01; 如下图展示&#xff1a; 问题&#xff1a;如何使用Collapse 折叠面板 将内容循环展示出来&#xff1f; js中的数据是这样的 代码实现&#xff1…

「屡教不改」又被罚,谁还在相信山姆?

值得信赖的品质」「全球进口品牌」……「更好的生活尽在山姆」。 作为全球最大的会员制商店&#xff0c;山姆这几年可以说在中国线下零售市场集体遇劫的背景下&#xff0c;逆势崛起&#xff0c;甚至可以说做到了独树一帜。‍‍‍‍‍‍ 背后的原因是什么&#xff1f;会员制这一…

react 使用WEB3.0控件开发包 V3.0接入海康威视摄像头

1、下载官方安装包&#xff1a; 2、安装官方插件 3、引入文件 在public/index 中引入监控依赖&#xff0c;这三个文件可以在下载的官方demo中找到 4、react 中使用 useEffect(() > { const ipInfo :[192.168.xxxx];//初始化摄像头const WebVideoCtrl window.WebVideoCtrl…

Oracle delete删除数据是否为逻辑删除、新插入数据占用的数据块位置实验

假设一&#xff1a;数据库delete删除为直接删除 假设二&#xff1a;数据库delete删除为逻辑删除&#xff0c;在数据块标记出来&#xff0c;但是实际并没有删除。 方式一&#xff1a;通过dump数据块的方式来实现 我们先用小数据量&#xff0c;通过dump数据块的方式来实现 -- 数…

安卓手机连接电脑实用技巧:实现文件传输与共享

在手机使用过程中&#xff0c;我们常常需要将手机中的文件传输到电脑&#xff0c;或者将手机与电脑进行共享。为了实现这一需求&#xff0c;掌握一些实用的安卓手机连接电脑技巧就显得尤为重要。本文将为您详细介绍2种简单、高效且安全的方法&#xff0c;让您轻松实现安卓手机与…

【opencv 加速推理】如何安装 支持cuda的opencv 包 用于截帧加速

要在支持CUDA的系统上安装OpenCV&#xff0c;您可以使用pip来安装支持CUDA的OpenCV版本。OpenCV支持CUDA加速&#xff0c;但需要安装额外的库&#xff0c;如cuDNN和NVIDIA CUDA Toolkit。以下是一般步骤&#xff1a; 安装NVIDIA CUDA Toolkit: 首先&#xff0c;您需要安装NVID…

qt5core.dll怎么下载,qt5core.dll丢失能否修复?

qt5core.dll的丢失真是让人头疼。这个Visual C Redistributable for Visual Studio 2015的运行时库被许多程序和游戏所依赖&#xff0c;一旦缺失了qt5core.dll&#xff0c;就会面临无法打开程序或游戏&#xff0c;甚至系统崩溃等一系列问题。 qt5core.dll的消失会带来以下麻烦 …

泰迪智能科技助力中山三院放射科搭建生成式大模型应用

泰迪智能科技作为一家专业从事物联网、大数据及人工智能技术研发、咨询与培训的高科技企业&#xff0c;具有强大的技术研发实力和应用经验。中山大学附属第三医院放射科是集医疗、教学、科研工作于一体的广东省临床重点专科&#xff0c;具有深厚的医疗资源和科研基础。两者合作…

GaN HEMT中短沟道效应的建模

来源&#xff1a;Modeling of Short-Channel Effects in GaN HEMTs&#xff08;TED 20年&#xff09; 摘要 在本文中&#xff0c;我们提出了一种用于估算GaN高电子迁移率晶体管&#xff08;HEMT&#xff09;器件中短沟道效应&#xff08;SCEs&#xff09;的显式和解析的基于电…

安卓和ios设置自己的短链

ios 的info.plist文件 设置 CFBundleURLSchemes 其中konnect 就是设置app的短链名称 <array><dict><key>CFBundleTypeRole</key><string>Editor</string><key>CFBundleURLName</key><string>org.konnect.app</str…

【Redis】Redis 非关系型数据库 安装、配置、使用(全集)

目录 Redis 第一章 1、什么是redis 2、安装redis 1-7 8 3、redis使用 第二章 1、redis的使用 1、使用方式 2、使用Java代码使用redis 3、优化连接redis 2、五种数据类型 常用命令 string hash list set zset 不同数据类型存、取、遍历的方法 3、redis在项目…

JCE cannot authenticate the provider BC

前言&#xff1a; 公司项目有用AES加密的&#xff0c;报错原因是BC&#xff08;Bouncy Castle&#xff09;提供的加密服务时&#xff0c;JCE&#xff08;Java Cryptography Extension&#xff09;无法进行验证。这通常是由于 JCE 的默认策略文件不支持所需的加密算法&#xff…

Windows下Golang初学乍到

安装 没啥说的&#xff0c;官网下载即可&#xff0c;地址&#xff1a;All releases - The Go Programming Language 根据系统类型下载即可&#xff01; 配置 Windows下安装完后&#xff0c;发现path中已经有了&#xff0c;但为了避免可能的问题&#xff0c;还是建议配置GOPA…

不得不说,在很多业务中,这种设计模式用得真的很香

故事 “不能在写if else来拓展当前系统了&#xff0c;现在已经有三个支付场景了…”工位上&#xff0c;小猫看着电脑&#xff0c;挠着头。 就在刚刚&#xff0c;小猫接到了一个新需求&#xff0c;需要和客户公司打通资产&#xff0c;形成资产联动。说白了就是需要定制化对接客…

Linux下基本指令-掌握

目录 为什么要学命令行 Linux下基本指令-掌握 ls 指令 pwd命令 cd 指令 touch指令 mkdir指令&#xff08;重要&#xff09;&#xff1a; rmdir指令 && rm 指令&#xff08;重要&#xff09;&#xff1a; man指令&#xff08;重要&#xff09;&#xff1a; cp指…

微信黑名单怎么恢复?一招迅速搞定

“求助&#xff01;微信拉黑后&#xff0c;怎样找到并解除黑名单&#xff1f;我不知道具体的操作&#xff0c;希望可以分析给我详细的图文解说&#xff0c;感谢&#xff01;” 微信的黑名单功能允许用户将某人加入黑名单&#xff0c;从而屏蔽其发送消息、查看朋友圈等行为。然…

7天入门Android开发之第1天——初识Android

一、Android系统 1.Linux内核层&#xff1a; 这是安卓系统的底层&#xff0c;它提供了基本的系统功能&#xff0c;如内存管理、进程管理、驱动程序模型等。安卓系统构建在Linux内核之上&#xff0c;借助于Linux的稳定性和安全性。 2.系统运行库层&#xff1a; 这一层包括了安卓…

最新windows版本erlang26.0和rabbitmq3.13下载

Erlang下载 官网下载&#xff1a;https://www.erlang.org/patches/otp-26.0 百度网盘&#xff1a;https://pan.baidu.com/s/1xU4syn14Bh7QR-skjm_hOg 提取码&#xff1a;az1t RabbtitMQ下载 官网下载&#xff1a;https://www.rabbitmq.com/docs/install-windows 百度网盘…

一文解读:阿里云 AI 基础设施的演进与挑战

云布道师 2024 年 4 月 18-19 日&#xff0c;2024 中国生成式 AI 大会在北京 JW 万豪酒店举行&#xff0c;阿里云高级技术专家、阿里云异构计算 AI 推理团队负责人李鹏受邀在【AI Infra】专场发表题为《AI 基础设施的演进与挑战》的主题演讲。李鹏从 AIGC 对云基础设施的挑战、…