从位图结构开始学内存的计算

目录

• 位图的定义
  
• 实践-40亿个QQ号在2G内存去重
  

今天发现从认识位图（Bitmap）结构，可以很好梳理底层的计算机内存结构基础。那就先来认识内存的计算单位：
内存可以比喻成一张巨大的Excel 表格，表格里可以需要划分一些边界才好使用，就需要用到划分边界的存储单位。
存储单位分为：
Bit、Byte、KB、MB、GB、......
存储单位间以2的10次方 = 1024 作为进率;

• Bit (位) (b)：计算机存储信息的最小单位（也是计算机最基础的单位），可以存储的值为 0 或 1。
  
• Byte (字节) (B)：基本存储单位，1 Byte = 8 bits。
  
  
  
  
• KB (千字节) (Kilobyte)：1 KB = 1024 Bytes。
  
• MB (兆字节) (Megabyte)：1 MB = 1024 KB。
  
• GB (吉字节) (Gigabyte)：1 GB = 1024 MB。
  

32位 和 64位计算机的区别：
我们说的 32 位和 64 位计算机，指的是 CPU 每一次可以处理多少位的数据；

好！基础的内存存储单位复习就到这里。
位图的定义

一种高效的数据结构，使用一串二进制位 (0/1) 来表示大量数据的存在状态，以极节省内存来快速判断数据是否在集合中。简而言之，它可以是图像（像素点阵），也可以是记录状态（位序列）的高效数据集合；
比如：

上图只用了 32位=4字节 就表示了一个用户一个月的全部登录记录。
记录方式为：如果登录了系统，那么对应天数的那个bit就设置为1，否则为0。一个月恰好是连续的31天：
实践-40亿个QQ号在2G内存去重

问题：一台 2G 内存电脑，要求处理 40 亿个无序10位的QQ号，如何快速去重？
我们先看看存储进内存需要多少内存空间：
一个10位的QQ号：1234567890，需要34位来存储，那么40亿个就是：
34 * 40亿  = 136000000000（Bits）;
136000000000 / (1024*1024*1024)  ≈ 126 (GB);
126G数据是装不进2G内存的。所以想进内存在开始计算的方案都行不通。考虑其他办法吧。
方案二：
以QQ号"9076072220"为例，我们可以按照以下步骤将其放入位图中:

• 确定位置： 找到对应的位图位置。对于QQ号"9076072220"，我们将其作为索引9076072220；
  
• 设置位： 将该位置设置为1，表示该QQ号存在。
  

通过这种方式，将所有QQ号放入位图后，所有值为1的位置表示存在，不为1的位置表示不存在。对于相同的QQ号，只需设置一次1，因此可以有效地完成去重。

然后计算需要多少内存空间：
4,000,000,000 bits ÷ 8 bits/Byte = 500,000,000 Bytes (字节)
500,000,000 Bytes ÷ 1024 (Bytes/KB) ≈ 488,281 KB
488,281 KB ÷ 1024 (KB/MB) ≈ 476.8 MB
哇！只需要不到500M的空间就可以搞定，相比而已，很省空间了。
时间复杂度：O(n+j)，n 为范围，j为记录数（上图的34位记录），都是常数：所以O(1)，非常快。
这个方案简单易懂，高效且低空间。
当然还有其他方案，比如Hash，这里不继续了，Bye.

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！