位图（Bit-map）

位图（Bit-map）就是用一个 bit 位来标记某个元素对应的 value， 而 key 即是该元素。由于采 用了 bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

位图通过使用 bit 数组来表示某些元素是否存在，可进行数据的快速查找、判重、删除，一般来说数 据范围是 int 的 10 倍以下。

例如要对 {4,7,2,5,3} 进行排序，可以设置一个范围为 0~8 的比特数组，读入数据之后将比特数组第 2、3、4、5、7 位置设置为 1。最后从头遍历比特数组，将比特数组值为 1 的数据读出得到 {2,3,4,5,7} 这个已排序的数据。

1. 2.5 亿个数的去重

问题

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

分析

采用 2-Bitmap（即每个整数分配 2 bit：00 表示不存在，01表示出现一次，10 表示多次，11 表示无意义）。

这样，所占内存 2^32 * 2 bit = 1 GB。

步骤

  • 扫描。
    扫描这 2.5 亿个整数，查看 Bitmap 中相对应位， 如果是 00 变 01，01 变 10，10 保持不变。

  • 输出。
    查看对应位为 01 的整数，输出即可。

2. 整数的快速查询

问题

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

分析

使用用位图的方法，40_10^8 = 4 _10^9 bit = 500 M，所以可以申请 512M 的内存，一个 bit 位代表一个 unsignedint 值。

步骤

读入 40 亿个数，设置相应的 bit 位，读入要查询的数，查看相应 bit 位是否为 1，为 1 表示存在，为 0 表示不存在。