【C++】哈希的应用:位图和布隆过滤器

news/2024/3/29 20:08:34/文章来源:https://blog.csdn.net/C0631xjn_/article/details/130231010

目录

  • 1. 位图
    • 1.1 位图的概念
    • 1.2 位图的结构
    • 1.3 位图的实现
  • 2. 布隆过滤器
    • 2.1 概念
    • 2.2 结构
    • 2.3 布隆过滤器的实现


1. 位图

1.1 位图的概念

💭位图bitset)是一种基于哈希思想设计的数据结构,其功能主要用于判断数据是否已存在。适用于海量数据,且数据不重复的场景。

以一个问题引入:给40亿个不重复的无符号整数,无序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。

🔎暴力查找法:遍历所有数据,查找目标数是否存在于数据中。但是,因为数据巨大,遍历效率会很慢。
🔎二分查找法:但要先排序,排序要在内存中排,40亿个整数大约要占16G空间(推导过程如下图),内存空间不足。

在这里插入图片描述

因此以上两种方法都不适应,此时就要上位图了。


1.2 位图的结构

在这里插入图片描述

⭕位图以一个个比特位组成,每个比特位代表一种状态,且每个位都有一个下标。位图中的状态为1表示对应下标的数据存在,为0表示对应下标的数据不存在。

举个栗子:假设有如下一组数据,用位图表示

int arr = {3,11,8,23,12,9,0,19,17}; 

在这里插入图片描述


1.3 位图的实现

namespace ckf
{template <size_t N> // 范围 0~Nclass bitset{public:bitset(){_bits.resize(N / 8 + 1, 0);}// 给第x位置1void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (1 << j);}// 给第x位置0void reset(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] &= ~(1 << j);}// 检测第x位是否存在bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);}private:vector<char> _bits;};
}

2. 布隆过滤器

2.1 概念

💭位图只能应用于整数,如果想存储其他类型应该怎么办呢?用布隆过滤器

布隆过滤器(Bloom Filter)是一种快速、高效的数据结构,用于检测一个元素是否属于某个集合。它通过使用一个位数组和多个哈希函数来判断一个元素是否可能在集合中。

布隆过滤器的主要应用是在大规模数据集合中判断某个元素是否存在,比如网络爬虫中URL的去重、大型分布式系统中的缓存机制等。布隆过滤器可以节省存储空间,因为它不需要将元素本身存储在数据结构中,只需要存储其哈希值。

但是,布隆过滤器也存在一些缺点,如误判率高和无法删除元素等。在使用时需要根据具体场景进行权衡和选择。

2.2 结构

在这里插入图片描述

⭕假设向布隆过滤器插入了"left""going"三个字符串,分别通过两个哈希函数映射到位图数组上。而"right","find"此时并不在布隆过滤器中,但是由于哈希函数映射与已在的字符串相同,导致它们在位图上的比特位存在1,这就是布隆过滤器的误判。

得出结论:布隆过滤器中,元素通过哈希函数映射后,若每个位都为1,则不一定存在(可能误判),若存在一个位为0,则该元素一定不存在。因此布隆过滤器只能判断元素不存在,因此起到了过滤的作用。

  • 如何选择哈希函数个数和布隆过滤器长度
    参考文章:详解布隆过滤器的原理,使用场景和注意事项

2.3 布隆过滤器的实现

// N为最多能插入的数据个数
template <size_t N, size_t X = 5,class K = string, class HashFunc1 = BKDRHash<K>, class HashFunc2 = SDBMHash<K>, class HashFunc3 = RSHash<K>>
class bloom_filter
{
public:void set(const K& key){size_t len = N * X;size_t hash1 = HashFunc1()(key) % len;size_t hash2 = HashFunc2()(key) % len;size_t hash3 = HashFunc3()(key) % len;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}bool test(const K& key){size_t len = N * X;size_t hash1 = HashFunc1()(key) % len;if (!_bs.test(hash1)){return false;}size_t hash2 = HashFunc2()(key) % len;if (!_bs.test(hash2)){return false;}size_t hash3 = HashFunc3()(key) % len;if (!_bs.test(hash3)){return false;}return true;}private:bitset<N* X> _bs;
};

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

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

