資料結構

1function fnv1a(key: string): number {
2  let h = 0x811c9dc5;
3  for (const byte of new TextEncoder().encode(key)) {
4    h ^= byte;
5    h = Math.imul(h, 0x01000193);
6  }
7  return h >>> 0;
8}
9 
10class BloomFilter {
11  bits: Uint8Array;
12 
13  constructor(private m: number, private k: number) {
14    this.bits = new Uint8Array(m);
15  }
16 
17  positions(key: string): number[] {
18    const h1 = fnv1a(key);
19    const h2 = (fnv1a("#" + key) | 1) >>> 0;
20    const out: number[] = [];
21    for (let i = 0; i < this.k; i++) {
22      out.push((h1 + i * h2) % this.m);
23    }
24    return out;
25  }
26 
27  add(key: string): void {
28    for (const p of this.positions(key)) {
29      this.bits[p] = 1;
30    }
31  }
32 
33  mightContain(key: string): boolean {
34    for (const p of this.positions(key)) {
35      if (this.bits[p] === 0) return false;
36    }
37    return true;
38  }
39}