和朋友聊天，說(shuō)到了大數據存儲和查找方式，朋友提到了「位圖」。結果我滿(mǎn)腦子都是「位圖-矢量圖」，「矢量圖-位圖」。難道此「位圖」非彼「位圖」？

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

為什么會(huì )有這樣的疑惑，那是因為：位圖可能是一種圖片類(lèi)型，也可能是數據結構的 bitmap。我們會(huì )逐一來(lái)剖析位圖，從這兩個(gè)角度入手，全面掌握位圖概念。

技術(shù)是一個(gè)很微妙的東西，一旦你發(fā)現它，就會(huì )無(wú)意的捕捉到更多點(diǎn)點(diǎn)滴滴。

二、位圖

位圖，又稱(chēng)為點(diǎn)陣圖像、像素圖或柵格圖像，是由像素（圖片元素）的單個(gè)點(diǎn)組成。這些點(diǎn)可以進(jìn)行不同的排列和染色以構成圖樣。

位圖的單位：像素（Pixel）

像素（Pixel）：指可以表現亮度甚至色彩變化的一個(gè)點(diǎn)，是構成數字圖像的最小單位。像素具有大小相同、明暗和顏色的變化。特點(diǎn)是有固定的位置和特定的顏色值。

位圖有以下特點(diǎn)：

1.位圖圖像善于重現顏色的細微層次，能夠制作出色彩和亮度變化豐富的圖像；

2.文件龐大，不能隨意縮放；

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

4.圖形面積越大，文件的字節數越多；

5.文件的色彩越豐富，文件的字節數越多。

位圖的文件類(lèi)型很多，如：

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

三、矢量圖

我們再來(lái)看看矢量圖：矢量又稱(chēng)為「向量」，矢量圖形中的圖形元素（點(diǎn)和線(xiàn)段）稱(chēng)為對象，每個(gè)對象都是一個(gè)單獨的個(gè)體，它具有大小、方向、輪廓、顏色和屏幕位置等屬性。

簡(jiǎn)單地說(shuō)，矢量圖形軟件就是用數學(xué)的方法來(lái)繪制矩形等基本形狀。

矢量圖有以下特點(diǎn)：

1.矢量圖形能重現清晰的輪廓，線(xiàn)條非常光滑、且具有良好的縮放性；

2.因為圖像中保存的是線(xiàn)條和圖塊的信息，與分辨率和圖形大小無(wú)關(guān)，只與圖像的復雜程度有關(guān)，所以圖像文件所占的存儲空間交較??；

3.文字編輯能力強；

4.與位圖相比，在顯示和打印方面都快的多；

5.缺點(diǎn)就是圖形不真實(shí)，顏色不生動(dòng)；

大概格式有：

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

通過(guò)軟件，矢量圖可以輕松地轉化為位圖。

而位圖轉化為矢量圖就需要經(jīng)過(guò)復雜而龐大的數據處理，而且生成的矢量圖的質(zhì)量絕對不能和原來(lái)的圖形比擬。

四、位圖的存儲格式

因為本文主旨是位圖，所以我們著(zhù)重來(lái)寫(xiě)寫(xiě)位圖。

我們知道，每張圖按大小來(lái)存儲，即圖像的長(cháng)寬像素大小。如果一張圖片的像素是 100*100，則此圖像在內存的存放是一個(gè)100*100 的數組，每個(gè)數組的元素是 int 整型（整數占用 4 個(gè) byte）。

需要補充一些知識：數組中每個(gè)元素中整型數字含四位信息：R-G-B-A。

1.R: 存放 Red 紅色通道（占一個(gè) byte 取值 0~255）

2.G: Green 綠色通道色（占一個(gè) byte 取值 0~255 ）

3.B: Blue 藍色通道（占一個(gè) byte 取值 0~255 ）

