海量数据处理（3）：布隆过滤器

一、简介

布隆过滤器（Bloom Filter，BF）对普通的哈希表做了进一步的改进，是一种更省空间的哈希表。当碰到内存不够的问题时，BF就是一个很好的选择。BF的两个功能：检测一个元素在不在一个集合中、统计一个元素的出现次数（实际上就是map的作用）。

BF虽然节省了空间，但同样也有一个副作用，即存在 False Positive（正误识）。 简单的说就是，如果是 Hash 的话，他说这个元素在集合里，那就是在集合里。而如果是 BF 的话，他说在集合里，你别当真，有一定概率这个元素不在集合里。也就是说 BF 会给出一个错误的（False）肯定（Positive）。

一个更完整的BloomFilter会包含以下两个部分：

• k 个完全独立的哈希函数
• 一个很大的数组

根据处理的问题的不同，BloomFilter可以分为：

• 标准型布隆过滤器（Standard Bloom Filter， SBF，相当于 HashSet）
• 计数型布隆过滤器（Counting Bloom Filter， CBF，相当于 HashMap）

对于 SBF，其包含的大数组的类型为 Boolean 类型。对于 CBF，其包含的大数组的类型为整数类型。

最常见的hash函数如下

# 这个算法，相当于把一个字符串当做了 31 进制，然后转换为整数。一边转换的过程中一边对 hashsize 取模，避免溢出。
# 要设计k个完全独立的hash函数，只要把31改成其他素数如37、41等。尽量不要合数，会增加哈希冲突概率
def hashfunc(string, hashsize):
    code = 0
    for c in string:
        code = code * 31 + ord(c)
        code = code % hashsize

    return code

二、实现标准布隆过滤器

SBF相当于HashSet，支持添加元素以及判断一个元素是否在集合中。（允许 False Positive）

实现：

• 初始化：开一个足够大的 boolean 数组，初始值都是 false。
• 插入一个元素：通过 k 个哈希函数，计算出元素的 k 个哈希值，对 boolean 数组的长度取模之后，标记对应的 k 个位置上的值为 true。
• 查询一个元素：通过同样的 k 哈希函数，在 boolean 数组中取出对应的 k 个位置上的值。如果都是 true，则表示该元素可能存在，如果有一个 false，则表示一定不存在。

LintCode 556. Standard Bloom Filter

在这边使用了BitSet，它是Java中的一种数据结构。主要存储的是二进制位，每一位只用来存储0，1值，0代表false，1代表true。0表示该数据没有出现过，1表示出现过。

public class StandardBloomFilter {
  public BitSet bitSet;   //Bitset类创建一种特殊类型的数组来保存位值。BitSet中数组大小会随需要增加。
  public int k;
  public List<HashFunction> hashFunctions;

  // 构造方法, 创建k个hash方法
  public StandardBloomFilter(int k) {
      this.k = k;
      hashFunctions = new ArrayList<>();
      for (int i = 0; i < k; i++) {
          hashFunctions.add(new HashFunction(100000 + i, 2 * i + 3));
      }
      bitSet = new BitSet(100000 + k);  //MOD有多大，bitSet就要有多少个位
  }

  /**
   * @param word
   * 往布隆过滤器中加入一个字符串
   * 用每个hash函数计算下hash值，得到了hash值就得到了在bitSet中对应的位，并将对应的位置成true（1）
   */
  public void add(String word) {
      for (int i = 0; i < k; i++) {
          int pos = hashFunctions.get(i).hash(word);
          bitSet.set(pos);
      }
  }

  //检查字符串是否在过滤器中
  public boolean contains(String word) {
      for (int i = 0; i < k; i++) {
          int pos = hashFunctions.get(i).hash(word);
          //如果有一处为false(0)，那就return false
          if (!bitSet.get(pos)) {
              return false;
          }
      }
      return true;
  }
}

//包装成类，每一个对象就是不同的hash函数
class HashFunction{
  public int MOD;     //MOD即基数，用于取模
  public int seed;    //seed相当于进制

  public HashFunction(int MOD, int seed) {
      this.MOD = MOD;
      this.seed = seed;
  }

  public int hash(String s) {
      int res = 0;
      int n = s.length();
      for (int i = 0; i < n; i++) {
          res += res * seed + s.charAt(i);
          res %= MOD;
      }
      return res;
  }
}

三、实现计数型布隆过滤器

对SBF稍作改动，把存储所用的 boolean 数组改为 int 数组，就成为了可以计数的布隆过滤器。这个数据结构类似 Java 中的 HashMap，但只能用作计数。支持添加元素以及统计某个元素在该集合中出现的次数，统计的次数可能会比实际出现次数要大一些。

实现：

• 初始化：开一个足够大的 int 数组，初始值都是 0。
• 插入一个元素：通过 k 个哈希函数，计算出元素的 k 个哈希值，对 int 数组的长度取模之后，将对应的 k 个位置上的值都加一。
• 查询一个元素的出现次数：通过同样的 k 哈希函数，在 int 数组中取出对应的 k 个位置上的值。并取其中的最小值来作为该元素的出现次数预估。

public class CountingBloomFilter {

    public int[] bits;
    public int k;
    public List<HashFunction> hashFunctions;

    public CountingBloomFilter(int k) {
        this.k = k;
        hashFunctions = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            hashFunctions.add(new HashFunction(100000 + i, 2 * i + 3));
        }
        bits = new int[100000 + k];     //MOD最大值即可
    }

    // 往布隆过滤器中加入一个字符串
    public void add(String word) {
        for (int i = 0; i < k; i++) {
            int pos = hashFunctions.get(i).hash(word);
            bits[pos]++;
        }
    }

    // 从布隆计数器中删除一个字符串
    public void remove(String word) {
        for (int i = 0; i < k; i++) {
            int pos = hashFunctions.get(i).hash(word);
            bits[pos]--;    //这边改一下即可
        }
    }

    // 检查一个字符串是否在布隆过滤器中
    // 需要得到最小的次数（虽然可能依旧偏大），如果存在最小的次数为0，那这个字符串必不存在于CBF中
    public boolean contains(String word) {
        for (int i = 0; i < k; i++) {
            int pos = hashFunctions.get(i).hash(word);
            if (bits[pos] <= 0) {
                return false;
            }
        }
        return true;
    }
}

class HashFunction{
    public int MOD;     //MOD即基数，用于取模
    public int seed;    //seed相当于进制

    public HashFunction(int MOD, int seed) {
        this.MOD = MOD;
        this.seed = seed;
    }

    public int hash(String s) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            res += res * seed + s.charAt(i);
            res %= MOD;
        }
        return res;
    }
}