java Bitmap 数据结构

Bitmap算法，
问题：对40亿个数据进行排序，数据类型为 int，无相同数据。

思考：关于40亿个数据的排序，首先想如何存储呢？一个int 4个字节，也就是160亿个字节，也就是大概有16GB的数据，现在所有的计算机估计

没有这么大的内存吧，所以我们就可以文件归并排序，也可以分段读入数据在进行Qsort，但是都需要不停地读入文件，可以想象不停地读取文件硬件操作会有多么浪费时间。

 

我们这样都是用4个字节来存储了一个数据，在计算机里都是用二进制进行表示，

例如 5 ：0000 0000 0000 0000 0000 0000 0000 0101

现在引入Bitmap，所谓Bitmap就是用一个bit来表示一个数据。平时32位存储一个数据，我们可以换一种想法，用一个字节32位来存储0-31这32个数据，例如我们对2，1，5，12这四个数据进行由小到大的排序，首先把32位初始化为0，我们可以把这4个数据存储为0000 0000 0000 0000 0001 0000 0010 0110

 

我们就把32位中的分别把 2  1  5  12位置为1，然后从第0位开始遍历，看相应位是否为1，为1就进行输出，就完成了数据从小到大的排序。

 

再返回原题应用Bitmap就可以把16GB的存储空间缩小为16GB/32 = 512M,就可以大大减少读取文件的工作。直接读一次文件存入内存，然后遍历输出就完成了排序。

 

优点：既大量节省了空间，又把时间复杂度降低到O(n)。

不足：如果数据过于稀疏就会有大量无用遍历，浪费时间。