相關(guān)概念

　基礎(chǔ)類型

　在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é)

　位運(yùn)算符

　　在java中，int數(shù)據(jù)底層以補(bǔ)碼形式存儲(chǔ)。int型變量使用32bit存儲(chǔ)數(shù)據(jù)，其中最高位是符號(hào)位，0表示正數(shù)，1表示負(fù)數(shù)，可通過Integer.toBinaryString()轉(zhuǎn)換為bit字符串，

// 若最高的幾位為0則不輸出這幾位，從為1的那一位開始輸出 System.out.println(Integer.toBinaryString(10)); System.out.println(Integer.toBinaryString(-10)); // 會(huì)輸出（手工排版過，以下的輸出均會(huì)被手工排版）：1010 11111111111111111111111111110110

　左移<<

　　例如：5 << 2 = 20

首先會(huì)將5轉(zhuǎn)為2進(jìn)制表示形式: 0000 0000 0000 0000 0000 0000 0000 0101 然后左移2位后，低位補(bǔ)0： 0000 0000 0000 0000 0000 0000 0001 0100 換算成10進(jìn)制為20

　右移>>

　　例如：?5 >> 2 = 1

還是先將5轉(zhuǎn)為2進(jìn)制表示形式： 0000 0000 0000 0000 0000 0000 0000 0101 然后右移2位，高位補(bǔ)0： 0000 0000 0000 0000 0000 0000 0000 0001 換算成十進(jìn)制后是1

　無符號(hào)右移>>>

　　　5 >>> 3　　　　

　　我們知道在Java中int類型占32位，可以表示一個(gè)正數(shù)，也可以表示一個(gè)負(fù)數(shù)。正數(shù)換算成二進(jìn)制后的最高位為0，負(fù)數(shù)的二進(jìn)制最高為為1。對(duì)于2進(jìn)制補(bǔ)碼的加法運(yùn)算，和平常的計(jì)算一樣，而且符號(hào)位也參與運(yùn)算，不過最后只保留32位

-5換算成二進(jìn)制： 1111 1111 1111 1111 1111 1111 1111 1011 -5右移3位： 1111 1111 1111 1111 1111 1111 1111 1111 // (用1進(jìn)行補(bǔ)位，結(jié)果為-1) -5無符號(hào)右移3位: 0001 1111 1111 1111 1111 1111 1111 1111 // (用0進(jìn)行補(bǔ)位,結(jié)果536870911 )

　位與&

　　第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1，否則為0

5轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 0000 0000 0000 0000 0101 3轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 0000 0000 0000 0000 0011 ------------------------------------------------------------ 1轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 0000 0000 0000 0000 0001

　位或|

　　第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位只要有一個(gè)為1則為1，否則為0

5轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 0000 0000 0000 0000 0101 3轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 0000 0000 0000 0000 0011 ------------------------------------------------------------------------------------- 6轉(zhuǎn)換為二進(jìn)制：0000 0000 0000 0000 0000 0000 0000 0111

　　對(duì)于移位運(yùn)算，例如將x左移/右移n位，如果x是byte、short、char、int，n會(huì)先模32（即n=n%32），然后再進(jìn)行移位操作。可以這樣解釋：int類型為32位,移動(dòng)32位（或以上）沒有意義。

　　同理若x是long，n=n%64。

　左移和右移代替乘除

a=a*4; b=b/4;

　可以改為

a=a<<2; b=b>>2;

　　說明：?　　除2 = 右移1位 乘2 = 左移1位 　　除4 = 右移2位 乘4 = 左移2位 　　除8 = 右移3位 乘8 = 左移3位 　　… …

　　類比十進(jìn)制中的滿十進(jìn)一，向左移動(dòng)小數(shù)點(diǎn)后，數(shù)字就會(huì)縮小十倍，在二進(jìn)制中滿二進(jìn)一，進(jìn)行右移一次相當(dāng)于縮小了2兩倍，右移兩位相當(dāng)于縮小了4倍，右移三位相當(dāng)于縮小了8倍。通常如果需要乘以或除以2的n次方，都可以用移位的方法代替。

　　實(shí)際上，只要是乘以或除以一個(gè)整數(shù)，均可以用移位的方法得到結(jié)果如：

　　a=a*9

　　分析a9可以拆分成a(8+1)即a8+a1, 因此可以改為： a=(a<<3)+a

　　a=a*7

　　分析a7可以拆分成a(8-1)即a8-a1, 因此可以改為： a=(a<<3)-a

　　關(guān)于除法讀者可以類推, 此略。

