bitmapでhashアルゴリズムに使う空間を減らす

第1章では、1000万件を含む整数ファイルのソート問題について主に議論し、baidu面接問題のスタイルがある.
並べ替え問題をhashで解決することが主な考え方であるが,hashの空間的複雑度は相対的に大きいのでbitmapを用いてhashアルゴリズムに必要な空間を減らす.
一般的なhashは、例えば配列[2,3,5,10]に対してバケツソートアルゴリズムを用いて、10個の整数のbucketを宣言する必要があり、下図のように:
0
1
1
0
1
0
0
0
0
1
1
2
3
4
5
6
7
8
9
10
しかし、bitmapを使うと、1つの整数しか必要ありません.1つの整数(32ビットマシン)では32 bitがあるので、各bitにはmap 1つの整数があります.下図のように:
 
 
 
 
 
 
 
 
 
1
 
 
1
 
1
1
 
31
30
…
3
2
1
0
31
…
9
…
5
4
3
2
1
0
配列要素1
配列要素0
キーはビット操作set,clear,testです01 #define BITSPERWORD 32 02 #define SHIFT 5 03 #define MASK 0x1f 04   05 typedef long long int64; 06   07 int array[100000]; 08   09 /** 10 * 11 *   i  / 32   12   13 *   i % 32   bit 14 *   i >> SHIFT == i /  32 15 *   i &  MASK   == i % 32 16 *   (32) = (100000) 17 * 18 **/ 19   20 void set(int64 i) 21 { 22
     array[ i >> SHIFT]  |= ( 1 << ( i  &  MASK)); 23 } 24   25 void clear(int64 i) 26 { 27
     array[ i >> SHIFT]  &= ~( 1 << ( i  & MASK)); 28 } 29   30 int    test(int64 i) 31 { 32
     return array[ i >> SHIFT]  & ( 1 << ( i  &  MASK)); 33 }
例えば、ある会社の面接問題:
 
1つのファイルに10 G個の整数があり、乱順に並べられ、中位数を見つけることが要求されます.メモリ制限は2 Gです.考えだけ書けばいい.
10 G整数bitmapは10 G/32=0.3 G個の整数(<32ビットマシンで合計可能な2^31-1=2 G個の整数)を必要とし、0.3 G個の整数は0.3 G*4=1.2 Gの記憶空間しか必要としないので、一度スキャンするだけで中位数を求めることができる.

public class BitMap {
	private static byte[] bitMap = null;

	public BitMap(int size) {
		if (size % 8 == 0) {
			bitMap = new byte[size / 8];
		} else {
			bitMap = new byte[size / 8 + 1];
		}
	}

	public static void main(String[] args) {
		BitMap map = new BitMap(10);
		map.setTag(11);
		map.printBitMap();
		String string = "";
		for (int i = 0; i < bitMap.length; i++) {
			System.out.println(string + bitMap[i]);
		}
	}

	public void setTag(int number) {
		int index = 0;
		int bit_index = 0;
		if (number % 8 == 0) {
			index = number / 8 - 1;
			bit_index = 8;
		} else {
			index = number / 8;
			bit_index = number % 8;
		}
		switch (bit_index) {
		case 1:
			bitMap[index] = (byte) (bitMap[index] | 0x01);
			break;
		case 2:
			bitMap[index] = (byte) (bitMap[index] | 0x02);
			break;
		case 3:
			bitMap[index] = (byte) (bitMap[index] | 0x04);
			break;
		case 4:
			bitMap[index] = (byte) (bitMap[index] | 0x08);
			break;
		case 5:
			bitMap[index] = (byte) (bitMap[index] | 0x10);
			break;
		case 6:
			bitMap[index] = (byte) (bitMap[index] | 0x20);
			break;
		case 7:
			bitMap[index] = (byte) (bitMap[index] | 0x40);
			break;
		case 8:
			bitMap[index] = (byte) (bitMap[index] | 0x80);
			break;
		}

	}

	public void printBitMap() {
		int size = bitMap.length;
		for (int i = 0; i < size; i++) {

			if ((bitMap[i] & 0x01) == 1) {
				System.out.print(i * 8 + 1 + " ");
			}
			if ((bitMap[i] >> 1 & 0x01) == 1) {
				System.out.print(i * 8 + 2 + " ");
			}
			if ((bitMap[i] >> 2 & 0x01) == 1) {
				System.out.print(i * 8 + 3 + " ");
			}
			if ((bitMap[i] >> 3 & 0x01) == 1) {
				System.out.print(i * 8 + 4 + " ");
			}

			if ((bitMap[i] >> 4 & 0x01) == 1) {
				System.out.print(i * 8 + 5 + " ");
			}
			if ((bitMap[i] >> 5 & 0x01) == 1) {
				System.out.print(i * 8 + 6 + " ");
			}
			if ((bitMap[i] >> 6 & 0x01) == 1) {
				System.out.print(i * 8 + 7 + " ");
			}
			if ((bitMap[i] >> 7 & 0x01) == 1) {
				System.out.print(i * 8 + 8 + " ");
			}
		}
		System.out.println();
	}

}