位图 —— 哈希思想的产物

2024-09-01 12:36
文章标签 哈希 思想 产物

本文主要是介绍位图 —— 哈希思想的产物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1.学习位图的前置知识

计算机中数据存储的单位

C++中数据类型的大小

2.位图的讲解

位图的引出

位图的使用

位图的实现

位图完整代码

3.位图的总结 

位图的优缺点

优点

缺点

1.学习位图的前置知识

计算机中数据存储的单位

想要学习位图，首先要明白什么是位。位指的是比特位，是计算机中存储数据的最小单位，只有0和1两种取值。下面介绍一下计算机中数据存储的单位。

计算机中数据存储的单位从小到大一次是：bit（位）-> Byte（字节） -> KB（千字节） ->MB（兆字节） ->GB（吉字节）。

他们之间的换算关系是：
1 Byte = 8 bits
1 KB = 1024 Bytes
1 MB = 1024 KB
1 GB = 1024 MB

当然，计算机中还有更大的存储单位，这里不作解释。

C++中数据类型的大小

在编程语言中，定义数据时，往往需要先声明其数据类型，以便于编译器编译时，根据类型正确的从内存中取出数据。这是怎么做到的呢？其实啊，这都是编程语言的设计者规定好的了；在C++语言中，语言的内置类型有 bool、char、short、int、long、longlong、float、double等。在32位平台下，这些数据类型占用的内存空间大小如下：

  • bool 类型的数据占用一个字节的空间。
  • char 类型的数据占用一个字节的空间。
  • short 类型的数据占用两个字节的空间。
  • int 类型的数据占用4字节的空间。
  • longlong 类型的数据占用8个字节的空间。
  • float 类型的数据占用4个字节的空间。
  • double类型的数据占用8个字节的空间。

位和字节的示意图如下图所示：

2.位图的讲解

位图的引出

因为数据是由类型的，类型又决定了数据占用多大的内存空间，所以我们存储数据的时候，需要根据数据的大小，合理的使用数据类型，才能更好的使用内存资源。而且，在面对一些数据量特别多的情况下，我们也应该考虑使用占用内存空间小的数据类型解决问题，这就是位图的用武之地。比如下面这个问题：

题目：给40亿个不重复的无符号整数，没排过序；给一个无符号整数，如何快速判断一个数是否在
这40亿个数中？

你可能会想到以下解法：

解法一：放在数组中，直接暴力地遍历查找。时间复杂度为O(N)。

解法二：要查找一个数？嗯，哦哦哦！我们可以使用二分查找。

  • 1.先用一个数组把这四十亿个不重复的、无符号的整数装起来；
  • 2.然后排序，排序可以使用快速排序；
  • 3.排完序之后，再跑一个二分查找；

排序的时间复杂度为O(NlogN)，二分查找时间复杂度为logN。

解法三：利用二叉搜索树结构的容器进行查找。

  • 1.把数据装进set中。
  • 2.调用其接口进行查找。

set的底层数据结构是红黑树，是一种接近平衡的二叉搜索树，最多只需要查找数的高度次，数据的查找效率是O(logN)。

上述解法的效率依次提升，你可能会说：“嗯，不错不错，我真牛批”。但是你别忘了，那可是40亿个无符号整数呀，你电脑的内存装不装的下还是个问题呢。 

我们可以讨论一下，这四十亿个不重复无符号整数需要多大的内存空间？

分析：首先，题目说有四十亿个不重复的、无符号的整数，但是没有告诉我们具体是哪一种的无符号整数类型；要想有四十亿个不重复的数，该数值的数据类型得支持，下面枚举C++中的无符号整数类型。

  1. unsigned int：
    • 字节数：通常为4字节（32位）。
    • 取值范围：从0到2^32 - 1，即0到4,294,967,295。这个范围明显大于四十亿（4,000,000,000），因此unsigned int可以满足要求。
  2. unsigned short：
    • 字节数：通常为2字节（16位）。
    • 取值范围：从0到2^16 - 1，即0到65,535。这个范围远小于四十亿，因此unsigned short不能满足要求。
  3. unsigned long：
    • 字节数：在大多数现代系统上，unsigned long是4字节（32位），但在某些平台（特别是64位系统）上，它可能是8字节（64位）。
    • 取值范围：如果是4字节，取值范围与unsigned int相同，即0到4,294,967,295；如果是8字节，则取值范围更大，远超过四十亿。无论是哪种情况，unsigned long都能满足要求。
  4. unsigned long long：
    • 字节数：通常为8字节（64位）。
    • 取值范围：从0到2^64 - 1，即0到18,446,744,073,709,551,615。这个范围远大于四十亿，因此unsigned long long也能满足要求，但相比unsigned int或4字节的unsigned long，它占用了更多的内存空间。

分析上面的数据类型，我们要想支持40亿个不重复的数，且尽可能的节省空间，我们的最佳选择是unsigned int类型，该类型的数据在32位平台下占用4字节，也就是8个比特位。1G大约为10亿个字节，40亿个无符号整数大约占用160亿个字节，也就是大约16G的内存空间。可以设想，光跑这一个程序就要16G的内存空间，其他程序还怎么玩呀？

