位图应用场合

位图主要用于快速检索关键字状态，通常要求关键字是一个连续的序列（或者关键字是一个连续序列中的大部分）， 最基本的情况，使用1bit标示一个关键字的状态（可标示两种状态），但根据需要也可以使用2bit（标示4种状态），3bit（标示8种状态），当一个状态标示需要的位数达到32bit时，就演变成来一个整型数组了。

 

位图的主要应用场合：标示连续（或接近连续，即大部分会出现）的关键字序列的状态（状态数/关键字个数 越小越好）。位图还可以用于实现诸如BloomFilter（用于快速判断一个元素是否属于某个集合）等扩展结构，这里只讨论纯位图的应用场景。

 

应用场景1：磁盘空闲块的管理

Ext3文件系统中使用位图来管理磁盘空闲块（空闲inode节点）。文件系统创建后，该文件系统拥有的块数以及inode节点数都是确定的，数据块区包含一系列连续的块（块号是连续的），于是可以用位图来标示数据块的分配状态（分配、未分配两种状态，1bit即可标示）。

 

如下图，假设ext3的数据块从128开始，一直到1024，则需要1024-128 = 996bit = 128字节的位图空间。如下图，第1bit标示128号块已经被分配，第2bit标示129号块未被分配，依次类推。使用位图的高效性在于：1bit标示状态，节省存储空间，通过关键字来定位位图（偏移是固定的），效率高。

1

0

1

1

….

 

应用场景2：区域服务器路由

腾讯的QQ号用一个数字标示，范围从0到20亿，每个QQ号都有可能出现，所有的QQ号被分散的存储北京、上海、深圳、武汉四个城市的服务器中，现在需要一个路由服务器快速的将登陆的QQ路由到正确的服务器，路由服务器可以读取四个QQ服务器的数据，并构建路由表（需全部存在内存中，内存限制1G），路由表该如何存储？

关键：QQ号从0-20亿，每个号码都有可能出现；服务器通过0、1、2、3标示，这四种状态可以用2bit来标示，于是可以考虑使用位图来描述路由表。

解法：从0~20亿，为每个QQ号分配2bit，路由服务器从QQ服务器中获取信息，并设置QQ于服务器号的对应关系。当QQ登录时，路由服务器根据QQ号定位到其对应的状态，并返回对应的服务器号。总的内存大小20亿 * 2 /8 = 5亿字节(约为0.5G)。

 

应用场景3：高效排序

数据库里存了很多800电话号码，数量特别大，以至于内存放不下，如何排序，时间比空间更重要？电话号码类似于800-810-5555。

关键：去掉电话号码的800后面就是7位的十进制整数，每个整数都有可能出现而且不会重复出现，可以采用各种排序算法对这些数据进行排序，但时间复杂度都在O(NlogN)及以上。

解法：因每个七位以内的整数都有可能出现，可以用1bit来标示电话号是否出现，遍历整个电话号序列，设置相应的位，遍历位图收集位被设置的号码即可。

扩展：对于上述问题，每个电话号码最多出现一次，如果关键字可能多次重复出现，但关键字范围比较确定且很集中的情况下，也可使用位图（根据关键字最多可能出现的次数确定每个关键字需要的位数），但此时的位图通常会是一个整型数组，数组内容为对应位置关键字出现的次数，在执行收集过程时，对于每个关键字要收集多次（根据数组的值确定）。如有一大批职工的年龄信息，需要对这些职工按照年龄信息进行排序，则只需要建立一个长度为100的数组，每个数组为对应年龄人的个数，扫描一遍数组，收集年龄信息即可。