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

niushao

2020-01-08

关注关注

位图

问题

问题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)
- 重复数字的情况：输出前判断数字在散列表是否存在，存在则按出现次数循环输出。

位图数据结构