相关文章

来使用分支语句和循环语句实现一个小游戏吧(猜数字游戏)

猜数字游戏 1.代码展示2.菜单设计3.主函数部分3.随机数设计 所属专栏&#xff1a;C语言 博主首页&#xff1a;初阳785 代码托管&#xff1a;chuyang785 感谢大家的支持&#xff0c;您的点赞和关注是对我最大的支持&#xff01;&#xff01;&#xff01; 博主也会更加的努力&am…

rtthread默认网卡的操作

设置网卡优先级 在 RT-Thread 操作系统中&#xff0c;可以通过修改网卡的优先级来设置默认网卡。优先级越高的网卡会被优先选择为默认网卡。 下面介绍一些设置默认网卡优先级的方法&#xff1a; 在 RT-Thread 的网络配置文件 rtconfig.h 中&#xff0c;可以通过修改 NETIF_P…

Jmeter5.1.1报错:java.net.BindException: Address already in use: connect

Jmeter5.1.1报错&#xff1a;java.net.BindException: Address already in use: connect 原因&#xff1a;从网上找到资料&#xff1a;端口占用 Windows提供给TCP/IP链接的端口为 1024-5000&#xff0c;并且要四分钟来循环回收它们&#xff0c;就导致我们在短时间内跑大量的请…

把ChatGPT训练成你的得力助手

在调教chatgpt时&#xff0c;我们大部分的时候都需要一个好的学术翻译官&#xff0c;但是在他成为学术翻译官之前我们有很多规定要说明&#xff0c;比如不用回答我的问题&#xff0c;不用计算公式等。我将以下命令要求集成&#xff0c;在使用的时候只需要你发给它这段话&#x…

如何评估小程序开发费用:从项目规模到技术需求

作为一种越来越受欢迎的移动应用&#xff0c;小程序的开发费用是许多企业和个人考虑的重要因素之一。但是&#xff0c;要确定小程序开发费用并不是一件容易的事情&#xff0c;因为它涉及到多个因素&#xff0c;从项目规模到技术需求。 项目规模 小程序开发的费用通常与项目规…

Linux部署人大金仓(Kingbase8)

陈老老老板&#x1f9b8; &#x1f468;‍&#x1f4bb;本文专栏&#xff1a;国产数据库-人大金仓&#xff08;kingbase8&#xff09;&#xff08;主要讲一些人大金仓数据库相关的内容&#xff09; &#x1f468;‍&#x1f4bb;本文简述&#xff1a;本文讲一下LInux上部署人大…

Vue+Echarts 项目演练(中)后台数据接口的创建

全局引用Echarts与axios 后台接口创建express路由 api接口数据创建 全局引用Echarts与axios vue3.0的挂载方式&#xff1a;使用Provide/Inject依赖注入&#xff0c;将替代vue2中在原型链上挂载一些属性在app.vue中使用provider来给后代们提供数据 <script> import { p…

经典数据结构之2-3树

2-3树定义 2-3树&#xff0c;是最简单的B-树&#xff0c;其中2、3主要体现在每个非叶子节点都有2个或3个子节点&#xff0c;B-树即是平衡树&#xff0c;平衡树是为了解决不平衡树查询效率问题&#xff0c;常见的二叉平衡书有AVL树&#xff0c;它虽然提高了查询效率&#xff0c…

深入JVM了解Java对象实例化过程

文章目录 一、对象创建方式二、对象产生步骤1、判断对象是否已经加载、链接、初始化2、为对象分配内存空间3、处理并发问题3.1 TLAB 4、初始化零值5、完善对象内存布局的信息6、调用对象的实例化方法 <init>7、总结 三、对象的内存布局1、对象头1.1 运行时元数据&#xf…

详解树与二叉树的概念,结构,及实现(上篇)

目录 一&#xff0c; 树 1.2 树的相关概念 1.3 树的表示 1.4 树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 二&#xff0c; 二叉树 2.1二叉树概念 三&#xff0c;特殊的二叉树 1. 满二叉树 2. 完全二叉树 3. 1 二叉树的性质 3. 2 二叉树的存储…

