带你读《图解算法小抄》十一、布隆过滤器（2）

export default class BloomFilter {
  /**
   * @param {number} size - 存储区的大小。
   */
  constructor(size = 100) {
    // 布隆过滤器的大小直接影响误报的可能性。
    // 大小越大，误报的可能性越低。
    this.size = size;
    this.storage = this.createStore(size);
  }
  /**
   * @param {string} item
   */
  insert(item) {
    const hashValues = this.getHashValues(item);
    // 将每个hash值索引设置为true。
    hashValues.forEach((val) => this.storage.setValue(val));
  }
  /**
   * @param {string} item
   * @return {boolean}
   */
  mayContain(item) {
    const hashValues = this.getHashValues(item);
    for (let hashIndex = 0; hashIndex < hashValues.length; hashIndex += 1) {
      if (!this.storage.getValue(hashValues[hashIndex])) {
        // 我们知道该项目肯定未被插入。
        return false;
      }
    }
    // 该项可能插入或可能未插入。
    return true;
  }
  /**
   * 为过滤器创建数据存储。
   * 我们使用此方法生成存储以封装数据本身并只提供访问
   * 必要方法的接口。
   *
   * @param {number} size
   * @return {Object}
   */
  createStore(size) {
    const storage = [];
    // 将所有索引初始化为false
    for (let storageCellIndex = 0; storageCellIndex < size; storageCellIndex += 1) {
      storage.push(false);
    }
    const storageInterface = {
      getValue(index) {
        return storage[index];
      },
      setValue(index) {
        storage[index] = true;
      },
    };
    return storageInterface;
  }
  /**
   * @param {string} item
   * @return {number}
   */
  hash1(item) {
    let hash = 0;
    for (let charIndex = 0; charIndex < item.length; charIndex += 1) {
      const char = item.charCodeAt(charIndex);
      hash = (hash << 5) + hash + char;
      hash &= hash; // 转换为32位整数
      hash = Math.abs(hash);
    }
    return hash % this.size;
  }
  /**
   * @param {string} item
   * @return {number}
   */
  hash2(item) {
    let hash = 5381;
    for (let charIndex = 0; charIndex < item.length; charIndex += 1) {
      const char = item.charCodeAt(charIndex);
      hash = (hash << 5) + hash + char; /* hash * 33 + c */
    }
    return Math.abs(hash % this.size);
  }
  /**
   * @param {string} item
   * @return {number}
   */
  hash3(item) {
    let hash = 0;
    for (let charIndex = 0; charIndex < item.length; charIndex += 1) {
      const char = item.charCodeAt(charIndex);
      hash = (hash << 5) - hash;
      hash += char;
      hash &= hash; // 转换为32位整数
    }
  return Math.abs(hash % this.size);
  }
  /**
   * 在输入上运行所有3个哈希函数并返回结果数组。
   *
   * @param {string} item
   * @return {number[]}
   */
  getHashValues(item) {
    return [
      this.hash1(item),
      this.hash2(item),
      this.hash3(item),
    ];
  }}