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

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

 

 

 

对于几亿int数据如要查找出相等的数据，利用Bitmap算法，只是使byte达到了极限，也是一种解决问题的一种方法。下一篇描述讲一下源代码的

描写。

评论

18 楼 luozhong915127 2012-09-15  

逸情公子 写道

引用

首先把32位初始化为0，
我们可以把这4个数据存储为0000 0000 0000 0000 0001 0000 0010 0110

这个是怎么存储出来的，没看明白。。

位运算

首先，明白存储是按字节存储的。接着就明白，一个整数要四个字节，而现在用Bitmap一个整数就对应一个整数。例如，这么一串数据byte[a[i]]={0,0,0,0,1,0,1,0}  就代表在整数为：1,3 ;因为a[1]=1,a[3]=1;就这样存储的。

17 楼 逸情公子 2012-08-14  

引用

首先把32位初始化为0，
我们可以把这4个数据存储为0000 0000 0000 0000 0001 0000 0010 0110

这个是怎么存储出来的，没看明白。。

位运算

16 楼 paladin1988 2012-08-14  

首先把32位初始化为0，
我们可以把这4个数据存储为0000 0000 0000 0000 0001 0000 0010 0110

这个是怎么存储出来的，没看明白。。

15 楼 luozhong915127 2012-08-02  

MyEyeOfJava 写道

nagat1111 写道

16G内存到处都是。。。

最看不起你这种的。。。

每个人都是从看不起，到看得起的。你认为本来或者一直被别人看得起的人。

14 楼 MyEyeOfJava 2012-08-01  

nagat1111 写道

16G内存到处都是。。。

最看不起你这种的。。。

13 楼 luozhong915127 2012-03-25  

请问一下，任你的负数有多大吧，转化为整数，他也只是是个1呀，转化的这个整数始终是下标 而已呀。

12 楼 wooyon 2012-03-25  

luozhong915127 写道

请问一下，你以为电脑就回去识别负数，只是我去定义正数与负数而已，他只能去识别二进制而已，在硬件中，底层的设计用高低电平来表示0和1.你以为负电压可以表示负数是吧。负数相等于原码取反加1呀，你应该学过计算机基础呀。大哥呀

晕死，跟我谈教材，算法问题，还扯蛋到硬件，大哥　这和硬件有个毛联系啊！你有没弄清我质问的内容啊？！　我的意思是　按你说的这种思路，理论上正负数的差别会使你的操作付出双倍代价，而不是简单的一句“那负数也可以转化正数呀。”——大哥，这可不仅是正负转化的操作！！！

11 楼 luozhong915127 2012-03-22  

请问一下，你以为电脑就回去识别负数，只是我去定义正数与负数而已，他只能去识别二进制而已，在硬件中，底层的设计用高低电平来表示0和1.你以为负电压可以表示负数是吧。负数相等于原码取反加1呀，你应该学过计算机基础呀。大哥呀

10 楼 pywepe 2012-03-22  

  我记得有一种算法就是这种思想,忘记叫什么名字了
  n位上标记一下,表示n

9 楼 wooyon 2012-03-22  

对这个种问题，直接的做法是分而治之，怎么会有这种空想，按这种想法，其中的负数问题可不是这么简单的一句能摆平的哦，你晓不晓得负数的二进位怎么表示的啊？

8 楼 luozhong915127 2012-03-22  

那负数也可以转化正数呀。

7 楼 b_l_east 2012-03-22  

负数怎么办？！

6 楼 nagat1111 2012-03-22  

16G内存到处都是。。。

5 楼 luozhong915127 2012-03-21  

byte可以存储8*2^32就能存储2G呀，他是利用0与1来表示的。你可看一下这个图

4 楼 luozhong915127 2012-03-21  

Bitmap可以自己写一个，专门用于算法的描写，Bitmap只是去解决一个巨大的数怎样减小存储空间。那里面的byte是到极限了。

3 楼 canghailan 2012-03-21  

java.util.BitSet

2 楼 youjianbo_han_87 2012-03-21  

问个问题，如果int值比较大

"用一个字节32位来存储0-31这32个数据" 这句是不是就有问题，一个字节不一定能放下32个数。

1 楼 逸情公子 2012-03-21  

貌似J2SE中没有BitMap啊。这该肿么办呀？