Bloom Filter Algoritması

1class BloomFilter {
2  private bits: boolean[];
3  constructor(private size: number) { this.bits = Array(size).fill(false); }
4  private hash(value: string): number {
5    let hash = 0;
6    for (let i = 0; i < value.length; i++) { hash = (hash * 31 + value.charCodeAt(i)) >>> 0; }
7    return hash;
8  }
9  add(value: string) {
10    for (const index of this.indexes(value)) { this.bits[index] = true; }
11  }
12  mightContain(value: string): boolean {
13    return this.indexes(value).every((index) => this.bits[index]);
14  }
15  private indexes(value: string): number[] {
16    const h1 = this.hash(value) % this.size;
17    const h2 = this.hash(value + ':salt') % this.size || 1;
18    return [h1, (h1 + h2) % this.size, (h1 + 2 * h2) % this.size];
19  }
20}