位图的使用

所以使用上面的三种解法都不靠谱，这个时候，我们有了计算机中存储单位的前置知识，我们自然而然的就想要用最小的单位 bit 来表示数据的存储了，但是bit只有个两种取值，0和1；这可怎么办呢？

学过逻辑数学的朋友都知道，逻辑电路中，通常使用0和1来表示两种状态，我们这里也是一样的，我们可以用1表示数据存在，用0表示数据不存在；还是这个题目。

题目：给40亿个不重复的无符号整数，没排过序；给一个无符号整数，如何快速判断一个数是否在
这40亿个数中？

题目只要求我们判断一个数在不在，在和不在，不就是两种状态吗？哦，感觉有戏。不要忘记，题目中说的是40亿个不重复的数；结合哈希的思想，如果一个数可以映射一个bit位，数据和位置之间不就建立了一 一 映射的关系了吗？所以我们现在的重点是，数据如何与位置之间建立一 一 映射关系？

一个数据映射一个比特位，我们就需要40亿个比特位，大约是4GB，大部分的电脑是能满足这个需求的。因为数据是不重复的，我们完全可以将数据 和 不同的比特位映射起来，具体做法如下：

  • 数据的值是666，就映射第666个比特位，数据的值是888，就映射第888个比特位。
  • 当我们需要判断一个数是否存在时，直接根据元素的值计算出元素所映射的bit位。
  • 通过判断该bit位是否为1，从而确定元素是否存在。

位图的实现

下面讲解位图这种数据结构的实现，相信看完之后，对位图的理解会更上一层楼！

成员变量设计图如下图所示：

我们采用采用一个vector，vector中装的是int类型的数据。

操作数据的成员方法有三个：

  • void set(size_t x)：把数据x映射的位标记为1。
  • void reset(size_t x)：把数据x映射的位标记为0。
  • bool test(size_t x)：判断数据x是否存在。

void set(size_t x)的实现：set函数用来将数据x映射的比特位标记为1。为了实现这个功能，我们分为以下三步。

1.计算出数据x在位图中的第几个整形数据中；

  • 一个整形数据占用4个字节，也就是32个bit位；使用数据x对32做除法，即可计算出该数据在第几个整形数据中。

2.计算出数据x在该整形数据的第几个bit位中；

  • 想要计算出该数据在整形数据中的第几个bit位，我们可以对32进行取余操作。

3.将该bit位置为1。

比如：我们想要将下图中的第i个bit位置为1，我们可以利用1的特性 —— 最低位位1，其他位全为0。进行这两步操作 ：

a、将1移到第i个bit位的下方，示意图如下所示：

b、然后让二者进行按位或操作（两个bit位进行按位或操作，有1则1），示意图如下所示：

这样一来，我们就将第i个bit位置为1了。 

set方法代码如下：

		// 将该数据映射的位置设为1 void set(size_t x){// 比如：25 应该映射在第25个比特位上// 1.计算在第几个整形上size_t i = x / 32;// 2.计算该整形的第几个比特位上size_t j = x % 32;_bitset[i] |= 1 << j; // 左移是往 高位移，右移是往 低位移}

void reset(size_t x)的实现：reset()函数用于将数据x映射的bit位标记为0，为了实现这个功能，我们也可以分为三步走。

1.确定该数据在位图中的第几个整形数据中。

2.确定该数据在整形数据中的第几个bit位中。

3.将该bit位置为0。

前面两步和set()的前两步是一模一样的，具体实现过程参考前面的set方法。所以我们只需要学习如何将第i个bit位置为0。

想要将第i个bit位置为0，我们同样可以借助1来完成，当我们把1移到第i个bit位的下方之后，我们可以通过如下两步操作将第i个bit位置0。

a、将1进行按位取反操作，如下图所示：

b、和第i个bit位进行按位与操作，如下图所示：

reset方法代码如下：

		// 将该数据映射的位置设为0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bitset[i] &= ~(1 << j);}

bool test(size_t x)方法的实现：test方法用于检测第x个bit位是否为1，也就是判读数据x是否存在；要想实现这个功能，我们只需要实现以下三步。

1.确定该数据在位图中的第几个整形数据中。

2.确定该数据在整形数据中的第几个bit位中。

3.取出位图中第i个bit位的值。

没错，这三个接口的前面两步都是一样的，所以我们的目标就是弄懂第三步是怎么实现的。

要想实现第三步，我们还是可以借助1来完成；当我们把1移到位图中第i个bit位的下方之后，我们只需要返回两个bit位进行按位与操作的结果即可，因为C++中用0表示假，非0表示真，因此，0和1可以直接做逻辑条件判断。

如果位图中第i个bit位的值为0，和1进行按位与操作之后，结果还是0；如下图所示：

如果位图中第i个bit位的值为1，和1进行按位与操作之后，结果还是1；如下图所示：

test方法代码如下：

		// 判断该数据是否存在bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bitset[i] & (1 << j);}

位图完整代码

附上一份位图的完整代码：

