【C++】哈希应用之位图

2024-03-26 12:36
文章标签 c++ 应用 哈希 之位

本文主要是介绍【C++】哈希应用之位图,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

👀樊梓慕:个人主页

 🎥个人专栏:《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子,都是对生命的辜负


目录

前言

1.位图的概念

2.位图的模拟实现

2.1构造

2.2set

2.3reset

2.4test

3.源码

4.位图应用变形 


前言

哈希是一种解决问题的思想,那么有关哈希的一个重要应用便是位图,该种结构适用于海量数据,数据无重复的场景,通常用来判断某个数据存在或者不存在,但只能处理整型数据。


欢迎大家📂收藏📂以便未来做题时可以快速找到思路,巧妙的方法可以事半功倍。 

=========================================================================

GITEE相关代码:🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================


1.位图的概念

我们以一道面试题引入:

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

---『 腾讯』

根据题意,给定40亿个数,很明显如果是40亿个整型,1GB=10亿byte,40亿个整型=160亿byte=16GB,内存中根本放不下,那么这道题关键就在于只需要判断这个数是否在,所以我们仅需一个『 比特位』就可以表示某个数的状态,如果二进制比特位为1,代表存在,为0代表不存在。

而无符号整数总共有2^32个,因此我们仅需2^32个比特位=512M的内存空间就可以判断一个数是否在。

这种思想就是利用了哈希应用中的位图。


2.位图的模拟实现

很明显,位图的底层就是数组,那么我们就选用vector来当作底层容器。

2.1构造

在构造位图时,我们需要根据所给位数N,创建一个N位的位图,并且将该位图中的所有位都初始化为0。

一个整型有32个比特位,因此N个位的位图就需要用到N/32个整型,但是实际我们所需的整型个数是N/32+1,因为所给非类型模板参数N的值可能并不是32的整数倍。

例如,当N为40时,我们需要用到两个整型,即40/32+1=2。

//构造函数
bitset()
{_bits.resize(N / 32 + 1, 0);
}

2.2set

set用于设置位,即设置某个数为存在,所处位设置为1。

设置位图中指定的位的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行或运算即可。

//设置位
void set(size_t pos)
{assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] |= (1 << j); //将该位设置为1(不影响其他位)
}

2.3reset

reset用于清空位,即设置某个数为不存在,所处位设置为0。

清空位图中指定的位的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位再整体反转后与第 i 个整数进行与运算即可。

//清空位
void reset(size_t pos)
{assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] &= (~(1 << j)); //将该位设置为0(不影响其他位)
}

2.4test

test用于检验位,即判断某个数是否存在,检验所处位设置的值。

获取位图中指定的位的状态的方法如下:

  1. 计算出该位位于第 i 个整数的第 j 个比特位。
  2. 将1左移 j 位后与第 i 个整数进行与运算得出结果。
  3. 若结果非0,则该位被设置,否则该位未被设置。

//获取位的状态
bool test(size_t x)
{assert(x <= N);//算出pos映射的位在第i个整数的第j个位size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);
}

3.源码

#pragma once
namespace bit_set
{template<size_t N>class bitset{public:bitset(){_bits.resize(N / 32 + 1, 0);}//设置位void set(size_t pos){assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] |= (1 << j); //将该位设置为1(不影响其他位)}//清空位void reset(size_t pos){assert(pos < N);//算出pos映射的位在第i个整数的第j个位int i = pos / 32;int j = pos % 32;_bits[i] &= (~(1 << j)); //将该位设置为0(不影响其他位)}        bool test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};
}

4.位图应用变形 

问:1个文件有100亿个int,1G内存,设法找到出现次数不超过2次的所有整数。

这种问题很明显就是利用位图来解决,可是前面的问题我们只需要一个比特位就能标识出一个数字是否存在。

那么这个问题呢?

我们可以设想为3种状态,出现0次、出现1次、出现2次、出现3次及以上。

分别用如下数字标识:

出现0次:00

出现1次:01

出现2次:10

出现3次及以上:11

所以设计结构如下:

namespace two_bit_set
{template<size_t N>class two_bit_set{public:void set(size_t x){// 00 -> 01if (_bs1.test(x) == false&& _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false&& _bs2.test(x) == true){// 01 -> 10_bs1.set(x);_bs2.reset(x);}}bool test(size_t x){if (_bs1.test(x) == false&& _bs2.test(x) == true){return true;}return false;}private:bitset<N> _bs1;bitset<N> _bs2;};
}

给定两组数据找交集,我们也可以通过双位图这种思想实现。


=========================================================================

如果你对该系列文章有兴趣的话,欢迎持续关注博主动态,博主会持续输出优质内容

🍎博主很需要大家的支持,你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏+关注 ~🌟

=========================================================================

这篇关于【C++】哈希应用之位图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/848527

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#