Fork me on GitHub

BitMap 特性解读

Posted on | Edited on | In | Views:

BitMap 特性解读

主要参考：极客时间专栏：数据结构与算法之美 45 | 位图：如何实现网页爬虫中的URL去重功能？

  1. 应用场景：爬虫爬网页时，要避免重复爬取，对网页去重。

  2. 需要暴露的api：add()和isExisted()，即插入跟查询操作。

  3. 要求：① 查询、插入效率高；② 省内存。

  4. 使用位图的思路：

    1. 若有 1千万个数据，这些数字落在范围在 1 到 1 亿之间，不使用位图时，使用 hashMap 时，需要使用 Integer 来存储每个数据，需要 40MB 空间。
    2. 当使用位图时，需要 1 亿个二进制bit 来表示 boolean，即需要 12MB 空间即可。

  5. 使用布隆过滤器的思路：

    1. 背景：以上位图的思路存在限制，如果数据范围过大，比如数字落在 1 到 10 亿之间，那么一旦使用位图，就需要约 120MB 的空间，相比 hashMap 的方式并不节省空间。
    2. 使用布隆过滤器解决以上问题：面对 1 到 10 亿的数据范围，仍然使用一个 1 亿二进制大小的位图，需要使用某哈希函数，对数据进行处理使落到 1 到 1 亿范围内。因为存在哈希冲突的情况，所以使用多个哈希函数进行多重判断，这种方式就叫做布隆过滤器。
    3. 布隆过滤器会对存在的情况进行误判。

  6. 场景难题：

    1. 直存URL的方式(单 URL 长 64Bytes，10 亿个 URL)，至少需要 64×10^9Bytes，即 64GB 的内存，考虑到装载因子，所需内存将更大（甚至超过 100GB）。
    2. 如果采用基于链表的方式解决冲突问题，将无法利用”局部性原理”。
    3. 因为 key 是 url，需要进行字符串匹配，效率不高。

  7. 使用布隆过滤器的解决思路：

    1. 首先计算这 10 亿个 URL 的哈希值。
    2. 然后开辟一个 100 亿二进制大小的位图来存储这些哈希值。
    3. 注：一般可以采用 10 倍，当然还需要考虑内存消耗和判错容忍度。

二进制位表示 boolean 的技术点：

  • 表示 0~nbits 之间的数据是否 existed，同时提供了 get/set 方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 以下就是用 char 数组实现 BitMap 的方法：
public class BitMap { // Java 中 char 类型占 16bit，也即是 2 个字节
  private char[] bytes;
  private int nbits; 
  
  // 构造方法中传入参数 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; // 第几个 char
    int bitIndex = k % 16; // char 中的第几个 bit
    return (bytes[byteIndex] & (1 << bitIndex)) != 0;
  }
}

位图的扩展用法：

  1. 用户的标签过多时可能使得数据库维护大量的 column，办法：使用BitMap，让每个标签维护自己的 BitMap，其中保存着用户的 ID，参考：漫画：Bitmap算法 整合版，使用 BitMap 之后，甚至可以方便地进行交并集运算。

  2. 开源的 BitMap 实现：BitSet、EWAHCompressedBitmap（来自 google 开发）。

    1. EWAHCompressedBitmap对稀疏 BitMap 进行了优化，通过动态扩容、横跨记录的方式(如果是跨度很大的数据，也可以存在临近的位置，只需要记录跨度的大小等)。

    2. EWAHCompressedBitmap源码在：

      1
      2
      3
      4
      5
      6
      <dependency>
        <groupId>com.googlecode.javaewah</groupId>
        <artifactId>JavaEWAH</artifactId>
        <version>1.1.0</version>
      </dependency>

-------------The End-------------