4.A：Alpha 通道值，即該位置像素點(diǎn)的透明值(占一個(gè) byte 取值 0~255）

其中 RGB 又是自然界三原色，通過(guò) RGB 的組合可以將任何色彩表示出來(lái)。

我們舉一個(gè)例子，假設有如下數組：

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

表示這是一張 4*4 像素大小的全紅色的圖。一個(gè)像素在屏幕上顯示出來(lái)非常小，當多個(gè)不同的像素按規律擺放在一起形成有行有列的數組的時(shí)候，我們就看到了圖像。

Png 和 Jpeg 等圖像都是在這種方法的基礎上加入了壓縮算法，方便人們攜帶和存儲。

五、如何計算

看完上面的解釋?zhuān)@時(shí)候我們有了大概的認識，你一定好奇圖片大小是如何計算的呢？

一張圖片（BitMap）占用的內存 = 圖片長(cháng)度 * 圖片寬度 * 單位像素占用的字節數

注：圖片長(cháng)度和圖片寬度的單位是像素。

1.為了形象說(shuō)明，我們舉個(gè)例子：一個(gè) 32 位的 PNG，像素是 1204*1024 ，那么占用空間是：

1024*1024*(32/8)

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

2.這里補充一下字節的概念：字節（Byte /bait/ n. [C]）是計算機信息技術(shù)用于計量存儲容量的一種計量單位，通常情況下一字節等于八位，也表示一些計算機編程語(yǔ)言中的數據類(lèi)型和語(yǔ)言字符。

六、面試題：100*100 的 canvas 占多少內存？

無(wú)獨有偶，在掘金上面看到了這樣一個(gè)面試題，作者是這么解說(shuō)的：

我們在定義顏色的時(shí)候就是使用 rgba(r,g,b,a) 四個(gè)維度來(lái)表示，而且每個(gè)像素值就是用十六位 00-ff 表示，
即每個(gè)維度的范圍是 0~255，即 2^8 位，即 1 byte, 也就是 Uint8 能表示的范圍。
所以 100 * 100 canvas 占的內存是 100 * 100 * 4 bytes = 40,000 bytes。

這和我們上面說(shuō)到的原理差不多，再回顧一下：如果一張圖片的像素是 100*100，則此圖像在內存的存放是一個(gè)100*100 的數組，每個(gè)數組的元素是 int 整型（整數占用 4 個(gè) byte ）。

想起高中時(shí)代老師經(jīng)常黑我們的一句話(huà)，把如圖一改成如圖二，你們就不會(huì )做題了。

七、擴展：數碼相機原理

數碼相機中所謂的支持 500W 像素就是這個(gè)意思，代表它能處理多大的圖形色彩信息的能力，像素越高，需要處理時(shí)間越長(cháng)，因為數組很大。

我們說(shuō)的 500W 像素，就是由 500W 個(gè)這樣的方塊組成。像素點(diǎn)的尺寸是不一定的。

1.我們舉個(gè)簡(jiǎn)單例子：

假設有一臺 500W 像素的數碼相機拍攝的圖片，這張圖片的實(shí)際容量是 500萬(wàn)X3=1500萬(wàn)=15兆 ，為什么乘以 3 呢？因為數碼相機中的感光 ccd 是通過(guò)紅、綠、藍三色通道，所以最終圖像容量就要乘以 3。

如果對對圖片的要求非常高，那么可以采用 tiff 格式存儲，那么這臺 500W 像素的相機拍出的實(shí)際容量為 15M 的圖片在文件列表中顯示的文件大小也就是 15M 了。

2.為什么計算出來(lái)的圖片占用內存和實(shí)際圖片尺寸大小不一致？

內存的數據和文件的數據不一樣，內存主要是解碼后的每個(gè)點(diǎn)的數據；文件數據要看你的格式、壓縮比、文件頭、附加信息等等；

因此文件數據和圖片在內存中的數據差別可能會(huì )很大。

八、數據結構之位圖（bitmap）

位圖bitmap 是一種非常常用的結構，在索引，數據壓縮等方面有廣泛應用。

