和朋友聊天，说到了大数据存储和查找方式，朋友提到了「位图」。结果我满脑子都是「位图-矢量图」，「矢量图-位图」。难道此「位图」非彼「位图」？

一、此「位图」非彼「位图」

 

为什么会有这样的疑惑，那是因为：位图可能是一种图片类型，也可能是数据结构的 bitmap。我们会逐一来剖析位图，从这两个角度入手，全面掌握位图概念。

技术是一个很微妙的东西，一旦你发现它，就会无意的捕捉到更多点点滴滴。

二、位图

 

位图，又称为点阵图像、像素图或栅格图像，是由像素（图片米素）的单个点组成。这些点可以进行不同的排列和染色以构成图样。

位图的单位：像素（Pixel）

像素（Pixel）：指可以表现亮度甚至色彩变化的一个点，是构成数字图像的最小单位。像素具有大小相同、明暗和颜色的变化。特点是有固定的位置和特定的颜色值。

位图有以下特点：

1.位图图像善于重现颜色的细微层次，能够制作出色彩和亮度变化丰富的图像；

2.文件庞大，不能随意缩放；

3.打印和输出的精度是有限的；

4.图形面积越大，文件的字节数越多；

5.文件的色彩越丰富，文件的字节数越多。

位图的文件类型很多，如：

*.bmp、*.pcx、*.gif、*.jpg、*.tif*.psd、kodak photo*.pcd、corel photo*.cpt

三、矢量图

 

我们再来看看矢量图：矢量又称为「向量」，矢量图形中的图形米素（点和线段）称为对象，每个对象都是一个单独的个体，它具有大小、方向、轮廓、颜色和屏幕位置等属性。

简单地说，矢量图形软件就是用数学的方法来绘制矩形等基本形状。

矢量图有以下特点：

1.矢量图形能重现清晰的轮廓，线条非常光滑、且具有良好的缩放性；

2.因为图像中保存的是线条和图块的信息，与分辨率和图形大小无关，只与图像的复杂程度有关，所以图像文件所占的存储空间交较小；

3.文字编辑能力强；

4.与位图相比，在显示和打印方面都快的多；

5.缺点就是图形不真实，颜色不生动；

大概格式有：

*.cdr、*.AI、*.EPS、*.dwg、*.wmf、*.emf

通过软件，矢量图可以轻松地转化为位图。

而位图转化为矢量图就需要经过复杂而庞大的数据处理，而且生成的矢量图的质量绝对不能和原来的图形比拟。

四、位图的存储格式

 

因为本文主旨是位图，所以我们着重来写写位图。

我们知道，每张图按大小来存储，即图像的长宽像素大小。如果一张图片的像素是 100*100，则此图像在内存的存放是一个100*100 的数组，每个数组的米素是 int 整型（整数占用 4 个 byte）。

需要补充一些知识：数组中每个米素中整型数字含四位信息：R-G-B-A。

1.R: 存放 Red 红色通道（占一个 byte 取值 0~255）

2.G: Green 绿色通道色（占一个 byte 取值 0~255 ）

3.B: Blue 蓝色通道（占一个 byte 取值 0~255 ）

