Fork me on GitHub

BitMap 特性解读

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
// 以下就是用 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
      <dependency>
      <groupId>com.googlecode.javaewah</groupId>
      <artifactId>JavaEWAH</artifactId>
      <version>1.1.0</version>
      </dependency>
-------------The End-------------