　　【注意】由于+/-運(yùn)算符優(yōu)先級(jí)比移位運(yùn)算符高，所以在寫公式時(shí)候一定要記得添加括號(hào)，不可以 a = a*12 等價(jià)于 a = a<<3 +a <<2; 要寫成a = (a<<3)+(a <<2 )。

　與運(yùn)算代替取余

31轉(zhuǎn)換為二進(jìn)制：011111,0,31 32轉(zhuǎn)換為二進(jìn)制：100010 與31取交集的結(jié)果是：10轉(zhuǎn)換為十進(jìn)制為2 31轉(zhuǎn)換為二進(jìn)制：100001 與31取交集的結(jié)果是：01轉(zhuǎn)換為十進(jìn)制為1 30轉(zhuǎn)換為二進(jìn)制：011110 與31取交集的結(jié)果是：11110轉(zhuǎn)換為十進(jìn)制為30 29轉(zhuǎn)換為二進(jìn)制：011101 與31取交集的結(jié)果是：11101轉(zhuǎn)換為十進(jìn)制為29 33轉(zhuǎn)換為二進(jìn)制：100001 與31取交集的結(jié)果是：1轉(zhuǎn)換為十進(jìn)制為1

　　31轉(zhuǎn)換為二進(jìn)制后，低位值全部為1，高位全為0。所以和其進(jìn)行與運(yùn)算，高位和0與，結(jié)果是0，相當(dāng)于將高位全部截取，截取后的結(jié)果肯定小于等于31，地位全部為1，與1與值為其本身，所以相當(dāng)于對(duì)數(shù)進(jìn)行了取余操作。

　進(jìn)制轉(zhuǎn)換

• 0x開頭表示16進(jìn)制，例如：0x2表示：2，0x2f表示48
• 0開頭表示8進(jìn)制，例如：02表示：2,010表示：8

Integer.toHexString(int i) // 十進(jìn)制轉(zhuǎn)成十六進(jìn)制 Integer.toOctalString(int i) // 十進(jìn)制轉(zhuǎn)成八進(jìn)制 Integer.toBinaryString(int i)// 十進(jìn)制轉(zhuǎn)成二進(jìn)制 Integer.valueOf(m,n).toString() // 把n進(jìn)制的m轉(zhuǎn)換為10進(jìn)制

---

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

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

　具體思路：

　　1個(gè)int占4字節(jié)即4*8=32位，那么我們只需要申請(qǐng)一個(gè)int數(shù)組長(zhǎng)度為 int tmp[1+N/32]即可存儲(chǔ)完這些數(shù)據(jù)，其中N代表要進(jìn)行查找的總數(shù)，tmp中的每個(gè)元素在內(nèi)存在占32位可以對(duì)應(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)換為對(duì)應(yīng)的bit位：

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

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

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 BitMap2(long length) {this.length = length;/*** 根據(jù)長(zhǎng)度算出，所需數(shù)組大小* 當(dāng) length%32=0 時(shí)大小等于* = length/32* 當(dāng) length%32>0 時(shí)大小等于* = 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 "+n+" is illegal!");}// 求出該n所在bitMap的下標(biāo),等價(jià)于"n/5"int index = (int) n>>5;// 求出該值的偏移量(求余),等價(jià)于"n%31"int offset = (int) n & 31;/*** 等價(jià)于* int bits = bitsMap[index];* bitsMap[index]=bits| BIT_VALUE[offset];* 例如,n=3時(shí),設(shè)置byte第4個(gè)位置為1 （從0開始計(jì)數(shù)，bitsMap[0]可代表的數(shù)為：0~31，從左到右每一個(gè)bit位表示一位數(shù)）* bitsMap[0]=00000000 00000000 00000000 00000000 | 00000000 00000000 00000000 00001000=00000000 00000000 00000000 00000000 00001000* 即: bitsMap[0]= 0 | 0x00000008 = 3** 例如,n=4時(shí),設(shè)置byte第5個(gè)位置為1* bitsMap[0]=00000000 00000000 00000000 00001000 | 00000000 00000000 00000000 00010000=00000000 00000000 00000000 00000000 00011000* 即: bitsMap[0]=3 | 0x00000010 = 12*/bitsMap[index] |= BIT_VALUE[offset];}/*** 獲取值N是否存在* @return 1：存在，0：不存在*/public int isExist(long n) {if (n < 0 || n > length) {throw new IllegalArgumentException("length value illegal!");}int index = (int) n>>5;int offset = (int) n & 31;int bits = (int) bitsMap[index];// System.out.println("n="+n+",index="+index+",offset="+offset+",bits="+Integer.toBinaryString(bitsMap[index]));return ((bits & BIT_VALUE[offset])) >>> offset;}

BitMap應(yīng)用

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

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

　　具體的過程如下：

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

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

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

BitMap問題

　　BitMap 的思想在面試的時(shí)候還是可以用來解決不少問題的，然后在很多系統(tǒng)中也都會(huì)用到，算是一種不錯(cuò)的解決問題的思路。

　　但是 BitMap 也有一些局限，因此會(huì)有其它一些基于 BitMap 的算法出現(xiàn)來解決這些問題。

• 數(shù)據(jù)碰撞。比如將字符串映射到 BitMap 的時(shí)候會(huì)有碰撞的問題，那就可以考慮用 Bloom Filter 來解決，Bloom Filter?使用多個(gè) Hash 函數(shù)來減少?zèng)_突的概率。
• 數(shù)據(jù)稀疏。又比如要存入(10,8887983,93452134)這三個(gè)數(shù)據(jù)，我們需要建立一個(gè) 99999999 長(zhǎng)度的 BitMap ，但是實(shí)際上只存了3個(gè)數(shù)據(jù)，這時(shí)候就有很大的空間浪費(fèi)，碰到這種問題的話，可以通過引入 Roaring BitMap 來解決。

