BitMap的原理和實(shí)現(xiàn)方法

這篇文章主要介紹“BitMap的原理和實(shí)現(xiàn)方法”，在日常操作中，相信很多人在BitMap的原理和實(shí)現(xiàn)方法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”BitMap的原理和實(shí)現(xiàn)方法”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

在java中：　

byte  ->   8 bits  -->1字節(jié)
char  ->   16 bit  -->2字節(jié)
short ->   16 bits -->2字節(jié)
int   ->   32 bits -->4字節(jié)
float ->   32 bits -->4字節(jié)
long  ->   64 bits -->8字節(jié)

BitMap實(shí)現(xiàn)原理　　

　　在java中，一個int類型占32個比特，我們用一個int數(shù)組來表示new int[32]，總計(jì)占用內(nèi)存32*32bit，現(xiàn)假如我們用int字節(jié)碼的每一位表示一個數(shù)字的話，那么32個數(shù)字只需要一個int類型所占內(nèi)存空間大小就夠了，這樣在大數(shù)據(jù)量的情況下會節(jié)省很多內(nèi)存。

　具體思路：

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

　　　　tmp[0]:可表示0~31

　　　　tmp[1]:可表示32~63

　　　　tmp[2]可表示64~95

　　　　.......

　　那么接下來就看看十進(jìn)制數(shù)如何轉(zhuǎn)換為對應(yīng)的bit位：假設(shè)這40億int數(shù)據(jù)為：6,3,8,32,35,......，那么具體的BitMap表示為：

　如何判斷int數(shù)字在tmp數(shù)組的哪個下標(biāo)，這個其實(shí)可以通過直接除以32取整數(shù)部分，例如：整數(shù)8除以32取整等于0，那么8就在tmp[0]上。另外，我們?nèi)绾沃懒?在tmp[0]中的32個位中的哪個位，這種情況直接mod上32就ok，又如整數(shù)8，在tmp[0]中的第8 mod上32等于8，那么整數(shù)8就在tmp[0]中的第八個bit位（從右邊數(shù)起）。

/**
 * @author sowhat
 * @create 2020-08-20 19:30
 */
public class BitMap
{
	private long length;
	private static int[] bitsMap;
	private static final int[] BIT_VALUE = {0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020,
			0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000,
			0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000,
			0x01000000, 0x02000000, 0x04000000, 0x08000000, 0x10000000, 0x20000000, 0x40000000, 0x80000000};

	public BitMap(long length)
	{
		this.length = length;
		/**
		 * 根據(jù)長度算出，所需數(shù)組大小
		 * 當(dāng) length%32=0 時大小等于 = length/32
		 * 當(dāng) length%32>0 時大小等于 = length/32+l
		 */
		bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
	}

	/**
	 * @param n 要被設(shè)置的值為n
	 */
	public void setN(long n)
	{
		if (n < 0 || n > length)
		{
			throw new IllegalArgumentException("length value ">

BitMap應(yīng)用

　　1：看個小場景 > 在3億個整數(shù)中找出重復(fù)>=2次的整數(shù)，限制內(nèi)存不足以容納3億個整數(shù)。

　　對于這種場景我可以采用2-BitMap來解決，即為每個整數(shù)分配2bit，用不同的0、1組合來標(biāo)識特殊意思，如00表示此整數(shù)沒有出現(xiàn)過，01表示出現(xiàn)一次，11表示出現(xiàn)過多次，就可以找出重復(fù)的整數(shù)了，其需要的內(nèi)存空間是正常BitMap的2倍，為：3億*2/8/1024/1024=71.5MB。

　　具體的過程如下：

　　掃描著3億個整數(shù)，組BitMap，先查看BitMap中的對應(yīng)位置，如果00則變成01，是01則變成11，是11則保持不變，當(dāng)將3億個整數(shù)掃描完之后也就是說整個BitMap已經(jīng)組裝完畢。最后查看BitMap將對應(yīng)位為11的整數(shù)輸出即可。

　　2：已知某個文件內(nèi)包含一些電話號碼，每個電話號碼為8位數(shù)字，統(tǒng)計(jì)不同號碼的個數(shù)。

　　8位最多99 999 999，大概需要99百萬個bit，大小= 99 999 999/8/1024/1024 =12M。 （可以理解為從0-99 999 999的數(shù)字，每個數(shù)字對應(yīng)一個Bit位，所以只需要99百萬個Bit==1.2MBytes，這樣，就用了小小的12M左右的內(nèi)存表示了所有的8位數(shù)的電話）。

 另一種方式分析BitMap

　一、問題引入　　

　　bitMap是位圖，其實(shí)準(zhǔn)確的來說，翻譯成基于位的映射，舉一個例子，有一個無序有界int數(shù)組{1,2,5,7},初步估計(jì)占用內(nèi)存4*4=16字節(jié)，這倒是沒什么奇怪的，但是假如有10億個這樣的數(shù)呢，10億*4字節(jié)/(1024*1024*1024)=3.72G左右（1GB=1024MB 、1MB=1024KB 、1KB=1024B 、1B=8b）。如果這樣的一個大的數(shù)據(jù)做查找和排序，那估計(jì)內(nèi)存也崩潰了，有人說，這些數(shù)據(jù)可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。我們提倡的是高性能，這個方案直接不考慮。

　二、問題分析

　　如果用BitMap思想來解決的話，就好很多，解決方案如下：
　　一個byte是占8個bit，如果每一個bit的值就是有或者沒有，也就是二進(jìn)制的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ù)之間沒有關(guān)聯(lián)性，要是讀取的，你可以用多線程的方式去讀取。時間復(fù)雜度方面也是O(Max/n)，其中Max為byte[]數(shù)組的大小，n為線程大小。

　三、應(yīng)用與代碼
　　如果BitMap僅僅是這個特點(diǎn)，還不是它的優(yōu)雅的地方，接下來繼續(xù)欣賞它的魅力所在。下面的計(jì)算思想其實(shí)就是針對bit的邏輯運(yùn)算得到，類似這種邏輯運(yùn)算的應(yīng)用場景可以用于權(quán)限計(jì)算之中。

　　再看代碼之前，我們先搞清楚一個問題，一個數(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ù)該怎么辦呢，不用擔(dān)心，很簡單，也很神奇。
　　上面已經(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進(jìn)行左移，然后取反，最后與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，然后對取反，再與當(dāng)前值做&，即可清除當(dāng)前的位置了.
        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位相當(dāng)于除以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，然后對取反，再與當(dāng)前值做&，即可清除當(dāng)前的位置了.
        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);
    }
}

到此，關(guān)于“BitMap的原理和實(shí)現(xiàn)方法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！