引言

阿里內推面試的時候被考了一道編程題：10億個范圍為1~2048的整數，將其去重并計算數字數目。

我看到這個題目就想起來了《編程珠璣》第一章講的叫做BitMap的數據結構，但是我并沒有在java上實現過，這就比較尷尬了，再加上時間不多了，只好暫時用byte代替bit，浪費7個字節，在這篇文章里總結一下BitMap的常用代碼，以免重蹈覆轍。

偷懶的方法

其實java.util包中已經有了一個實現，可以用這個數據結構偷懶，寫了一個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

//將數組內容組bitmap

for(int i=0;i

{

bitSet.set(array[i], true);

}

System.out.println(bitSet.get(22));

System.out.println(bitSet.get(60));

System.out.println("下面開始遍歷BitSet：");

for ( int i = 0; i < bitSet.size(); i++ ){

System.out.println(bitSet.get(i));

}

}

}

java.util.BitSet的底層是long數組，.size()方法返回的是BitSet當前位數，因為long是64位的，所以size返回的值也是64的整數倍，所以在上面的代碼中發現，我在構造函數中傳入初始化長度1~64中的任意一個值，size的大小都是64位，因為此時long數組的長度只有1，而我一旦將其設置成65，size的大小就變成128了。

用這個類是個偷懶的好辦法，但是一旦面試官一定要讓你自己實現一個就不行了。

自己實現BitMap

可以用int數組來實現一個BitMap，這種方法最關鍵的是求出index在int數組中的位置以及在該位置上的偏移量，有如下公式：

int數組中的位置(belowIndex) = (index - 1) >> 5

偏移量(offset) = (index - 1) & 31

我們這里假設index是從1開始的，所以先將index減去1，如果你要統計的數據范圍是從0開始的，則不需要減去這個1。右移5位(相當于除以32)的原因是，一個int型數據是32位的(2的5次方等于32)。偏移量中&31相當于模32，其原因也因為int型數據是32位的。如果你不準備基于int，而是準備基于其他的，如byte，long的話，(以byte為例)則將>>5改成>>3，&31改成&7即可。

setBit的流程如下：

求出belowIndex并且得到int值；

求出offset并且利用“或運算”將剛才得到的int值的offset位置置為1；

getBit的流程如下：

求出belowIndex并且得到int值；

求出offset，之后利用“與運算”取出offset位置的值將其變為01后返回；

代碼如下：

package org.du.offerproblem.bitmap;

/**

* 實現BitMap

*注：這個bitMap的index是從1開始的

*/

public class BitMap {

private long length;

private static int[] bitsMap;

//構造函數中傳入數據中的最大值

public BitMap(long length) {

this.length = length;

// 根據長度算出，所需數組大小

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的下標

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進行數據去重

下面給出數組去重的代碼：

package org.du.offerproblem.bitmap;

import java.util.Arrays;

/**

* Created by 燃燒杯 on 2018/2/24.

* 這個BitMap的去重是從0開始

*/

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) {

//未出現的元素

array[index] = num;

index = index + 1;

//設置標志位

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;

}

}