Фильтр Блума

1class BloomFilter {
2  private bits: Uint8Array
3 
4  constructor(private size: number, private hashCount: number) {
5    this.bits = new Uint8Array(size)
6  }
7 
8  add(item: string): void {
9    for (const h of this.hashes(item)) this.bits[h] = 1
10  }
11 
12  mightContain(item: string): boolean {
13    return this.hashes(item).every((h) => this.bits[h] === 1)
14  }
15 
16  // «точно нет» надёжно; «может быть» — с вероятностью ложного срабатывания
17  private *hashes(item: string): Generator<number> {
18    let h = 0
19    for (const ch of item) h = (h * 31 + ch.charCodeAt(0)) >>> 0
20    for (let i = 0; i < this.hashCount; i++) {
21      h = (h * 31 + i) >>> 0
22      yield h % this.size
23    }
24  }
25}