資料結構

1function hash32(key: string): number {
2  let h = 0x811c9dc5;
3  for (const byte of new TextEncoder().encode(key)) {
4    h = Math.imul(h ^ byte, 0x01000193);
5  }
6  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b);          // mix the bits (MurmurHash3 finaliser)
7  h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
8  return (h ^ (h >>> 16)) >>> 0;
9}
10 
11class HyperLogLog {
12  registers: number[];
13  constructor(private p: number) {                      // m = 2^p registers
14    this.registers = new Array(1 << p).fill(0);
15  }
16 
17  add(key: string): void {
18    const h = hash32(key);
19    const index = h >>> (32 - this.p);
20    const rest = (h << this.p) >>> 0;
21    const rank = rest === 0 ? 33 - this.p : Math.clz32(rest) + 1;
22    if (rank > this.registers[index]) this.registers[index] = rank;
23  }
24 
25  estimate(): number {
26    const m = this.registers.length;
27    const alpha = m === 16 ? 0.673 : m === 32 ? 0.697 : m === 64 ? 0.709 : 0.7213 / (1 + 1.079 / m);
28    let sum = 0, empty = 0;
29    for (const r of this.registers) {
30      sum += 2 ** -r;
31      if (r === 0) empty++;
32    }
33    const raw = (alpha * m * m) / sum;
34    if (raw <= 2.5 * m && empty > 0) return m * Math.log(m / empty);
35    return raw;
36  }
37}
38 
39class CountMinSketch {
40  rows: number[][];
41  constructor(private depth: number, private width: number) {
42    this.rows = Array.from({ length: depth }, () => new Array(width).fill(0));
43  }
44 
45  private columns(key: string): number[] {
46    const h1 = hash32(key);
47    let h2 = h1 ^ 0x9e3779b9;                           // a second hash from the first
48    h2 ^= h2 >>> 16; h2 = Math.imul(h2, 0x85ebca6b);
49    h2 ^= h2 >>> 13; h2 = Math.imul(h2, 0xc2b2ae35);
50    h2 = ((h2 ^ (h2 >>> 16)) | 1) >>> 0;
51    return this.rows.map((_, i) => (h1 + i * h2) % this.width);
52  }
53 
54  add(key: string, count = 1): void {
55    this.columns(key).forEach((col, row) => {
56      this.rows[row][col] += count;
57    });
58  }
59 
60  query(key: string): number {
61    return Math.min(...this.columns(key).map((col, row) => this.rows[row][col]));
62  }
63}