数据结构与算法简记--位图

位图

问题

问题1：如何实现网页爬虫中url去重功能？

分析

　　传统数据结构散列表、红黑树、跳表这些动态数据结构，都能支持快速地插入、查找数据。

但通常爬虫爬取的网页数量级都比较大，假设为10亿个网页，估算一下散列表存储所需的内存：

为了判重，我们把这 10 亿网页链接存储在散列表中。

假设一个 URL 的平均长度是 64 字节，单纯存储这 10 亿个 URL，需要大约 60GB 的内存空间。

因为散列表必须维持较小的装载因子，才能保证不会出现过多的散列冲突，导致操作的性能下降。

用链表法解决冲突的散列表，还会存储链表指针。所以，如果将这 10 亿个 URL 构建成散列表，那需要的内存空间会远大于 60GB，有可能会超过 100GB。

此时，可用分治思想，分多个机器存储，但作为一个有追求的工程师，应该考虑是否有进一步的优化空间。

位图

考虑一个简单点儿的问题：问题2：有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢？

可以使用一种比较“特殊”的散列表：位图。申请一个大小为 1 亿、数据类型为布尔类型（true 或者 false）的数组。我们将这 1 千万个整数作为数组下标，将对应的数组值设置成 true。

比如，整数 5 对应下标为 5 的数组值设置为 true，也就是 array[5]=true。

判断整数 K 是否在这 1 千万个整数中，可直取 array[K] 的值，true为存在，false为不存在。

优化内存占用

很多编程语言中的boolean类型大小至少为1字节，可优化为1个二进制位，也就是用位图来存储，1字节=8位，内存占用可省至原来的1/8。

位图实现

借助编程语言中提供的数据类型，比如 int、long、char 等类型，通过位运算，用其中的某个位表示某个数字。

public class BitMap { // Java中char类型占16bit，也即是2个字节
  private char[] bytes;
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits;
    this.bytes = new char[nbits/16+1];
  }

  public void set(int k) {
    if (k > nbits) return;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    bytes[byteIndex] |= (1 << bitIndex);
  }

  public boolean get(int k) {
    if (k > nbits) return false;
    int byteIndex = k / 16;
    int bitIndex = k % 16;
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

用散列表存储这 1 千万的数据，数据是 32 位的整型数，需要 4 个字节的存储空间，那总共至少需要 40MB 的存储空间。如果通过位图的话，数字范围在 1 到 1 亿之间，只需要 1 亿个二进制位，也就是 12MB 左右的存储空间就够了。

但位图是按数据范围定义大小的，如果数据范围是1到10亿，就需要120M存储空间，内存占用反而增加了，这时候需要再优化，就要使用布隆过滤器了

布隆过滤器

特点
基于位图的优化
会有误判，应用在可以容忍有一定误判的场景
针对问题2 在数据范围为1到10亿时，布隆过滤器的做法是：
- 仍然使用一个 1 亿个二进制大小的位图，然后通过哈希函数，对数字进行处理，让它落在这 1 到 1 亿范围内。
- 可以把哈希函数设计成 f(x)=x%n。其中，x 表示数字，n 表示位图的大小（1 亿），也就是，对数字跟位图的大小进行取模求余，但这样势必会有散列冲突。
- 降低散列冲突：
  - 使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 X1，X2，X3，…，XK。
  - 把这 K 个数字作为位图中的下标，将对应的 BitMap[X1]，BitMap[X2]，BitMap[X3]，…，BitMap[XK] 都设置成 true，也就是说，用 K 个二进制位，来表示一个数字的存在。
- 会有误判
  - 调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，可以将误判的概率降到非常低。
用布隆过滤器来处理问题1
- 假设需要判重的网页有 10 亿，那我们可以用一个 10 倍大小的位图来存储，也就是 100 亿个二进制位，换算成字节，那就是大约 1.2GB。
- 之前用散列表判重，需要至少 100GB 的空间。相比来讲，布隆过滤器在存储空间的消耗上，降低了非常多。
执行效率
- 布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的。
- 而在散列表的处理方式中，需要读取散列冲突拉链的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的。 CPU 计算可能是要比内存访问更快速的，
- 所以，理论上讲，布隆过滤器的判重方式，更加快速。

思考题

假设我们有 1 亿个整数，数据范围是从 1 到 10 亿，如何快速并且省内存地给这 1 亿个数据从小到大排序？

使用位图算法：数字范围是1到10亿，用位图存储125M（10亿 / 8）就够了;
输入位图
- 将1亿个数字依次添加到位图中：数字是x，则下标为x的位设置为1
- 对于重复的数据，维护一个小的散列表，以数字为key，出现次数为value
排序输出
- 将位图按下标从小到大输出值为1的下标，排序就完成了，时间复杂度为 O(n)
- 重复数字的情况：输出前判断数字在散列表是否存在，存在则按出现次数循环输出。