所謂的 bitmap 就是用一個(gè) bit 位來(lái)標記某個(gè)元素對應的 value， 而 key 即是該元素。由于采用了 bit 為單位來(lái)存儲數據，因此在存儲空間方面，可以大大節省。

來(lái)看一個(gè)具體的例子，假設我們要對 0-7 內的 5 個(gè)元素 (4,7,2,5,3) 排序（這里假設這些元素沒(méi)有重復）。那么我們就可以采用 bitmap 的方法來(lái)達到排序的目的。

文中給出了使用 bitmap 進(jìn)行排序的算法思路，感興趣的同學(xué)可以移步：什么是Bit-map？

九、場(chǎng)景分析

1.先看看這樣的一個(gè)場(chǎng)景：給一臺普通 PC，2G 內存，要求處理一個(gè)包含 40 億個(gè)不重復并且沒(méi)有排過(guò)序的無(wú)符號的 int 整數，給出一個(gè)整數，問(wèn)如果快速地判斷這個(gè)整數是否在文件 40 億個(gè)數據當中？

2.問(wèn)題思考：

40 億個(gè) int 占 (40億*4)/1024/1024/1024 大概為 14.9G 左右，很明顯內存只有 2G ，放不下，因此不可能將這 40 億數據放到內存中計算。

要快速的解決這個(gè)問(wèn)題最好的方案就是將數據擱內存里，所以現在的問(wèn)題就在如何在 2G 內存空間以?xún)却鎯χ?zhù) 40 億整數。一個(gè) int 整數占 4 個(gè)字節的即要 32bit 位，如果能夠用一個(gè) bit 位來(lái)標識一個(gè) int 整數那么存儲空間將大大減少。

算一下 40 億個(gè) int 需要的內存空間為 40億/8/1024/1024 大概為 476.83MB，這樣的話(huà)我們完全可以將這 40 億個(gè) int 數放到內存中進(jìn)行處理。

3.具體思路：

1 個(gè) int 占 4 字節即 4*8=32位 ，那么我們只需要申請一個(gè) int 數組長(cháng)度為 int tmp[1 N/32] 即可存儲完這些數據，其中 N 代表要進(jìn)行查找的總數，tmp 中的每個(gè)元素在內存在占 32 位可以對應表示十進(jìn)制數 0~31 ,所以可得到 bitmap 表:

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

4.那么接下來(lái)就看看十進(jìn)制數如何轉換為對應的 bit 位：

假設這 40 億 int 數據為：6,3,8,32,36,......，那么具體的 BitMap 表示為：

5.如何判斷 int 數字在 tmp 數組的哪個(gè)下標，這個(gè)其實(shí)可以通過(guò)直接除以 32 取整數部分，例如：整數 8 除以32 取整等于 0，那么 8 就在 tmp[0]上。另外，我們如何知道了 8 在 tmp[0] 中的 32 個(gè)位中的哪個(gè)位，這種情況直接 mod 上 32 就 ok ，又如整數 8 ，在 tmp[0] 中的第 8 mod 上 32 等于 8，那么整數 8 就在 tmp[0] 中的第八個(gè) bit 位（從右邊數起）。

具體算法可以查看此篇文章，很清晰：海量數據解決思路之 BitMap

其實(shí) bitmap 的應用場(chǎng)景遠遠不止點(diǎn)，比如還可以用于壓縮、爬蟲(chóng)系統中 url 去重、解決全組合問(wèn)題?？赡苡行┤擞X(jué)得bitmap 算法實(shí)現起來(lái)有點(diǎn)麻煩，其實(shí)某些語(yǔ)言是對 bitmap 算法進(jìn)行了封裝的，比如 java 中對應 bitmap 的數據結構就有 bitset 類(lèi)。

十、海量數據解決思路

《數據結構：位圖法》這篇文章中提到幾個(gè)解決海量數據的思路：

