BitMap是一種很常用的數(shù)據(jù)結(jié)構(gòu)鼠哥，它的思想的和原理是很多算法的基礎(chǔ)驻售，當(dāng)然露久，并且在索引，數(shù)據(jù)壓縮欺栗，海量數(shù)據(jù)處理等方面有廣泛應(yīng)用毫痕。
一、簡(jiǎn)介
BitMap 是一種很常用的數(shù)據(jù)結(jié)構(gòu)迟几，它的思想和原理是很多算法的基礎(chǔ)消请，比如Bloom Filter 。
BitMap 的基本原理就是用一個(gè) bit 位來存放某種狀態(tài)（如果理解不了类腮，看完下文再回頭來看即可）臊泰，適用于擁有大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況蚜枢。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的缸逃。
它最大的一個(gè)特點(diǎn)就是對(duì)內(nèi)存的占用極小，所以經(jīng)常在大數(shù)據(jù)中被優(yōu)化使用厂抽。
為什么說占用內(nèi)存小呢需频？其實(shí)從名字就可以看出端倪，直譯過來叫位圖筷凤，但不是圖形學(xué)里面的位圖哦昭殉，關(guān)鍵單詞是Bit。比如通過某種方法用一個(gè) bit 來表示一個(gè) int，這樣的話內(nèi)存足足壓縮至 1/32（1 int = 4 byte = 32 bit挪丢，PS：理論計(jì)算而已莽鸭，實(shí)操時(shí)并不會(huì)有 1/32 這么夸張，下文會(huì)解釋）吃靠，所以原先需要8G內(nèi)存的數(shù)據(jù)硫眨，現(xiàn)在只需要256M，豈不樂哉巢块？當(dāng)然了礁阁，其中算法的一些概念在下文會(huì)詳解。
二族奢、初窺 BitMap
1姥闭、概念理解
所謂的 BitMap 就是用一個(gè) Bit 位來標(biāo)記某個(gè)元素對(duì)應(yīng)的 Value， 而 Key 即是該元素越走。由于采用了 Bit 為單位來存儲(chǔ)數(shù)據(jù)棚品，因此在存儲(chǔ)空間方面，可以大大節(jié)省廊敌。
比如有個(gè) int 數(shù)組 [2,6,1,7,3]铜跑，內(nèi)含5個(gè)元素，存儲(chǔ)的空間大小為 5 * 32 = 160 bit骡澈，取的時(shí)候锅纺，使用元素的下標(biāo)來獲取對(duì)應(yīng)位上的元素。
但是如果換種思路肋殴，把元素的值作為下標(biāo)囤锉，每個(gè)下標(biāo)位使用 bit 來標(biāo)記，有值則為1护锤，否則為0官地，此時(shí)我們只需要在內(nèi)存上開辟一個(gè)連續(xù)的二進(jìn)制位空間，長度為8（因?yàn)樯厦鏀?shù)據(jù)最大的元素是7烙懦，但是需要考慮下標(biāo)起點(diǎn)為0）驱入，則可以表示成：
說明：初始化一個(gè)長度是8的 BitMap修陡，初始值均為0沧侥，然后將[2,6,1,7,3]填入對(duì)應(yīng)的下標(biāo)處，上圖中藍(lán)色域魄鸦，即將這幾個(gè)下標(biāo)處的值設(shè)置為1宴杀，所以表示為：1 1 0 0 1 1 1 0。此時(shí)占用的內(nèi)存空間為 8 bit拾因，而原來是 160 bit（順便解釋下上文提到的 1/32旺罢，因?yàn)槲覀冮_辟的是連續(xù)的內(nèi)容空間旷余，所以會(huì)有冗余）。
2扁达、案例說明
① 案例一：還是上文的數(shù)組正卧，需求是查詢?cè)?是否在數(shù)組中。
原先我們需要遍歷整個(gè)數(shù)組跪解，時(shí)間復(fù)雜度為 O(n);
而現(xiàn)在我們只需要查驗(yàn)下標(biāo)為6的字節(jié)是0還是1即可炉旷，如果是1，則代表存在叉讥，時(shí)間復(fù)雜度直接降為 O(1)窘行。
所以，最直接的應(yīng)用場(chǎng)景便是：數(shù)據(jù)的查重图仓。
② 案例二：有兩個(gè)數(shù)組罐盔，判斷這兩個(gè)數(shù)組中的重復(fù)元素。
原先的最淺顯的做法是雙層for循環(huán)進(jìn)行判斷比較救崔。
而現(xiàn)在惶看，只需要將轉(zhuǎn)換完成的兩個(gè)BirMap進(jìn)行與運(yùn)算即可，如：11001110B & 10100000B = 10000000B六孵，所有得出結(jié)果纬黎，只有元素 7 重復(fù)。
當(dāng)然狸臣，最直接的應(yīng)用場(chǎng)景是：每個(gè)客戶都有不同的標(biāo)簽莹桅，當(dāng)需要查找同時(shí)符合標(biāo)簽a和標(biāo)簽b的客戶的時(shí)候昌执，只需要將標(biāo)簽a和標(biāo)簽b的客戶查出來進(jìn)行如上的與運(yùn)算即可烛亦。
3、補(bǔ)充說明
① 實(shí)際使用的時(shí)候懂拾，并不會(huì)向上面一樣很隨意地將長度設(shè)置為8煤禽，一般會(huì)設(shè)置為32（int型）或64（long型），理由見下文 BitSet 源碼即可岖赋。
② 除了上文提到的與運(yùn)算檬果，當(dāng)然了，邏輯或和邏輯異或操作都是OK的唐断。
③ 每個(gè)Bit位只能是0或1选脊，所以只能代表true or false，當(dāng)我們要進(jìn)行少量統(tǒng)計(jì)的時(shí)候脸甘，可以使用2-BitMap恳啥，即每個(gè)位上可以使用 00、01丹诀、10钝的、11來分別表示數(shù)量為 0翁垂、1、2硝桩，此時(shí)的 11 一般無意義沿猜。
三、BitSet 源碼
1碗脊、簡(jiǎn)述
對(duì)于 BitMap 這種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)啼肩，在 Java 語言里面，其實(shí)已經(jīng)有對(duì)應(yīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類 java.util.BitSet 了（**@since ****JDK1.0）衙伶，而 BitSet 的底層原理疟游，其實(shí)就是用 long 類型的數(shù)組來存儲(chǔ)元素，所以回過頭來看上文提到的為什么實(shí)際使用的時(shí)候痕支，長度一般會(huì)是有規(guī)則的颁虐，因?yàn)榇颂幨褂玫氖莑ong類型的數(shù)組，而 1 long = 64 bit卧须，所以數(shù)據(jù)大小會(huì)是64的整數(shù)倍另绩。
/**
* The internal field corresponding to the serialField "bits".
*/
private long[] words;
至于 Java 中的 BitSet 為什么使用 long 數(shù)組而不使用 int 數(shù)組，我覺得應(yīng)該是出于 Java 語言的性能考慮的花嘶，因?yàn)樵谶M(jìn)行邏輯與等一系列位運(yùn)算的時(shí)候笋籽，是需要將兩個(gè)數(shù)組中的元素一一進(jìn)行位運(yùn)算的，而使用 long 的一個(gè)好處是數(shù)組的長度減少了椭员，從而遍歷的次數(shù)也就減少了车海。
總之就是和場(chǎng)景有關(guān)系，抽象概念上就有點(diǎn)類似 Java 中字符串的匹配算法（indexOf）使用的是 BF（暴力檢索）算法一樣隘击，為什么不用更優(yōu)解呢侍芝？還不是因?yàn)楦鼉?yōu)解在少量數(shù)據(jù)的情況下反而是拖后腿的那一位。
2埋同、成員變量
3州叠、構(gòu)造方法
有參構(gòu)造的參數(shù)代表的是元素的長度，不是數(shù)組的大小凶赁，比如傳參1和64咧栗，數(shù)組的長度均為1，整個(gè)size均為64虱肄，但是傳參65的時(shí)候致板，數(shù)組長度為2，size為128咏窿，因?yàn)閿?shù)組是long類型斟或，而一個(gè)long可以存儲(chǔ)64個(gè)bit元素。
4翰灾、 initWords 函數(shù)
該函數(shù)只在兩個(gè)構(gòu)造方法中調(diào)用缕粹，作用是初始化數(shù)組稚茅，而數(shù)組的長度則會(huì)通過 workIndex(nbits-1) + 1 來獲取。
5平斩、 wordIndex 函數(shù)
這個(gè)方法很重要亚享， 它是用來獲取某個(gè)數(shù)在 words 數(shù)組中的索引的，采用的算法是將這個(gè)數(shù)右移6位绘面，why欺税？因?yàn)?bitIndex >> 6 == bitIndex / (2^6) == bitIndex /64，而long就是64個(gè)字節(jié)揭璃。
6晚凿、ensureCapacity 函數(shù)
又是一個(gè)很重要的方法，作用是動(dòng)態(tài)擴(kuò)容瘦馍，因?yàn)樵诔跏蓟臅r(shí)候歼秽，我們并不知道將來會(huì)需要存儲(chǔ)多大的數(shù)據(jù)。
7情组、size 和 length 函數(shù)
size 方法很好理解燥筷，返回的其實(shí)就是數(shù)組的空間大小，即數(shù)組長度64院崇。
而 length 方法肆氓，看源碼其實(shí)有點(diǎn)晦(qu)澀(qiao)，簡(jiǎn)言之底瓣，返回的是 BitSet 的“邏輯大小”谢揪，即BitSet 中最高設(shè)置位的索引加 1* 。
舉個(gè)栗子捐凭，一個(gè) BitSet 中存儲(chǔ)了兩個(gè)元素拨扶，10和50，那么柑营，此時(shí)這個(gè) BitMap 的：size = 64屈雄；length = 51。
8官套、題外話
其余的 set、get等方法暫不贅述蚁孔，總之一句話奶赔，想要深刻理解 BitSet 的源碼，對(duì)于二進(jìn)制的計(jì)算需要有一定的掌握水準(zhǔn)杠氢。不得不承認(rèn)站刑，BitSet 的源碼，很多細(xì)節(jié)的設(shè)計(jì)太精妙了鼻百。
四绞旅、拓展
如要論述拓展摆尝，要么就是論述場(chǎng)景的高層次應(yīng)用，要么就是論述此算法的不足之處因悲，此處各提一個(gè)點(diǎn)：
① 不足：數(shù)據(jù)稀疏問題堕汞，比如三個(gè)元素(1,100,10000000)，則需要初始化的長度為 10000000晃琳，很不合理讯检，此時(shí)可以使用 Roaring BitMap 算法來解決，而 Java 程序可以使用goolge的 **EWAHCompressedBitmap **來解決卫旱。
② 拓展：數(shù)據(jù)碰撞問題人灼，比如上文提到的爬蟲應(yīng)用場(chǎng)景是將URL進(jìn)行哈希運(yùn)算，然后將hash值存入BitMap之中顾翼，但是不得不面臨一個(gè)尷尬的情況投放，那就是哈希碰撞，而布隆算法（Bloom Filter）就可以解決這個(gè)問題适贸，為什么是拓展呢跪呈？因?yàn)樗且?BitMap 為基礎(chǔ)的排重算法。
