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

C++|哈希应用->位图

目录

一、概念

1.1原理分析:

1.2效率分析:

二、模拟实现

2.1位图框架+初始化空间

2.2映射

2.3清零

2.4判断

2.5测试代码

三、位图扩展应用


一、概念

位图,本质上也是一个数组,通过哈希思想构造的一种数据结构,他提现的哈希思想是整数与比特位的映射,通过比特位来代表某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在。 

通过一道经典题来引入如何模拟实现位图结构。

给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。【腾讯】

方法1:遍历,时间复杂度O(N)

方法2:排序O(N*logN)+二分查找O(logN),时间复杂度O((N+1)*logN)

这两种方法看似都行,但是有一个问题的是40亿个整数大小,每个整形占4个字节,40亿个整数占160亿个字节,而1GB ≈ 10亿个字节,所以40亿个整数≈16GB,而16GB是大于正常的内存大小,我们也无法在内存中开16GB大小的空间。所以,该40亿个数据是存放在文件当中,但是也无法直接导入到内存当中,那么为了解决该问题,就可以采用映射的方式,将数据映射到位图中,且位图的大小是不超过内存的大小。至于原理是什么,接下来进行解释。

方法3:位图

1.1原理分析:

将每个整数想象成一个比特位,对于位图来说,它是个数组,目的就是要将这些整数存储到数组中去,也就是将比特位存储到数组中去,

那么数组存储的数据类型又是什么,只能是整形,如果是char类型,根本存不下,其他类型又不符合,接着将数组中每个整数当成32个比特位去理解,

所以最终目的是将比特位映射到数组中的对应整数中的32个比特位之中,也就是将整数映射到数组中对应整数的32个比特位之中,并将映射位置设为1,所以就可以通过判断映射到32个比特位的对应位置是1或者0来确定该整数是否存在。示意图;

通过该图,可以更清晰的了解是如何发生映射的,可以发现,数组中存储的仍然是整数,但是要把整数当成32个比特位去理解,虽然映射后,数组中的整数值是改变了,但是所看的根本就不是该整数值,而是整数对应的比特为是1还是0的状态来判断要映射的整数是否存在。

1.2效率分析:

那么这样算下来,40亿个数据映射到数组中的时间复杂度是O(N),但是对于该16GB的大小,对于数组来说就只要开16GB/32 = 0.5G 大小的空间,且内存是完全够开的,这就是位图体现的作用。

位图就是个以空间换时间的做法,但同时位图有自己的缺陷,就是只能针对整型数据,数据量大,整数在不在的问题。而对于其他数据类型不支持,那么对于这一问题,布隆过滤器可以解决,这在下一章节将解决

现在就来模拟实现一下位图。 

二、模拟实现

2.1位图框架+初始化空间

对于位图,需要容纳海量数据,判断数据是否存在,所以采用的是非类型模板参数。 

假设整形个数据个数为N,那么对于位图而言需要开多大空间呢?

是 N/32个吗? 并不是,对于刚好是32的倍数的确实满足,但对于不能刚好取整的就要多开一个,即使是刚好取整,多开32个比特位空间也不足挂齿。所以最终开的空间是 N/32 + 1个大小空间。

    template<size_t N>class bitset{public:bitset(){_bst.resize(N / 32 + 1);}private:vector<int> _bst;};

2.2映射