4.A：Alpha 通道值，即该位置像素点的透明值(占一个 byte 取值 0~255）

其中 RGB 又是自然界三原色，通过 RGB 的组合可以将任何色彩表示出来。

我们举一个例子，假设有如下数组：

{0xffff0000,0xffff0000,0xffff0000,0xffff0000},{0xffff0000,0xffff0000,0xffff0000,0xffff0000},{0xffff0000,0xffff0000,0xffff0000,0xffff0000},{0xffff0000,0xffff0000,0xffff0000,0xffff0000},

表示这是一张 4*4 像素大小的全红色的图。一个像素在屏幕上显示出来非常小，当多个不同的像素按规律摆放在一起形成有行有列的数组的时候，我们就看到了图像。

Png 和 Jpeg 等图像都是在这种方法的基础上加入了压缩算法，方便人们携带和存储。

五、如何计算

 

看完上面的解释，这时候我们有了大概的认识，你一定好奇图片大小是如何计算的呢？

一张图片（BitMap）占用的内存 = 图片长度 * 图片宽度 * 单位像素占用的字节数

注：图片长度和图片宽度的单位是像素。

1.为了形象说明，我们举个例子：一个 32 位的 PNG，像素是 1204*1024 ，那么占用空间是：

1024*1024*(32/8)

因为 8 bit = 1 byte，32 位就是 4 byte。

2.这里补充一下字节的概念：字节（Byte /bait/ n. [C]）是计算机信息技术用于计量存储容量的一种计量单位，通常情况下一字节等于八位，也表示一些计算机编程语言中的数据类型和语言字符。

六、面试题：100*100 的 canvas 占多少内存？

 

无独有偶，在掘金上面看到了这样一个面试题，作者是这么解说的：

我们在定义颜色的时候就是使用 rgba(r,g,b,a) 四个维度来表示，而且每个像素值就是用十六位 00-ff 表示，即每个维度的范围是 0~255，即 2^8 位，即 1 byte, 也就是 Uint8 能表示的范围。所以 100 * 100 canvas 占的内存是 100 * 100 * 4 bytes = 40,000 bytes。

这和我们上面说到的原理差不多，再回顾一下：如果一张图片的像素是 100*100，则此图像在内存的存放是一个100*100 的数组，每个数组的米素是 int 整型（整数占用 4 个 byte ）。

想起高中时代老师经常黑我们的一句话，把如图一改成如图二，你们就不会做题了。

七、扩展：数码相机原理

 

数码相机中所谓的支持 500W 像素就是这个意思，代表它能处理多大的图形色彩信息的能力，像素越高，需要处理时间越长，因为数组很大。

我们说的 500W 像素，就是由 500W 个这样的方块组成。像素点的尺寸是不一定的。

1.我们举个简单例子：

假设有一台 500W 像素的数码相机拍摄的图片，这张图片的实际容量是 500万X3=1500万=15兆 ，为什么乘以 3 呢？因为数码相机中的感光 ccd 是通过红、绿、蓝三色通道，所以最终图像容量就要乘以 3。

如果对对图片的要求非常高，那么可以采用 tiff 格式存储，那么这台 500W 像素的相机拍出的实际容量为 15M 的图片在文件列表中显示的文件大小也就是 15M 了。

2.为什么计算出来的图片占用内存和实际图片尺寸大小不一致？

• 内存的数据和文件的数据不一样，内存主要是解码后的每个点的数据；
• 文件数据要看你的格式、压缩比、文件头、附加信息等等；

因此文件数据和图片在内存中的数据差别可能会很大。

八、数据结构之位图（bitmap）

 

位图bitmap 是一种非常常用的结构，在索引，数据压缩等方面有广泛应用。

所谓的 bitmap 就是用一个 bit 位来标记某个米素对应的 value， 而 key 即是该米素。由于采用了 bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

来看一个具体的例子，假设我们要对 0-7 内的 5 个米素 (4,7,2,5,3) 排序（这里假设这些米素没有重复）。那么我们就可以采用 bitmap 的方法来达到排序的目的。

文中给出了使用 bitmap 进行排序的算法思路，感兴趣的同学可以移步：什么是Bit-map？

九、场景分析

1.先看看这样的一个场景：给一台普通 PC，2G 内存，要求处理一个包含 40 亿个不重复并且没有排过序的无符号的 int 整数，给出一个整数，问如果快速地判断这个整数是否在文件 40 亿个数据当中？

2.问题思考：

40 亿个 int 占 (40亿*4)/1024/1024/1024 大概为 14.9G 左右，很明显内存只有 2G ，放不下，因此不可能将这 40 亿数据放到内存中计算。

要快速的解决这个问题最好的方案就是将数据搁内存里，所以现在的问题就在如何在 2G 内存空间以内存储着 40 亿整数。一个 int 整数占 4 个字节的即要 32bit 位，如果能够用一个 bit 位来标识一个 int 整数那么存储空间将大大减少。

算一下 40 亿个 int 需要的内存空间为 40亿/8/1024/1024 大概为 476.83MB，这样的话我们完全可以将这 40 亿个 int 数放到内存中进行处理。

3.具体思路：

1 个 int 占 4 字节即 4*8=32位 ，那么我们只需要申请一个 int 数组长度为 int tmp[1+N/32] 即可存储完这些数据，其中 N 代表要进行查找的总数，tmp 中的每个米素在内存在占 32 位可以对应表示十进制数 0~31 ,所以可得到 bitmap 表:

tmp[0]:可表示 0~31tmp[1]:可表示 32~63tmp[2]可表示 64~95.......

4.那么接下来就看看十进制数如何转换为对应的 bit 位：

假设这 40 亿 int 数据为：6,3,8,32,36,......，那么具体的 BitMap 表示为：

 

5.如何判断 int 数字在 tmp 数组的哪个下标，这个其实可以通过直接除以 32 取整数部分，例如：整数 8 除以32 取整等于 0，那么 8 就在 tmp[0]上。另外，我们如何知道了 8 在 tmp[0] 中的 32 个位中的哪个位，这种情况直接 mod 上 32 就 ok ，又如整数 8 ，在 tmp[0] 中的第 8 mod 上 32 等于 8，那么整数 8 就在 tmp[0] 中的第八个 bit 位（从右边数起）。

具体算法可以查看此篇文章，很清晰：海量数据解决思路之 BitMap

其实 bitmap 的应用场景远远不止点，比如还可以用于压缩、爬虫系统中 url 去重、解决全组合问题。可能有些人觉得bitmap 算法实现起来有点麻烦，其实某些语言是对 bitmap 算法进行了封装的，比如 java 中对应 bitmap 的数据结构就有 bitset 类。

十、海量数据解决思路

 

《数据结构：位图法》这篇文章中提到几个解决海量数据的思路：

1.给40亿个不重复的 unsigned int 的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那 40 亿个数当中？

思路：首先，将这 40 亿个数字存储到 bitmap 中，然后对于给出的数，判断是否在 bitmap 中即可。

2.使用位图法判断整形数组是否存在重复？

答：遍历数组，一个一个放入 bitmap，并且检查其是否在 bitmap 中出现过，如果没出现放入，否则即为重复的米素。

3.如何使用位图法进行整形数组排序？

答：首先遍历数组，得到数组的最大最小值，然后根据这个最大最小值来缩小 bitmap 的范围。这里需要注意对于 int 的负数，都要转化为 unsigned int 来处理，而且取位的时候，数字要减去最小值。

4、在 2.5 亿个整数中找出不重复的整数？（注：内存不足以容纳这 2.5 亿个整数）

参考的一个方法是：采用 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现一次，10 表示多次，11 无意义）。其实，这里可以使用两个普通的 Bitmap，即第一个 Bitmap 存储的是整数是否出现，如果再次出现，则在第二个 Bitmap 中设置即可。这样的话，就可以使用简单的 1-Bitmap 了。

数据结构-位图法这篇文章对位图法分析非常到位，而且有更多的应用场景，强烈推荐。

十一、扩展：计算机 32 位和 64 位操作系统

 

1.先明确一下概念：

其实我们说的 32 位和 64 位，指的是 CPU 每一次处理多少位的数据。对于 32 位 CPU，其一次只能处理 32 位（即 4 个字节）的数据；

而 64 位 CPU 一次可以处理 64 位（即 8 个字节）的数据。从处理数据的能力方面来看，64 位是 32 位的两倍，64 位要比 32 位好。

2.特点

• 64 位 CPU 拥有更大的寻址能力，最大支持到 16GB 内存，而 32 位只支持 4G 内存；
• 64 位 CPU 一次可提取 64 位数据，比 32 位提高了一倍，理论上性能会提升 1 倍。但这是建立在 64 位操作系统，64 位软件的基础上的。
• 64 位操作系统的设计初衷是为了满足机械设计和分析、三维动画、视频编辑和创作，以及科学计算和高性能计算应用程序等领域中需要大量内存和浮点性能的客户需求，而 32 位系统，初期并没有考虑太多。

3.原理

8 位处理器、16 位处理器、32 位处理器和 64 位处理器，其计数都是 8 的倍数。

它表示一个 32 位、64 位处理器区别时钟周期里，处理器处理的二进制代码数。0 和 1 就是二进制代码，线路上有电信号，则计做 1 ,没有电信号则为 0 。8 位机有 8 条线路，每个时钟周期有 8 个电信号，组成一个字节。

所以，随 8 位处理器上升至 64 位处理器，每个时钟周期传送 1 个字节到 8 个字节，关联到时钟速度提高到若干个千兆赫之后，处理器处理信息的能力越来越大。

十、参考

1.图片占用内存计算方法

2.数据结构：位图法

3.百科

4.图片的存储原理

5.32 位和 64 位操作系统

6.64位计算