Java实现BitMap

BitMap的概念、用法网上介绍很多，在大数据领域用来排序、计数等均有很不错的性能，这里使用Java来实现一下。

命题

给定一百万个int类型整数，所有整数范围在1至1千万之间，对这一百万个整数进行排序，并在有重复数出现时给出提示

问题

1. 如何确定用来存放数据的位图数组bitmap的大小？以及每个数据在bitmap中的位置？
2. 如何对一个int类型的32为bit的某一个bit进行赋值操作？
3. 如何对一个int类型的32为bit的某一个bit进行读取操作？
4. 如何判重？
5. 如何根据bitmap恢复原始数据？

思路

如何确定用来存放数据的位图数组bitmap的大小？

在java中一个int占32位，bitmap的大小取决于数据集合中的最大值，因此bitmap的大小可以简单的计算为：
size = maxValue/32 + 1

如何确定每个数据在bitmap中的位置？

value位于数组bitmap中的index=value/32
value位于数组bitmap[index]这个int中的bit位置offset = value%32 - 1（offset是1移动多少位，位于第六位则需要1移动五位，所以要减一）

如何对一个int类型的32为bit的某一个bit进行赋值操作？

bitmap[index] = bitmap[index] | 1<<offset

1<<offset即为value的bitmap的位置，与目前有的值进行或操作进行合并

如何对一个int类型的32为bit的某一个bit进行读取操作？

bitmap[index] >> offset & 0x01 == 0x01 ? true : false

bitmap[index] >> offset后，如果当前value值已经存在了，则最低位肯定为1，否则为0；此时与0x01进行与操作，若结果为0x01说明对应offset的值已经存在，否则不存在

如何判重？

设置bit时，先保存前值，设置之后如果值没有发生改变，则说明此bit位之前已经为1，即发生了重复

int temp = a[index]
a[index] = a[index] | 1<<offset
temp == a[index]  //说明重复了

如何根据bitmap恢复原始数据？

//遍历顺序输出
for[i, [0,a.length) ]{
  int t = a[i]
    for[j, [0,32) ]{
       t >> j & 0x01 == 0x01 ? true : false
        if(true){
          int data = i*32 + j+1
        }
    }
}

一般面试题中如果要用到BitMap基本都会限制内存，本文直接将所有数据一次性全都读取到内存中，若内存不足直接分批次多次读取数据即可