經(jīng)常能夠看到有些大廠的面試題里有一些這樣的題目：一個(gè)10G的文件麻掸，里面全部是自然數(shù)，一行一個(gè)诚隙，亂序排列，對(duì)其排序地消。在32位機(jī)器上面完成，內(nèi)存限制為 2G半夷。
首先來分析一下題目否彩，10G的文件列荔，只有2G內(nèi)存，顯然崎溃，不可能一次性把數(shù)據(jù)放入內(nèi)存中直接排序袁串。那么囱修，還有什么其他辦法呢？遍尋資料鲜漩，可以發(fā)現(xiàn)大致有兩種解決方案：
1、把大文件分成多個(gè)小文件鳞青，分別排序习寸，到最后合并成一個(gè)文件（我暫時(shí)還沒搞懂這個(gè)方法孵滞，所以不會(huì)描述，有興趣的看官可以自己去查一下）匿级；
2、另外一種方法就是著名的bitmap算法了孤页。引用一下《編程珠璣》的內(nèi)容：
所謂的Bit-map就是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)冰寻，因此在存儲(chǔ)空間方面，可以大大節(jié)省划乖。
如果說了這么多還沒明白什么是Bit-map误算，那么我們來看一個(gè)具體的例子庆寺，假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）知纷。那么我們就可以采用Bit-map的方法來達(dá)到排序的目的伍绳。要表示8個(gè)數(shù)漠趁，我們就只需要8個(gè)Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0
然后遍歷這5個(gè)元素，首先第一個(gè)元素是4图谷，那么就把4對(duì)應(yīng)的位置為1（可以這樣操作 p+(i/8)|(0×01<<(i%8)) 當(dāng)然了這里的操作涉及到Big-ending和Little-ending的情況承璃，這里默認(rèn)為Big-ending）,因?yàn)槭菑牧汩_始的，所以要把第五位置為1。
然后再處理第二個(gè)元素7咬崔，將第八位置為1,兜蠕，接著再處理第三個(gè)元素盗舰，一直到最后處理完所有的元素，將相應(yīng)的位置為1较沪。
然后我們現(xiàn)在遍歷一遍Bit區(qū)域控轿，將該位是一的位的編號(hào)輸出（2烘苹，3，4望浩，5典挑，7），這樣就達(dá)到了排序的目的肆糕。
其實(shí)就是把計(jì)數(shù)排序用的統(tǒng)計(jì)數(shù)組的每個(gè)單位縮小成bit級(jí)別的布爾數(shù)組
這就是Bit-map的基本思想始赎。Bit-map算法利用這種思想處理大量數(shù)據(jù)的排序涨享、查詢以及去重。
片頭提出的問題，這里自然是要用bitmap算法來解決了，下面先來解釋一下算法（本期算法用java實(shí)現(xiàn)）橄维。
1、
32位機(jī)器上的自然數(shù)一共有4294967296個(gè)店溢，如果用一個(gè)bit來存放一個(gè)整數(shù)遭贸，1代表存在算利，0代表不存在胖秒，那么把全部自然數(shù)存儲(chǔ)在內(nèi)存只要4294967296 / (8 * 1024 * 1024) = 512MB（8bit = 一個(gè)字節(jié)），而這些自然數(shù)存放在文件中，一行一個(gè)數(shù)字，需要20G的容量。可見，bitmap算法節(jié)約了非常多的空間。
不過在java中惑淳，應(yīng)該沒有bit這種數(shù)據(jù)結(jié)構(gòu)绢馍，最小的是byte你稚，byte占8bit，那么我們可以用byte代表8個(gè)連續(xù)的數(shù)字，不過因?yàn)閎yte的范圍是127 ~ -128，最高位是符號(hào)位疗垛，所以可以變通一下咬展，前7位代表8n ~ 8n + 7的數(shù)字祷舀，8n + 7這個(gè)數(shù)可以按位取反變成負(fù)數(shù)來區(qū)分谤职，即>0即含有8n + 7饶套，<0即不含8n + 7（這里其實(shí)不一定要用byte來做，用short，int，long來做都一樣的，因?yàn)槲艺业降谝黄怯胋yte，所以就先入為主了）。
talk is cheap，show me the code. -- Linus Torvalds
2、
package main.io;
public class BitMap {
public byte[] bitArr;
private static final byte mask = 3;
private static final int maxNum = (1 << mask) - 1;
private long count = 0;
BitMap() {
bitArr = new byte[1 << (Integer.SIZE - mask)];
}
}
這里的mask代表的是移位數(shù)，n >>3 等價(jià)于 Math.floor(n / 8)， (1 << 3) - 1 = 7 = bin 111（這兩個(gè)地方先記著，下面會(huì)解釋）谓厘。
3他爸、
設(shè)置bit的方法讨跟，網(wǎng)上能夠找到的代碼多數(shù)是這樣實(shí)現(xiàn)的:
bitArr[num >> mask] |= (1 << (num & maxNum));
但是這個(gè)方法會(huì)有一個(gè)邏輯漏洞预愤，就是(1 << (8n + 7) & 7) = 128销睁，128就超出了byte的范圍變成-128了演顾，我就是被這個(gè)坑了棉钧，還好寫了一個(gè)php的版本來對(duì)比debug愧捕。。。o(╥﹏╥)o
這里要區(qū)分原來的數(shù)值是否為負(fù)數(shù)，還有設(shè)置的數(shù)是否為8n + 7卸夕。
我對(duì)于位運(yùn)算不太熟乖寒，所以就把負(fù)數(shù)按位取反進(jìn)行 | 運(yùn)算再轉(zhuǎn)回來瓢省。
設(shè)置bit的方法：
public void setBit(int num) {
var val = bitArr[num >> mask];
var bit = num & maxNum;
if (val >= 0 && bit == maxNum) {
bitArr[num >> mask] = (byte) ~val;
} else if (val < 0 && bit != maxNum) {
bitArr[num >> mask] = (byte) ~(~val | (1 << bit));
} else if (val >= 0 && bit != maxNum) {
bitArr[num >> mask] |= (1 << bit);
}
}
4馒胆、
只要明白了上面的方法，下面的查詢和移除的方法也就十分簡單了。
public byte getBit(int num) {
var val = bitArr[num >> mask];
var bit = num & maxNum;
if (bit == maxNum) {
return bitArr[num >> mask] < 0 ? (byte) 1 : (byte) 0;
} else if (val < 0 && bit != maxNum) {
return (byte) (~bitArr[num >> mask] & (1 << (bit)));
} else {
return (byte) (bitArr[num >> mask] & (1 << (bit)));
}
}
public void delBit(int num) {
var val = bitArr[num >> mask];
var bit = num & maxNum;
if (bit == maxNum) {
bitArr[num >> mask] = (byte) ~val;
} else if (val < 0 && bit != maxNum) {
bitArr[num >> mask] = (byte) ~(~bitArr[num >> mask] ^ (1 << (bit)));
} else {
bitArr[num >> mask] = (byte) (bitArr[num >> mask] ^ (1 << (bit)));
}
}
最后還有一個(gè)統(tǒng)計(jì)bitmap存在數(shù)字?jǐn)?shù)量的方法：
public long countDistinctNum() {
var length = bitArr.length;
for (int i = 0; i < length; ++i) {
if (bitArr[i] >= 0) {
count += Integer.bitCount(bitArr[i]);
}else {
count += Integer.bitCount(~bitArr[i]) + 1;
}
}
return count;
}
明白了bitmap的算法原理，接下來就要實(shí)戰(zhàn)一下冗茸，下期來講一下利用bitmap給海量數(shù)據(jù)排序的方法屎篱。