【速卖通】 AliExpress(速卖通)关键词搜索结果采集

采集场景 在AliExpress(速卖通) 首页中 http://www.aliexpress.com 中输入关键词&#xff0c;采集关键词搜索后得到的商品列表信息。 采集字段 关键词、标题、商品id、商品图片地址、商品详情链接、价格、免费退送货、星级、已出售数量、店铺名 采集结果 采集结果可导出为E…

Linux-初学者系列——篇幅7_文本编辑和处理命令

文本编辑和处理命令-目录 一、系统基本编辑命令安装vim软件工具包语法格式&#xff1a; 1、vim编辑命令模式01 普通模式02 编辑模式03 命令模式 2、编辑文件技巧01 批量删除多行指定信息02 批量增加多列指定信息03 编辑常见问题错误1&#xff1a;没有指定编辑信息错误2&#xf…

基于TensorRT的yolov5 实例分割部署

yolov5-7.0 github: https://github.com/ultralytics/yolov5/tree/master 1. 代码的使用 1.1 训练yolov5-seg模型 使用的yolov5-7.0的代码,github下载:https://github.com/ultralytics/yolov5/releases/tag/v7.0 训练指令 python segment/train.py --data coco128-seg.y…

centos7 查看服务器配置信息

1.linux查看版本当前操作系统发行信息 cat /etc/centos-release cat /etc/centos-release 2、查看内核版本uname -a或者cat /proc/version 3、查看CPU参数 1&#xff09;、查看 CPU 物理个数   grep physical id /proc/cpuinfo | sort -u | wc -l 2&#xff09;、查看 CPU …

SpringCloud:ElasticSearch之DSL查询文档

elasticsearch的查询依然是基于JSON风格的DSL来实现的。 1.1.DSL查询分类 Elasticsearch提供了基于JSON的DSL&#xff08;Domain Specific Language&#xff09;来定义查询。常见的查询类型包括&#xff1a; 查询所有&#xff1a;查询出所有数据&#xff0c;一般测试用。例如…

magento webapi 接口返回 json对象

前言 现在主流的项目开发都是前后端分离&#xff0c;数据通过json对象格式进行传输。但是magento框架&#xff0c;和传统PHP框架相比&#xff0c;区别很大。虽然也支持以RestApi的形式传输数据&#xff0c;但是要么格式并非是传统jsonObject要么就是需要大量的get、set方法。本…

关于xilinx使用PCIE实现FPGA的部分重配置实现(MCAP)

平台&#xff1a;vivado21018.3 芯片&#xff1a;xcku115-flva1517-2-i (active) 本文官方文档&#xff1a;Xilinx_Answer_64761_Ultrascale_Devices 本文驱动下载地址&#xff1a;64761 - Bitstream Loading across the PCI Express Link in UltraScale and UltraScale Dev…

JAVA——线程池

目录 一、线程池的概念 二、Java标准库中的线程池 三、ThreadPoolExecutor 类的参数 四、线程池的拒绝策略 五、模拟实现线程池 一、线程池的概念 线程池顾名思义就是集中存储线程的地方——联想一下水池。 线程池是一种多线程处理形式&#xff0c;处理过程中将任务添加到…

Ext4日志优化-iJournaling

背景 这几年随着SSD等高性能介质的普及&#xff0c;及其在大规模分布式存储系统上的应用。基于Append only的日志写入技术也应用得越来越多&#xff0c;这几天刚好有空&#xff0c;重读了Ext4文件系统的日志部分的内容&#xff0c;也正好看到一篇对Ext4日志技术进行优化的论文…

《编码——隐藏在计算机软硬件背后的语言》精炼——第11章(门)

“The only source of knowledge is experience.” - Albert Einstein 引言 编码是一种处理并表达信息的方式&#xff0c;它包括摩斯电码、盲文、二进制语言等等&#xff0c;当然作为计算机类的经典书籍&#xff0c;这本书简述了计算机中以二进制数为基础的编码方式&#xff0…