資料結構

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 
10function charSum(key: string): number {
11  let sum = 0;
12  for (const byte of new TextEncoder().encode(key)) {
13    sum += byte;
14  }
15  return sum;
16}
17 
18class HashTable {
19  private buckets: string[][] = Array.from({ length: 8 }, () => []);
20  private count = 0;
21 
22  constructor(private hash: (key: string) => number = fnv1a) {}
23 
24  private bucketOf(key: string): string[] {
25    return this.buckets[this.hash(key) % this.buckets.length];
26  }
27 
28  has(key: string): boolean {
29    for (const k of this.bucketOf(key)) {
30      if (k === key) return true;
31    }
32    return false;
33  }
34 
35  add(key: string): void {
36    if (this.has(key)) return;
37    this.bucketOf(key).push(key);
38    this.count++;
39    if (this.count / this.buckets.length > 0.75) {
40      this.resize();
41    }
42  }
43 
44  delete(key: string): void {
45    const bucket = this.bucketOf(key);
46    const i = bucket.indexOf(key);
47    if (i === -1) return;
48    bucket.splice(i, 1);
49    this.count--;
50  }
51 
52  private resize(): void {
53    const old = this.buckets;
54    this.buckets = Array.from({ length: old.length * 2 }, () => []);
55    for (const bucket of old) {
56      for (const k of bucket) this.bucketOf(k).push(k);
57    }
58  }
59}
60 
61const DELETED = Symbol("deleted");
62 
63class OpenHashTable {
64  private slots: (string | symbol | null)[] = new Array(8).fill(null);
65  private used = 0; // keys plus tombstones
66  private live = 0;
67 
68  constructor(private hash: (key: string) => number = fnv1a) {}
69 
70  slotOf(key: string): number {
71    let i = this.hash(key) % this.slots.length;
72    while (this.slots[i] !== null) {
73      if (this.slots[i] === key) return i;
74      i = (i + 1) % this.slots.length;
75    }
76    return -1;
77  }
78 
79  has(key: string): boolean {
80    return this.slotOf(key) !== -1;
81  }
82 
83  add(key: string): void {
84    let i = this.hash(key) % this.slots.length;
85    let reuse = -1;
86    while (this.slots[i] !== null) {
87      if (this.slots[i] === key) return;
88      if (this.slots[i] === DELETED && reuse === -1) reuse = i;
89      i = (i + 1) % this.slots.length;
90    }
91    if (reuse === -1) {
92      reuse = i;
93      this.used++;
94    }
95    this.slots[reuse] = key;
96    this.live++;
97    if (this.used / this.slots.length > 2 / 3) this.resize();
98  }
99 
100  delete(key: string): void {
101    const i = this.slotOf(key);
102    if (i === -1) return;
103    this.slots[i] = DELETED;
104    this.live--;
105  }
106 
107  private resize(): void {
108    const old = this.slots;
109    // Mostly live keys: double. Mostly tombstones: same size, swept clean.
110    const size = (this.live + 1) * 3 > old.length ? old.length * 2 : old.length;
111    this.slots = new Array(size).fill(null);
112    this.used = 0;
113    this.live = 0;
114    for (const k of old) {
115      if (typeof k === "string") this.add(k);
116    }
117  }
118}