template<size_t N>// 位图空间开多大，不取决于要处理的数据个数，而是取决于数据的范围class BitSet{public:BitSet(){_bitset.resize(N / 32 + 1); // N是要开的比特位的个数，转换成对应的整形的个数}// 将该数据映射的位置设为1 void set(size_t x){// 比如：25 应该映射在第25个比特位上// 1.计算在第几个整形上size_t i = x / 32;// 2.计算该整形的第几个比特位上size_t j = x % 32;_bitset[i] |= 1 << j; // 左移是往 高位移，右移是往 低位移}// 将该数据映射的位置设为0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bitset[i] &= ~(1 << j);}// 判断该数据是否存在bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bitset[i] & (1 << j);}private:std::vector<int> _bitset;};

3.位图的总结 

位图其实就是将计算机中最小的存储单位 bit位 和 哈希 思想结合实现的一种数据结构，用每一位来存放某种状态，适用于海量数据，数据无重复的场景，通常是用来判断某个数据存不存在的。

位图的优缺点

优点

  1. 空间效率高：由于每个元素只需要一个bit来表示，因此位图能够极大地节省存储空间。与使用整数或字符数组相比，位图在表示大量布尔值时具有显著的空间优势。

  2. 查询速度快：位图支持快速的查询操作。由于元素以位的形式存储，通过索引直接访问位数组，可以在O(1)时间复杂度内查询某个元素是否存在。这对于处理大规模数据集合非常有效。

  3. 去重和快速统计：位图可以高效地用于数据去重和统计。在处理大量数据时，可以快速判断一个数据是否已经出现过，并统计出每个元素的频率。

  4. 数据压缩：对于只有两种状态的数据（如布尔值），使用位图可以极大地减少存储空间，实现高效的数据压缩。

缺点

  1. 数据类型限制：位图一般只能处理整形数据，如果内容编号是字符串或其他非整形类型，就无法直接使用位图进行处理。这限制了位图的适用范围。

  2. 功能限制：位图主要用于表示元素是否存在某个集合中，对于需要存储复杂数据或进行复杂查询的应用场景，位图可能不是最佳选择。

  3. 稀疏数据问题：如果元素值范围很大但实际值很稀疏，那么位图可能会浪费大量的空间。因为，位图需要为所有可能的元素值分配空间，即使某些值在数据集中并不存在。

这篇关于位图 —— 哈希思想的产物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1126949。

相关文章

哈希leetcode-1

哈希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
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
函数式编程思想

函数式编程思想

我们经常会用到各种各样的编程思想，例如面向过程、面向对象。不过笔者在该博客简单介绍一下函数式编程思想. 如果对函数式编程思想进行概括，就是f(x) = na(x) , y=uf(x)…至于其他的编程思想，可能是y=a(x)+b(x)+c(x)…，也有可能是y=f(x)=f(x)/a + f(x)/b+f(x)/c… 面向过程的指令式编程 面向过程，简单理解就是y=a(x)+b(x)+c(x)
阅读更多...
哈希表的底层实现(1)---C++版

哈希表的底层实现(1)---C++版

目录 哈希表的基本原理 哈希表的优点 哈希表的缺点 应用场景 闭散列法 开散列法 开放定值法Open Addressing——线性探测的模拟实现 超大重点部分评析 链地址法Separate Chaining——哈希桶的模拟实现 哈希表（Hash Table）是一种数据结构，它通过将键（Key）映射到值（Value）的方式来实现快速的数据存储与查找。哈希表的核心概念是哈希
阅读更多...
哈希表的封装和位图

哈希表的封装和位图

文章目录 2 封装2.1 基础框架2.2 迭代器(1)2.3 迭代器(2) 3. 位图3.1 问题引入3.2 左移和右移？3.3 位图的实现3.4 位图的题目3.5 位图的应用 2 封装 2.1 基础框架 文章 有了前面map和set封装的经验，容易写出下面的代码 // UnorderedSet.h#pragma once#include "HashTable.h"
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
PHP: 深入了解一致性哈希

PHP: 深入了解一致性哈希

前言 随着memcache、redis以及其它一些内存K/V数据库的流行，一致性哈希也越来越被开发者所了解。因为这些内存K/V数据库大多不提供分布式支持(本文以redis为例)，所以如果要提供多台redis server来提供服务的话，就需要解决如何将数据分散到redis server，并且在增减redis server时如何最大化的不令数据重新分布，这将是本文讨论的范畴。 取模算法 取模运
阅读更多...
哈希表题总结

哈希表题总结

哈希表题总结 hot100两数之和字母异位词分组最长连续序列 hot100 两数之和 题目链接： 1.两数之和 代码： class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer,Integer> map = new HashMap<>();int n = nums.length;for
阅读更多...
【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念？

【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念？

大家好，我是锋哥。今天分享关于 【说说 Redis 哈希槽的概念？】面试题，希望对大家有帮助； 说说 Redis 哈希槽的概念？ Redis 集群没有使用一致性 hash,而是引入了哈希槽的概念，Redis 集群有 16384 个哈希槽，每个 key 通过 CRC16 校验后对 16384 取模来决定放置哪个槽， 集群的每个节点负责一部分 hash 槽。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2