对于映射,在概念中,也已经简明扼要,这就不在过多阐述。

        void set(size_t x){int i = x/32;//在第几个整形int j = x % 32;//在这个整形的第几个比特位_bst[i] |= (1 << j);//将该位置设置为1}

2.3清零

对于映射完后的数据,如果不想要了,就可以清理调,那么对此该如何操作了。其实只需要更改一下位操作即可,即_bst[i] &= ~(1<<j);示意图:

实现:

void reset(size_t x){int i = (x >> 5);int j = x % 32;_bst[i] &= ~(1 << j);//将对应映射位置清0}

2.4判断

同理只需要更改为操作判断该为是否为1即可

实现: 

        bool test(size_t x){int i = (x >> 5);int j = x % 32;return _bst[i] & (1 << j);//测试该整数映射位置是否为1,即判断整数在不在}

2.5测试代码

//MyBitSet.h
#include <iostream>
#include <vector>
using namespace std;
namespace bit
{template<size_t N>class bitset{public:bitset(){_bst.resize(N / 32 + 1);}void set(size_t x){int i = x/32;//在第几个整形int j = x % 32;//在这个整形的第几个比特位_bst[i] |= (1 << j);//将该位置设置为1}void reset(size_t x){int i = (x >> 5);int j = x % 32;_bst[i] &= ~(1 << j);//将对应映射位置清0}bool test(size_t x){int i = (x >> 5);int j = x % 32;return _bst[i] & (1 << j);//测试该整数映射位置是否为1,即判断整数在不在}private:vector<int> _bst;};
}

 测试:

#include "MyBitSet.h"int main()
{bit::bitset<0xffffffff> bst;int arr[] = { 1,3,7,4,12,16,19,13,22,18 };for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++){bst.set(arr[i]);}cout << bst.test(7);return 0;
}

 输出结果:

三、位图扩展应用

1.给定100亿个整数,设计算法找到只出现一次的整数?

 这里直接说解法了,用两个位图来实现,对于这100一个整数可能出现重复的数,那么可以分三种情况,出现0次,1次,2次及以上,那么可以用位图来表示的情况是:

出现0次:0 0

出现1次:0 1

出现2次及以上:1 0,

100亿个整数大约1.25GB,构造两个分别为2GB的位图即可,这样内存开了4GB的空间,也是够的。 

 代码实现,对于位图的代码,前面已经实现了,这里就直接使用了:

	template<size_t N>class two_bitset{public:void set(size_t x){if (_bst1.test(x) == false && _bst2.test(x) == false)//出现1次{_bst2.set(x);}else if (_bst1.test(x) == false && _bst2.test(x) == true)//出现2次{_bst1.set(x);//1_bst2.reset(x);//0}}void PrintOnce(){for (int i = 0; i < N; i++){if (_bst1.test(i) == false && _bst2.test(i) == true){cout << i << endl;;}}}private:bitset<N> _bst1;bitset<N> _bst2;};

测试:

#include "MyBitSet.h"int main()
{bit::two_bitset<100> tbst;int arr[] = { 1,3,3,7,4,12,12,16,16,19,13,13,22,22,18 };for (auto e : arr){tbst.set(e);}tbst.PrintOnce();return 0;
}

输出结果:

2.给两个文件,分别由100亿个整数,我们只有1G内存,如何找到两个文件交集?

方案一:整型的范围是确定的,如果按大小算大约为2GB,映射到位图中,位图只需开2GB/32 =1/16,所以构造一个位图开0.5G是完全够用的,虽然有100亿个数据,但都脱离不开整型的范围,必然会有重复,且位图会进行去重,所以0.5G必然够用。接着,将一个文件的数据映射到这个位图,再判断另一个文件的数据在不在位图中即可。

方案二:构造两个位图,每个位图开0.5G个内存,分别将两个文件中的数据映射到两个位图中,进行按位与比较即可。

3.1个文件有100亿个整数,1G内存,设计算法找到出现次数不超过2次的所有整数

这跟第一个情况是类似的,分析出现0次,1次,2次,3次及以上,这里就不在实现了。 

end~

相关文章:

C++|哈希应用->位图

目录 一、概念 1.1原理分析&#xff1a; 1.2效率分析&#xff1a; 二、模拟实现 2.1位图框架初始化空间 2.2映射 2.3清零 2.4判断 2.5测试代码 三、位图扩展应用 一、概念 位图&#xff0c;本质上也是一个数组&#xff0c;通过哈希思想构造的一种数据结构&#xff0c…...

Rust 实战丨SSE(Server-Sent Events)

&#x1f4cc; SSE&#xff08;Server-Sent Events&#xff09;是一种允许服务器向客户端浏览器推送信息的技术。它是 HTML5 的一部分&#xff0c;专门用于建立一个单向的从服务器到客户端的通信连接。SSE的使用场景非常广泛&#xff0c;包括实时消息推送、实时通知更新等。 S…...

Django API开发实战:前后端分离、Restful风格与DRF序列化器详解

系列文章目录 Django入门全攻略&#xff1a;从零搭建你的第一个Web项目Django ORM入门指南&#xff1a;从概念到实践&#xff0c;掌握模型创建、迁移与视图操作Django ORM实战&#xff1a;模型字段与元选项配置&#xff0c;以及链式过滤与QF查询详解Django ORM深度游&#xff…...

React基础教程:TodoList案例

todoList案例——增加 定义状态 // 定义状态state {list: ["kevin", "book", "paul"]}利用ul遍历list数组 <ul>{this.state.list.map(item ><li style{{fontWeight: "bold", fontSize: "20px"}} key{item.i…...

PHP超详细安装及应用

目录 所需安装包如下 一、PHP安装 依赖包安装 安装扩展工具&#xff08;先将PHP所需的软件包全部拖进centos根目录下&#xff09; 安装libmcrypt 安装mhash 安装mcrypt 安装PHP 二、设置LAMP组件环境&#xff08;要保证mysql、http都安装完成了&#xff09; Php.ini的建…...

【算法篇】大数加法JavaScript版

题目描述 以字符串的形式读入两个数字&#xff0c;编写一个函数计算它们的和&#xff0c;以字符串形式返回。 数据范围&#xff1a;s.length,t.length≤100000&#xff0c;字符串仅由’0’~‘9’构成 要求&#xff1a;时间复杂度 &#x1d442;(&#x1d45b;) 示例1 输入&…...

【LeetCode 128】 最长连续子序列

判断前一位数在不在字典中是这道题的关键之处&#xff0c;这样就可以避免重复查找&#xff0c;从而达到O(n) 的时间复杂度。如果没有这个判断&#xff0c;那么时间复杂度最坏也得是O(N^2)级别的。 1. 题目 2. 分析 合理利用数据结构。本题中使用了set来保存数组的元素&#x…...

SpringCloud-面试篇(二十六)

&#xff08;1&#xff09;Sentinel核心API-ProcessorslotChain...

使用__try...__except和try...catch捕获异常实例分享(附源码)

在C/C++的代码中,为了防止代码块执行的过程中产生异常导致软件崩溃,我们会给代码块添加__try...__except或try...catch保护,防止软件因为操作内部触发的异常产生崩溃。本文简单地介绍一下这两种异常捕获的使用示例。 1、概述 当软件运行过程中代码抛出异常,如果异常没有处…...

基于51单片机的简易温控水杯恒温杯仿真设计( proteus仿真+程序+设计报告+讲解视频)

基于51单片机的简易温控水杯恒温杯仿真设计( proteus仿真程序设计报告讲解视频&#xff09; 仿真图proteus7.8及以上 程序编译器&#xff1a;keil 4/keil 5 编程语言&#xff1a;C语言 设计编号&#xff1a;S0099 1. 主要功能&#xff1a; 基于51单片机的简易温控水杯恒温…...

王德峰视频讲座,王德峰视频全部大全集,百度云百度网盘资源下载

王德峰教授的视频讲座其内容丰富、观点独到&#xff0c;深受广大学者和爱好者的喜爱。很多朋友想下载王德峰教授的讲座视频&#xff0c;今天我给大家分享一个下载王德峰教授视频的方法 搜索 “方圆资源网官网” 打开 “方圆资源网官网&#xff0c;找到王德峰教授的讲座 总之&a…...

Visual Studio和BOM历史渊源

今天看文档无意间碰到了微软对编码格式解释&#xff0c;如下链接&#xff1a; Understanding file encoding in VS Code and PowerShell - PowerShell | Microsoft LearnConfigure file encoding in VS Code and PowerShellhttps://learn.microsoft.com/en-us/powershell/scrip…...

虚拟现实(VR)游戏与增强现实(AR)游戏的区别

随着科技的飞速发展&#xff0c;沉浸式游戏体验已经成为现代娱乐的重要组成部分。虚拟现实&#xff08;VR&#xff09;游戏和增强现实&#xff08;AR&#xff09;游戏是这类体验中的两大主流&#xff0c;但它们在技术实现、用户体验和应用场景上有显著的区别。本文将详细探讨VR…...

git已经设置了自己的账号和密码,提交信息还是别人解决方法

1、运行一下命令缓存输入的用户名和密码&#xff1a; git config --global credential.helper wincred2、重新设置自己的邮箱和用户名 查看配置信息 git config --list修改用户名和邮箱地址&#xff1a; git config --global user.name 你自己的username git config --glo…...

探索面向对象与并发编程的完美融合:Java中的实践与思考

探索面向对象与并发编程的完美融合:Java中的实践与思考 在软件开发的世界里,面向对象编程(OOP)与并发编程(Concurrency)常被视为两个独立的领域。然而,Java语言却将这两个领域无缝地融合在一起,使得面向对象思想能够有效简化并发编程的复杂性。那么,如何才能用面向对…...

探索在线问诊系统的安全性与隐私保护

随着远程医疗的普及&#xff0c;在线问诊系统成为医疗服务的重要组成部分。然而&#xff0c;随着医疗数据的在线传输和存储&#xff0c;患者的隐私保护和数据安全面临巨大挑战。本文将探讨在线问诊系统的安全性与隐私保护&#xff0c;介绍常见的安全措施和技术实现&#xff0c;…...

How To: Localize Bar and Ribbon Skin Items

您可以使用Localizer对象自定义皮肤菜单&#xff0c;而不是迭代每个条形皮肤子菜单项和功能区皮肤库项容器来手动修改这些项。此方法允许您同时自定义所有现有栏子菜单和功能区库中的外观项目。 创建BarLocalizer类的派生类并重写XtraLocalizer.GetLocalizedString方法。 pub…...

通过 urllib 结合代理IP下载文件实现Python爬虫

本教程将向您展示如何使用 Python 的 urllib 库结合代理 IP 来下载文件。这种技术对于避免被目标网站封锁 IP 或简单地从不同的地理位置访问网站特别有用。通过这种方式&#xff0c;您可以更安全地进行网页数据的爬取和分析。 安装必须的库 在开始编写代码之前&#xff0c;您…...

单线服务器与双线服务器的区别?

单线服务器和双线服务器之间有什么区别呢&#xff1f;接下来就让小万来为大家具体分析一下吧&#xff01; 首先单线服务器和双线服务器之间运营商的性质是不同的&#xff0c;单线服务器主要是一家带宽运营商&#xff0c;而双线服务器则是有两家运营商提供带宽的线路。 单线服务…...

使用Hadoop MapReduce实现各省学生总分降序排序,根据省份分出输出到不同文件

使用Hadoop MapReduce实现各省学生总分降序排序&#xff0c;根据省份分出输出到不同文件 本文将展示如何使用Hadoop MapReduce对一组学生成绩数据进行处理&#xff0c;将各省的学生成绩按总分降序排序并按照省份进行分区将结果分别输出到不同的文件中。 数据样例 我们将使用…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...