bitmap(BitMap的原理和實現方法)

在java中:　

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

BitMap實現原理　　

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

　具體思路:

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

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

　　那么接下來就看看十進制數如何轉換為對應的bit位:假設這40億int數據為:6,3,8,32,35,......,那么具體的BitMap表示為:

　如何判斷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位(從右邊數起)。

/***@authorsowhat*@create2020-08-2019:30*/publicclassBitMap{privatelonglength;privatestaticint[]bitsMap;privatestaticfinalint[]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};publicBitMap(longlength){this.length=length;/***根據長度算出,所需數組大小*當length%32=0時大小等于=length/32*當length%32>0時大小等于=length/32+l*/bitsMap=newint[(int)(length>>5)+((length&31)>0?1:0)];}/***@paramn要被設置的值為n*/publicvoidsetN(longn){if(n<0||n>length){thrownewIllegalArgumentException("lengthvalue">

BitMap應用

　　1:看個小場景 > 在3億個整數中找出重復>=2次的整數,限制內存不足以容納3億個整數。

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

　　具體的過程如下:

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

　　2:已知某個文件內包含一些電話號碼,每個電話號碼為8位數字,統計不同號碼的個數。

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

另一種方式分析BitMap

　一、問題引入　　

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

　二、問題分析

　　如果用BitMap思想來解決的話,就好很多,解決方案如下:
　　一個byte是占8個bit,如果每一個bit的值就是有或者沒有,也就是二進制的0或者1,如果用bit的位置代表數組值有還是沒有, 那么0代表該數值沒有出現過,1代表該數組值出現過。不也能描述數據了嗎?具體如下圖:

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

　三、應用與代碼
　　如果BitMap僅僅是這個特點,還不是它的優雅的地方,接下來繼續欣賞它的魅力所在。下面的計算思想其實就是針對bit的邏輯運算得到,類似這種邏輯運算的應用場景可以用于權限計算之中。

　　再看代碼之前,我們先搞清楚一個問題,一個數怎么快速定位它的索引號,也就是說搞清楚byte[index]的index是多少,position是哪一位。舉個例子吧,例如add(14)。14已經超出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數據該怎么辦呢,不用擔心,很簡單,也很神奇。
　　上面已經分析了,add的目的是為了將所在的位置從0變成1.其他位置不變.

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

(2) clear(int num)

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

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

(3) contain(int num)

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

全部代碼:

publicclassBitMap{//保存數據的privatebyte[]bits;//能夠存儲多少數據privateintcapacity;publicBitMap(intcapacity){this.capacity=capacity;//1bit能存儲8個數據,那么capacity數據需要多少個bit呢,capacity/8+1,右移3位相當于除以8bits=newbyte[(capacity>>3)+1];}publicvoidadd(intnum){//num/8得到byte[]的indexintarrayIndex=num>>3;//num%8得到在byte[index]的位置intposition=num&0x07;//將1左移position后,那個位置自然就是1,然后和以前的數據做|,這樣,那個位置就替換成1了。bits[arrayIndex]|=1<<position;}publicbooleancontain(intnum){//num/8得到byte[]的indexintarrayIndex=num>>3;//num%8得到在byte[index]的位置intposition=num&0x07;//將1左移position后,那個位置自然就是1,然后和以前的數據做&,判斷是否為0即可return(bits[arrayIndex]&(1<<position))!=0;}publicvoidclear(intnum){//num/8得到byte[]的indexintarrayIndex=num>>3;//num%8得到在byte[index]的位置intposition=num&0x07;//將1左移position后,那個位置自然就是1,然后對取反,再與當前值做&,即可清除當前的位置了.bits[arrayIndex]&=~(1<<position);}publicstaticvoidmain(String[]args){BitMapbitmap=newBitMap(100);bitmap.add(7);System.out.println("插入7成功");booleanisexsit=bitmap.contain(7);System.out.println("7是否存在:"+isexsit);bitmap.clear(7);isexsit=bitmap.contain(7);System.out.println("7是否存在:"+isexsit);}}

到此,關于“BitMap的原理和實現方法”的學習就結束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習,快去試試吧!若想繼續學習更多相關知識,請繼續關注本站網站,小編會繼續努力為大家帶來更多實用的文章!