给40亿个不重复的unsigned int的整数，没排序。再给一个数，快速判断这个数是否存在40亿个整数中？

什么是Bitmap

所谓Bitmap，就是用一个bit位来映射某个元素的value值，key则是该元素值。

假设我们要对5个不重复的数（4，7，2，5，3）排序。确定最大值是7，数值范围是0~7，共8个数，需要8bit，即1byte。

1、首先分配1byte空间，所有bit位赋值0：

1

00000000  -->  76543210

每一个bit位，映射为一个整数值

2、遍历这5个数，在数值对应的bit位赋值1：

12345

00010000 （4）10010000 （7）10010100 （2）10110100 （5）10111100 （3）

3、最终结果为10111100，遍历这8个bit位，将值为1所映射的value值输出：（7，5，4，3，2）

这里的排序算法是桶排序。桶排序是常见排序里最快的，但也是最耗空间的。结合Bitmap，鱼和熊掌兼得。

解决方案

因为40亿是不重复的unsigned int整数，而unsigned int最大值为2^32 =4294967296， 大专栏  Bitmap算法不超过43亿。建立Bitmap需要内存为：2^32 /8/1024/1024=512MB。

对于给定的任一数，查看Bitmap中对应的bit位，1表示存在，0表示不存在。

BitSet类

Java中对应的实现是BitSet类，非线程安全

12345678910

public static void (String[] args) {    int[] intArray = { 4, 7, 2, 5, 3 };    BitSet bitSet = new BitSet(8);    for (int i = 0; i < intArray.length; i++) {        bitSet.set(intArray[i], true);    }    System.out.println(bitSet);}

Bitmap应用场景

Bitmap用来存储大规模数据，可进行数据的快速查找、判重、统计