nestjs 手写布隆过滤器

NestJS是一个基于TypeScript的Node.js框架，用于构建高效、可维护的Web应用程序。手写布隆过滤器(Bloom Filter)在NestJS中主要用于空间效率极高的去重场景，它是一种概率型数据结构，可以判断某个元素是否在一个集合中，但不能保证绝对准确，因为存在误判的可能性。

要在NestJS中手写布隆过滤器，你可以按照以下步骤：

1. **创建数组或位数组**：布隆过滤器的核心是多个独立的哈希函数，将每个元素映射到一组位置。这通常是一个位数组，每个位置表示一个哈希值对应的比特状态。

import { Injectable } from '@nestjs/common';
const BUCKET_SIZE = 1000; // 每个桶的大小

@Injectable()
export class BloomFilter {
  private bits: boolean[] = new Array<BIT>(BUCKET_SIZE);
}

2. **实现哈希函数**：为了提高性能，需要选择几个互斥的哈希函数，这里可以用Math库提供的随机数生成函数结合元素作为种子。

private getHashes(key: string): number[] {
  return [
    Math.abs(hashFn(key, 1)),
    Math.abs(hashFn(key, 2)),
    // 添加更多哈希函数...
  ];
}

3. **插入操作**：对于新元素，对所有哈希值对应的桶设置为`true`。

insert(key: string) {
  const hashes = this.getHashes(key);
  for (const hash of hashes) {
    this.bits[hash] = true;
  }
}

4. **查询操作**：检查所有哈希值对应的桶，如果全部为`true`，则返回可能是重复的，否则可能不是。由于误判率的存在，即使所有桶都是`true`也不能确定元素一定在集合里。

contains(key: string): boolean {
  const hashes = this.getHashes(key);
  for (const hash of hashes) {
    if (!this.bits[hash]) {
      return false; // 如果有一个不匹配，直接返回false
    }
  }
  // 全部匹配，可能存在误判
  return true;
}