和朋友聊天，說到了大數據存儲和查找方式，朋友提到了「位圖」。結果我滿腦子都是「位圖-矢量圖」，「矢量圖-位圖」。難道此「位圖」非彼「位圖」？一、此「位圖」非彼究竟什麽是位圖？和朋友聊天，說到了大數據存儲和查找方式，朋友提到了「位圖」。結果我滿腦子都是「位圖-矢量圖」，「矢量圖-位圖」。難道此「位圖」非彼「位圖」？一、此「位圖」非彼「位圖」究竟什麽是位圖？為什麽會有這樣的疑惑，那是因為：位圖可能是一種圖片類型，也可能是數據結構的 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位計算