布隆过滤器 Bloom Filter

作用：判断一个元素不在集合中

背景

之前我们要判断一个元素是否在一个集合中，想到的做法是把数据集合取出来，通过数组或者树的结构重新构建。之后达到 O(n) 或 O(logN) 的检索效率

而布隆过滤器是借助哈希表的思想，能够达到 O(1) 的检索效率

实现原理

初始化时，需要将存量数据进行哈希；后续增量数据再逐步添加到哈希表中

需要处理好集群同步、启动数据同步、高可用。 一般不和业务耦合，而是单独另起一个服务来处理

哈希处理时，采用 bitmap （位列表）结构节省空间

由于哈希函数存在冲突的情况，所以哈希表存在并不能说明这个元素存在；但如果哈希表不存在就说明元素真的不存在

如何降低误判？使用多个哈希函数设点，若某函数的所有哈希值都存在表中，大概率说明这个元素真的存在

多个哈希函数可以充分利用硬件并行计算

js 代码实现

示例，不可用于生产环境

class BloomFilter {
  constructor() {
    this.init()
    console.log('init success')
  }
  /**
   * 一个长度为10 亿的比特位
   */
  DEFAULT_SIZE = 256 << 22
  /**
   * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组
   */
  seeds = [3, 5, 7, 11, 13, 31, 37, 61]
  /**
   * 相当于构建 8 个不同的hash算法
   */
  functions = new Array(this.seeds.length);
  /**
   * 初始化布隆过滤器的 bitmap，这里简单的使用 Array
   */
  bitset = new Array(this.DEFAULT_SIZE);
  /**
   * 添加数据
   *
   * @param value 需要加入的值
   */
  add(value) {
    if (value != null) {
      for (let f of this.functions) {
        //计算 hash 值并修改 bitmap 中相应位置为 true
        this.bitset[f.hash(value)] = true;
      }
    }
  }

  /**
   * 判断相应元素是否存在
   * @param value 需要判断的元素
   * @return 结果
   */
  contains(value) {
    if (value == null) {
      return false;
    }
    let ret = true;
    for (let f of this.functions) {
      ret = this.bitset[f.hash(value)];
      // 若存在某个 hash 函数返回 false 则跳出循环
      if (!ret) {
        break;
      }
    }
    return ret;
  }

  init() {

    for (let i = 0; i < this.seeds.length; i++) {
      this.functions[i] = new HashFunction(this.DEFAULT_SIZE, this.seeds[i]);
    }

    // 添加100w数据
    for (let i = 0; i < 1e+6; i++) {
      this.add(String(i));
    }
  }

}


/**
 * 哈希函数
 */
class HashFunction {

  size;
  seed;

  constructor(size, seed) {
    this.size = size;
    this.seed = seed;
  }

  hash(value) {
    let result = 0;
    let len = value.length;
    for (let i = 0; i < len; i++) {
      result = this.seed * result + value.charAt(i);
    }
    return (this.size - 1) & result;
  }
}

let bloom = new BloomFilter()



let test = (val) => {
  let isContain = bloom.contains(val)
  console.log(`元素${val}${isContain ? '' : '不'}存在`)
}

test("99999") // 元素99999存在
test("9999999") // 元素9999999不存在
bloom.add("9999999") // 元素9999999存在
test("9999999")

npm 包

• bloomfilter (opens new window)

变种

支持删除元素：每个哈希位增加标记位，增加元素的时候，所有哈希函数的值其对应位置加 1，删除时则减 1；若无标记位了，则该位置重置

应用

• 网页URL的去重
• 垃圾邮件的判别
• 集合重复元素的判别
• 查询加速（比如基于key-value的存储系统）
• 数据库防止查询击穿
• 使用 BloomFilter 来减少不存在的行或列的磁盘查找。

拓展阅读

• https://baike.baidu.com/item/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8/5384697