引言
阿里內(nèi)推面試的時(shí)候被考了一道編程題：10億個(gè)范圍為1~2048的整數(shù)燕差，將其去重并計(jì)算數(shù)字?jǐn)?shù)目碧库。
我看到這個(gè)題目就想起來(lái)了《編程珠璣》第一章講的叫做BitMap的數(shù)據(jù)結(jié)構(gòu)辞槐，但是我并沒(méi)有在java上實(shí)現(xiàn)過(guò)践付，這就比較尷尬了，再加上時(shí)間不多了频鉴，只好暫時(shí)用byte代替bit栓辜，浪費(fèi)7個(gè)字節(jié)，在這篇文章里總結(jié)一下BitMap的常用代碼垛孔，以免重蹈覆轍藕甩。
偷懶的方法
其實(shí)java.util包中已經(jīng)有了一個(gè)實(shí)現(xiàn)，可以用這個(gè)數(shù)據(jù)結(jié)構(gòu)偷懶周荐，寫(xiě)了一個(gè)Demo如下：
package org.du.offerproblem.bitmap;
import java.util.BitSet;
/**
* Created by 燃燒杯 on 2018/2/24.
*/
public class BitSetTest {
public static void main(String[] args) {
int [] array = new int [] {1,2,3,22,0,3,63};
BitSet bitSet = new BitSet(1);
System.out.println(bitSet.size()); //64
bitSet = new BitSet(65);
System.out.println(bitSet.size()); //128
bitSet = new BitSet(23);
System.out.println(bitSet.size()); //64
//將數(shù)組內(nèi)容組bitmap
for(int i=0;i<array.length;i++)
{
bitSet.set(array[i], true);
}
System.out.println(bitSet.get(22));
System.out.println(bitSet.get(60));
System.out.println("下面開(kāi)始遍歷BitSet：");
for ( int i = 0; i < bitSet.size(); i++ ){
System.out.println(bitSet.get(i));
}
}
}
java.util.BitSet的底層是long數(shù)組辛萍，.size()方法返回的是BitSet當(dāng)前位數(shù)，因?yàn)閘ong是64位的羡藐，所以size返回的值也是64的整數(shù)倍贩毕，所以在上面的代碼中發(fā)現(xiàn)，我在構(gòu)造函數(shù)中傳入初始化長(zhǎng)度1~64中的任意一個(gè)值仆嗦，size的大小都是64位辉阶，因?yàn)榇藭r(shí)long數(shù)組的長(zhǎng)度只有1，而我一旦將其設(shè)置成65瘩扼，size的大小就變成128了谆甜。
用這個(gè)類是個(gè)偷懶的好辦法，但是一旦面試官一定要讓你自己實(shí)現(xiàn)一個(gè)就不行了集绰。
自己實(shí)現(xiàn)BitMap
可以用int數(shù)組來(lái)實(shí)現(xiàn)一個(gè)BitMap规辱，這種方法最關(guān)鍵的是求出index在int數(shù)組中的位置以及在該位置上的偏移量，有如下公式：
int數(shù)組中的位置(belowIndex) = (index - 1) >> 5
偏移量(offset) = (index - 1) & 31
我們這里假設(shè)index是從1開(kāi)始的栽燕，所以先將index減去1罕袋，如果你要統(tǒng)計(jì)的數(shù)據(jù)范圍是從0開(kāi)始的，則不需要減去這個(gè)1碍岔。右移5位（相當(dāng)于除以32）的原因是浴讯，一個(gè)int型數(shù)據(jù)是32位的（2的5次方等于32）。偏移量中&31相當(dāng)于模32蔼啦，其原因也因?yàn)閕nt型數(shù)據(jù)是32位的榆纽。如果你不準(zhǔn)備基于int，而是準(zhǔn)備基于其他的捏肢，如byte奈籽，long的話，（以byte為例）則將>>5改成>>3鸵赫，&31改成&7即可衣屏。
setBit的流程如下：
- 求出belowIndex并且得到int值；
- 求出offset并且利用“或運(yùn)算”將剛才得到的int值的offset位置置為1奉瘤；
getBit的流程如下：
- 求出belowIndex并且得到int值勾拉；
- 求出offset煮甥，之后利用“與運(yùn)算”取出offset位置的值將其變?yōu)?1后返回盗温；
代碼如下：
package org.du.offerproblem.bitmap;
/**
* 實(shí)現(xiàn)BitMap
*注：這個(gè)bitMap的index是從1開(kāi)始的
*/
public class BitMap {
private long length;
private static int[] bitsMap;
//構(gòu)造函數(shù)中傳入數(shù)據(jù)中的最大值
public BitMap(long length) {
this.length = length;
// 根據(jù)長(zhǎng)度算出藕赞，所需數(shù)組大小
bitsMap = new int[(int) (length >> 5) + ((length & 31) > 0 ? 1 : 0)];
}
public int getBit(long index) {
int intData = bitsMap[(int) ((index - 1) >> 5)];
int offset = (int) ((index - 1) & 31);
return intData >> offset & 0x01;
}
public void setBit(long index) {
// 求出該index - 1所在bitMap的下標(biāo)
int belowIndex = (int) ((index - 1) >> 5);
// 求出該值的偏移量(求余)
int offset = (int) ((index - 1) & 31);
int inData = bitsMap[belowIndex];
bitsMap[belowIndex] = inData | (0x01 << offset);
}
public static void main(String[] args) {
BitMap bitMap = new BitMap(32);
bitMap.setBit(32);
System.out.println(bitMap.getBit(1));
System.out.println(bitMap.getBit(32));
}
}
使用BitMap進(jìn)行數(shù)據(jù)去重
下面給出數(shù)組去重的代碼：
package org.du.offerproblem.bitmap;
import java.util.Arrays;
/**
* Created by 燃燒杯 on 2018/2/24.
* 這個(gè)BitMap的去重是從0開(kāi)始
*/
public class BitMapRepRemove {
//public static final int _1MB = 1024 * 1024;
//public static byte[] flags = new byte[ 512 * _1MB ];
public static byte[] flags;
public static void main(String[] args) {
int[] array = {255, 1024, 1024, 0, 65536, 0, 1024, 8888, 9999, 1111, 8888};
int length = 65536 + 1;
flags = new byte[(int) (length >> 3) + ((length & 7) > 0 ? 1 : 0)];
int index = 0;
for(int num : array) {
if( getFlags(num) != 1) {
//未出現(xiàn)的元素
array[index] = num;
index = index + 1;
//設(shè)置標(biāo)志位
setFlags(num);
}
}
array = Arrays.copyOf(array, index);
System.out.println(Arrays.toString(array));
System.out.println(array.length);
}
public static void setFlags(int num) {
int offset = num & (0x07);
flags[num >> 3] |= 0x01 << offset;
}
public static int getFlags(int num) {
int offset = num & (0x07);
return flags[num >> 3] >> offset & 0x01;
}
}
