当前位置: 首页 > 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;将各省的学生成绩按总分降序排序并按照省份进行分区将结果分别输出到不同的文件中。 数据样例 我们将使用…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...