具体算法3 - 位图&布隆过滤器

本章关键词

大量数据存储、查找、判重 、布尔代数、节省内存、小概率容错

布隆过滤器不是一个算法，确切的来说，它是一个数据结构。那么为什么将它归结为算法呢？因为它提供了一个全新的处理思路，也就让我们在设计算法的时候有了一个好用的工具。

问题解析

我们想象这样一个场景：在一个网络爬虫中，你需要实现对网页的去重功能，我们需要判断网页的 URL 是否已经被爬取过，如果已经被爬取，则不必再爬取网页。

分析：这个应用的场景其实非常好处理，最简单的思路就是使用散列表进行去重。但是，如果我们需要爬取的网页非常多，比如超过 100 亿，使用散列表存储信息就会耗费巨量的存储空间。如果我们只是需要完成添加和数据去重，有没有更加高效且节省存储空间的方法呢？

答案是肯定的，那就是使用位图&布隆过滤器。

算法解析

布隆过滤器是在位图的基础上完成的，所以我们要首先了解位图。

1.位图
1.1概念
首先我们看一个简单一点的场景：我们有 1 千万个整数，整数的范围在 1 到 1 亿之间。如何快速查找某个整数是否在这 1 千万个整数中呢？

当然，这个问题可以使用散列表解决。不过，我们可以使用一种比较 “特殊” 的散列表来实现，这就是 位图。

在散列表中，存储的数据可能是指针、数字、字符...而位图的特殊之处在于，它的数据元素为一个二进制为，即 0(true) 或者 1(false) 。

以上面的例子为例，我们可以申请一个大小为 1 亿，数据类型为 bool 类型的数组。我们将需要判定的一千万个整数作为数组下标，将对应的数组设置成 true。例如，在数据中出现了 5 ，我们可以设置 array[5] = true。

当我们要查询某个整数 K 是否在数据中的时候，只需要查询对应的数组 array[K] 的值，如果为 true，证明存在，反之不存在。

1.2二进制位的表示
在许多编程语言中提供的 bool 类型是 1字节 的，这样算来，并不能节省太多空间。那么，如何在编程语言中表示二进位呢？
这里就需要用到位运算了，我们可以借助计算机中的内置类型，通过位运算表示某个位置的二进制位。这里使用专栏作者给出的代码解释：

public class BitMap { // Java中char类型占2个字节，即16bit
  private char[] bytes; // 我们使用char类型作为存储二进制的基本类型
  private int nbits;
  
  public BitMap(int nbits) {
    this.nbits = nbits; // 一共有 nbits 个二进制位需要保存
    this.bytes = new char[nbits/16+1]; //  一个 char 可以保存 16 个 bit ，所以需要 nbit/16+1 个 char
  }

  public void set(int k) {
    if (k > nbits) return;
    int byteIndex = k / 16; // 计算 k 会落到哪个 char 上，即在 char[ k / 16 ] 中包含了 k
    int bitIndex = k % 16; // 计算 k 会落到 char 到哪一位上，即 char[k / 16] 中的第 k % 16 -1 个 bit （-1是因为数组从 0 开始计数）
    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.3位图的问题
在前面的例子中，数据的范围在 0~ 1亿，所以我们开辟了 1亿 个bit，如果条件改成我们有 1 千万个整数，整数的范围在 1 到 100 亿之间。这时候，我们该怎么办呢？如果你开辟 100 亿个 bit，耗费的空间反而比散列表还要大。

针对这个问题，我们建立了布隆过滤器

2.布隆过滤器
2.1概念
布隆过滤器的思想，是在位图中添加多个哈希函数，减小需要开辟的存储空间。

借用之前的例子，我们设计一个 f(x) = x%n 的哈希函数（x代表数字，n代表你想要开辟的存储空间，这里我们设置 n=1亿），就可以将需要开辟的空间大小从 100亿 缩小为 1亿 。

当然，使用哈希函数一大问题是会存在散列冲突，针对这种情况，我们可以使用多个哈希函数共同确定一个一个数是否存在：

我们使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 X1​，X2​，X3​，…，XK​。我们把这 K 个数字作为位图中的下标，将对应的 BitMap[X1​]，BitMap[X2​]，BitMap[X3​]，…，BitMap[XK​]都设置成 true，也就是说，我们用 K 个二进制位，来表示一个数字的存在。
当我们要查询某个数字是否存在的时候，我们用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1​，Y2​，Y3​，…，YK​。我们看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。

下面的图可能会帮助你理解： 布隆过滤器.jpg

2.2布隆过滤器的缺陷
敏感的朋友可能已经发现了，使用布隆过滤器可能会出现判断错误的情况：

布隆过滤器的误判有一个特点，那就是，它只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。不过，只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。

请看这个图： 布隆过滤器-错误.jpg

所以，布隆过滤器只能使用在可以容忍一定错误的情境下。

3.性能分析
布隆过滤器在一定条件下可以替代散列表，在空间上，布隆过滤器无疑会减少非常多的空间消耗。而在时间上，它的表现是否依然优秀呢？答案是肯定的：

布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的。而在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的。我们知道 CPU 计算可能是要比内存访问更快速的，所以，理论上讲，布隆过滤器的判重方式，更加快速。

总结

这一节中，我们学习了位图和布隆过滤器，但是我最想说的，还是对二进制位的使用：

• 一个二进制位只能表示 0 或 1 ，所以它能表达的信息有限
• 二进制位最适合表达 “是” 或 “否”，从这个思路延伸下去，我暂时可以想到这样几个应用场景：

1. 查询某个元素 是否 在一个集合中
2. 根据布尔代数，二进制可以进行 与 、或 、非 三种运算。
3. 由上一条扩展，我们可以查询 某个既在 A 集合 又在 B 集合中的元素（使用 与 运算）。等

• 哈希函数的使用：可以减少对空间的占用
• 如果你对数组的下标足够敏感，你可以使用下标存储一定的信息
• 布尔过滤器一定会出现误判
• 如果想了解更多内容，你可以看这里

---

以上就是本节的所有内容希望对你有所收获

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间