前言

• BitMap從字面的意思，很多人認為是位圖，其實準確的來說，翻譯成基于位的映射，怎么理解呢?

問題引入

有一個無序有界int數(shù)組{1,2,5,7},初步估計占用內存44=16字節(jié)，因為只有4個數(shù)，很容易，可以很快找到需要的數(shù)。但是假如有10億個這樣的數(shù)呢，10億個不重復并且沒有排過序的無符號的int整數(shù)，給出一個整數(shù)，找出給定的某個數(shù)，你該如何操作?

需求分析：Int類型在Java中的存儲占用4個Byte,32Bit。10億4/(102410241024)=3.72G左右。如果這樣的一個大的數(shù)據(jù)做查找和排序，那估計內存也崩潰了，有人說，這些數(shù)據(jù)可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。我們提倡的是高性能，這個方案直接不考慮。

[[330308]]

問題分析

如果用BitMap思想來解決的話，就好很多，那么BitMap是怎么解決的啊，如下：

一個byte是占8個bit，如果每一個bit的值就是有或者沒有，也就是二進制的0或者1，如果用bit的位置代表數(shù)組值有還是沒有，那么0代表該數(shù)值沒有出現(xiàn)過，1代表該數(shù)組值出現(xiàn)過。不也能描述數(shù)據(jù)了嗎?具體如下圖： 

是不是很神奇，那么現(xiàn)在假如10億的數(shù)據(jù)所需的空間就是3.72G/32了吧，一個占用32bit的數(shù)據(jù)現(xiàn)在只占用了1bit，節(jié)省了不少的空間，排序就更不用說了，一切顯得那么順利。這樣的數(shù)據(jù)之間沒有關聯(lián)性，要是讀取的，你可以用多線程的方式去讀取。時間復雜度方面也是O(Max/n)，其中Max為byte[]數(shù)組的大小，n為線程大小。

三、應用與代碼

如果BitMap僅僅是這個特點，我覺得還不是它的優(yōu)雅的地方，接下來繼續(xù)欣賞它的魅力所在。下面的計算思想其實就是針對bit的邏輯運算得到，類似這種邏輯運算的應用場景可以用于權限計算之中。

再看代碼之前，我們先搞清楚一個問題，一個數(shù)怎么快速定位它的索引號，也就是說搞清楚byte[index]的index是多少，position是哪一位。舉個例子吧，例如add(14)。14已經(jīng)超出byte[0]的映射范圍，在byte[1]范圍之類。那么怎么快速定位它的索引呢。如果找到它的索引號，又怎么定位它的位置呢。Index(N)代表N的索引號，Position(N)代表N的所在的位置號。

• Index(N) = N/8 = N >> 3;
• Position(N) = N%8 = N & 0x07;

(1) add(int num)

你要向bitmap里add數(shù)據(jù)該怎么辦呢，不用擔心，很簡單，也很神奇。上面已經(jīng)分析了，add的目的是為了將所在的位置從0變成1.其他位置不變. 

實例代碼：

public void add(int num){ 
        // num/8得到byte[]的index 
        int arrayIndex = num >> 3;  
         
        // num%8得到在byte[index]的位置 
        int position = num & 0x07;  
         
        //將1左移position后，那個位置自然就是1，然后和以前的數(shù)據(jù)做|，這樣，那個位置就替換成1了。 
        bits[arrayIndex] |= 1 << position;  
    } 

(2) clear(int num)

對1進行左移，然后取反，最后與byte[index]作與操作。 

實例代碼：

public void clear(int num){ 
        // num/8得到byte[]的index 
        int arrayIndex = num >> 3;  
         
        // num%8得到在byte[index]的位置 
        int position = num & 0x07;  
         
        //將1左移position后，那個位置自然就是1，然后對取反，再與當前值做&，即可清除當前的位置了. 
        bits[arrayIndex] &= ~(1 << position);  
 
    } 

(3) contain(int num) 

實例代碼：

public boolean contain(int num){ 
       // num/8得到byte[]的index 
       int arrayIndex = num >> 3;  
        
       // num%8得到在byte[index]的位置 
       int position = num & 0x07;  
        
       //將1左移position后，那個位置自然就是1，然后和以前的數(shù)據(jù)做&，判斷是否為0即可 
       return (bits[arrayIndex] & (1 << position)) !=0;  
   } 

全部代碼如下：

public class BitMap { 
    //保存數(shù)據(jù)的 
    private byte[] bits; 
     
    //能夠存儲多少數(shù)據(jù) 
    private int capacity; 
     
     
    public BitMap(int capacity){ 
        this.capacity = capacity; 
         
        //1bit能存儲8個數(shù)據(jù)，那么capacity數(shù)據(jù)需要多少個bit呢，capacity/8+1,右移3位相當于除以8 
        bits = new byte[(capacity >>3 )+1]; 
    } 
     
    public void add(int num){ 
        // num/8得到byte[]的index 
        int arrayIndex = num >> 3;  
         
        // num%8得到在byte[index]的位置 
        int position = num & 0x07;  
         
        //將1左移position后，那個位置自然就是1，然后和以前的數(shù)據(jù)做|，這樣，那個位置就替換成1了。 
        bits[arrayIndex] |= 1 << position;  
    } 
     
    public boolean contain(int num){ 
        // num/8得到byte[]的index 
        int arrayIndex = num >> 3;  
         
        // num%8得到在byte[index]的位置 
        int position = num & 0x07;  
         
        //將1左移position后，那個位置自然就是1，然后和以前的數(shù)據(jù)做&，判斷是否為0即可 
        return (bits[arrayIndex] & (1 << position)) !=0;  
    } 
     
    public void clear(int num){ 
        // num/8得到byte[]的index 
        int arrayIndex = num >> 3;  
         
        // num%8得到在byte[index]的位置 
        int position = num & 0x07;  
         
        //將1左移position后，那個位置自然就是1，然后對取反，再與當前值做&，即可清除當前的位置了. 
        bits[arrayIndex] &= ~(1 << position);  
 
    } 
     
    public static void main(String[] args) { 
        BitMap bitmap = new BitMap(100); 
        bitmap.add(7); 
        System.out.println("插入7成功"); 
         
        boolean isexsit = bitmap.contain(7); 
        System.out.println("7是否存在:"+isexsit); 
         
        bitmap.clear(7); 
        isexsit = bitmap.contain(7); 
        System.out.println("7是否存在:"+isexsit); 
    } 
} 

總結：

Bitmap典型的應用場景為：大量數(shù)據(jù)的快速排序、查找、去重

其被廣泛用于數(shù)據(jù)庫和搜索引擎中，通過利用位級并行，它們可以顯著加快查詢速度。

但是，位圖索引會占用大量的內存，因此我們會更喜歡壓縮位圖索引。

以上為全部內容。