数据结构之位图

介绍

（20120511）位图就是通过将数组下标与应用中的一些值关联，数组中该下标所指定的位置上的元素可以用来标识应用中值的情况（是否存在 or 数目 or 。。。）。

 

位图中的值可以是计数、标识（如例1）。

可以运用在快速查找、排重、删除？、排序、压缩数据等。

实现

不同语言版本

相关应用

压缩

 

 

排序

 

例：有1000,0000个数，如果想对这些数排序，并且想尽量少用内存，该如何设计数据结构和排序算法？

方案1 ：采用32Bitmap（即容量为1000,1000/32，每个元素为32bit）位图中元素为整型32bit（下标为0-31），位图中元素可以存储相邻32个数是否存在的信息。例如89256 mod 32=2789…8，这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1。89257 mod 32=2789…9，设置a[2789]中元素的第9位为1。在将1000,0000个数都存入位图后，然后进行排序，遍历位图，将元素通过 ”位操作“还原为原值，输出。

 

注：来自http://blog.csdn.net/QIBAOYUAN/article/details/5914662 ，该文利用位图实现了压缩和排序，压缩体现在位图中每个元素为32位，将某个数与32取模，将取模后值对应到32位中的某位上设置为1，这样，32位就能保存相邻的32个数是否存在的信息。这样位图的大小就可以缩小到10000000/32.

 

 

搜索

 

例1：在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

 方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

 

例2：在Map3搜索例子中，通过将url的个数存储在bitmap中，可以通过歌曲id来快速找到歌曲url个数。

http://tech.techweb.com.cn/thread-222923-1-1.html

 

例3：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

 

最简单的方法就是将这40亿个整数载入到数组中，然后遍历，看给定的数是否在这个数组中。但这是一个非常粗糙的方法，没有考虑存储空间和搜索效率问题。

 

可以考虑快速排序+二分查找，但是内存占用还是很大，并且如果40亿数据还有增加，涉及重排序。能不能有一种结构不用排序，占用内存比较少，面对增量数据也能从容应对呢？——bitmap

构建一个bitmap，元素为1bit（0表示无，1表示有），遍历40亿数据，设置bitmap里相应位置上元素值为1，搜索时只要根据目标值去bitmap里查找该位置上元素即可。

 

设计搜索剪枝时，需要保存已经搜索过的历史信息，有些情况下，可以使用位图减小历史信息数据所占空间。

 

扩展

 

Bloom filter

参考阅读

1. http://dongxicheng.org/structure/bitmap/ 

C++的STL中有bitmap类/