1.給40億個(gè)不重復的 unsigned int 的整數，沒(méi)排過(guò)序的，然后再給一個(gè)數，如何快速判斷這個(gè)數是否在那 40 億個(gè)數當中？

思路：首先，將這 40 億個(gè)數字存儲到 bitmap 中，然后對于給出的數，判斷是否在 bitmap 中即可。

2.使用位圖法判斷整形數組是否存在重復？

答：遍歷數組，一個(gè)一個(gè)放入 bitmap，并且檢查其是否在 bitmap 中出現過(guò)，如果沒(méi)出現放入，否則即為重復的元素。

3.如何使用位圖法進(jìn)行整形數組排序？

答：首先遍歷數組，得到數組的最大最小值，然后根據這個(gè)最大最小值來(lái)縮小 bitmap 的范圍。這里需要注意對于 int 的負數，都要轉化為 unsigned int 來(lái)處理，而且取位的時(shí)候，數字要減去最小值。

4、在 2.5 億個(gè)整數中找出不重復的整數？（注：內存不足以容納這 2.5 億個(gè)整數）

參考的一個(gè)方法是：采用 2-Bitmap（每個(gè)數分配 2bit，00 表示不存在，01 表示出現一次，10 表示多次，11 無(wú)意義）。其實(shí)，這里可以使用兩個(gè)普通的 Bitmap，即第一個(gè) Bitmap 存儲的是整數是否出現，如果再次出現，則在第二個(gè) Bitmap 中設置即可。這樣的話(huà)，就可以使用簡(jiǎn)單的 1-Bitmap 了。

數據結構-位圖法這篇文章對位圖法分析非常到位，而且有更多的應用場(chǎng)景，強烈推薦。

十一、擴展：計算機 32 位和 64 位操作系統

1.先明確一下概念：

其實(shí)我們說(shuō)的 32 位和 64 位，指的是 CPU 每一次處理多少位的數據。對于 32 位 CPU，其一次只能處理 32 位（即 4 個(gè)字節）的數據；

而 64 位 CPU 一次可以處理 64 位（即 8 個(gè)字節）的數據。從處理數據的能力方面來(lái)看，64 位是 32 位的兩倍，64 位要比 32 位好。

2.特點(diǎn)

64 位 CPU 擁有更大的尋址能力，最大支持到 16GB 內存，而 32 位只支持 4G 內存；64 位 CPU 一次可提取 64 位數據，比 32 位提高了一倍，理論上性能會(huì )提升 1 倍。但這是建立在 64 位操作系統，64 位軟件的基礎上的。64 位操作系統的設計初衷是為了滿(mǎn)足機械設計和分析、三維動(dòng)畫(huà)、視頻編輯和創(chuàng )作，以及科學(xué)計算和高性能計算應用程序等領(lǐng)域中需要大量?jì)却婧透↑c(diǎn)性能的客戶(hù)需求，而 32 位系統，初期并沒(méi)有考慮太多。

3.原理

8 位處理器、16 位處理器、32 位處理器和 64 位處理器，其計數都是 8 的倍數。

它表示一個(gè) 32 位、64 位處理器區別時(shí)鐘周期里，處理器處理的二進(jìn)制代碼數。0 和 1 就是二進(jìn)制代碼，線(xiàn)路上有電信號，則計做 1 ,沒(méi)有電信號則為 0 。8 位機有 8 條線(xiàn)路，每個(gè)時(shí)鐘周期有 8 個(gè)電信號，組成一個(gè)字節。

所以，隨 8 位處理器上升至 64 位處理器，每個(gè)時(shí)鐘周期傳送 1 個(gè)字節到 8 個(gè)字節，關(guān)聯(lián)到時(shí)鐘速度提高到若干個(gè)千兆赫之后，處理器處理信息的能力越來(lái)越大。

十、參考

1.圖片占用內存計算方法

2.數據結構：位圖法

3.百科

4.圖片的存儲原理

5.32 位和 64 位操作系統

6.64位計算