---

?另一種方式分析BitMap

　一、問題引入　　

bitMap是位圖，其實(shí)準(zhǔn)確的來說，翻譯成基于位的映射，舉一個(gè)例子，有一個(gè)無序有界int數(shù)組{1,2,5,7},初步估計(jì)占用內(nèi)存44=16字節(jié)，這倒是沒什么奇怪的，但是假如有10億個(gè)這樣的數(shù)呢，10億*4字節(jié)/(1024*1024*1024)=3.72G左右（1GB=1024MB 、1MB=1024KB 、1KB=1024B 、1B=8b）。如果這樣的一個(gè)大的數(shù)據(jù)做查找和排序，那估計(jì)內(nèi)存也崩潰了，有人說，這些數(shù)據(jù)可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。我們提倡的是高性能，這個(gè)方案直接不考慮。 二、問題分析 　　如果用BitMap思想來解決的話，就好很多，解決方案如下：
　　一個(gè)byte是占8個(gè)bit，如果每一個(gè)bit的值就是有或者沒有，也就是二進(jìn)制的0或者1，如果用bit的位置代表數(shù)組值有還是沒有， 那么0代表該數(shù)值沒有出現(xiàn)過，1代表該數(shù)組值出現(xiàn)過。不也能描述數(shù)據(jù)了嗎？具體如下圖：

　　　　　　　　　　　　　　　　　　bitMap結(jié)構(gòu).p

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

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

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

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

add.png

代碼：

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

　(2) clear(int num)

　　對(duì)1進(jìn)行左移，然后取反，最后與byte[index]作與操作。

　　實(shí)例代碼：

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

　(3) contain(int num)

?

?

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

全部代碼：

public class BitMap {//保存數(shù)據(jù)的private byte[] bits;//能夠存儲(chǔ)多少數(shù)據(jù)private int capacity;public BitMap(int capacity){this.capacity = capacity;//1bit能存儲(chǔ)8個(gè)數(shù)據(jù)，那么capacity數(shù)據(jù)需要多少個(gè)bit呢，capacity/8+1,右移3位相當(dāng)于除以8bits = new byte[(capacity >>3 )+1];}public void add(int num){// num/8得到byte[]的indexint arrayIndex = num >> 3; // num%8得到在byte[index]的位置int position = num & 0x07; //將1左移position后，那個(gè)位置自然就是1，然后和以前的數(shù)據(jù)做|，這樣，那個(gè)位置就替換成1了。bits[arrayIndex] |= 1 << position; }public boolean contain(int num){// num/8得到byte[]的indexint arrayIndex = num >> 3; // num%8得到在byte[index]的位置int position = num & 0x07; //將1左移position后，那個(gè)位置自然就是1，然后和以前的數(shù)據(jù)做&，判斷是否為0即可return (bits[arrayIndex] & (1 << position)) !=0; }public void clear(int num){// num/8得到byte[]的indexint arrayIndex = num >> 3; // num%8得到在byte[index]的位置int position = num & 0x07; //將1左移position后，那個(gè)位置自然就是1，然后對(duì)取反，再與當(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);} }

?

出處：　https://my.oschina.net/freelili/blog/2885263

　　　　http://www.cnblogs.com/wuhuangdi/p/4126752.html#3074215

轉(zhuǎn)載于:https://www.cnblogs.com/myseries/p/10880641.html

總結(jié)

以上是生活随笔為你收集整理的BitMap的原理和实现的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。