系統設計

1const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
2 
3function encode(n: number, length: number): string {
4  let code = "";
5  for (let i = 0; i < length; i++) {
6    code = ALPHABET[n % 62] + code;
7    n = Math.floor(n / 62);
8  }
9  return code;
10}
11 
12function fnv1a(s: string): number {
13  let h = 0x811c9dc5;
14  for (let i = 0; i < s.length; i++) h = Math.imul(h ^ s.charCodeAt(i), 0x01000193);
15  return h >>> 0;
16}
17 
18class Shortener {
19  private db = new Map<string, string>();    // code -> long URL
20  private cache = new Map<string, string>(); // oldest use first
21  private counter = 0;
22 
23  constructor(
24    private strategy: "hash" | "counter" | "random",
25    private length: number,
26    private nextRandom: () => number = () => Math.floor(Math.random() * 2 ** 32),
27    private cacheSize = 100,
28  ) {}
29 
30  shorten(url: string): string {
31    const space = 62 ** this.length;
32    for (let attempt = 0; ; attempt++) {
33      let n: number;
34      if (this.strategy === "counter") n = this.counter++;
35      else if (this.strategy === "hash") {
36        n = fnv1a(attempt === 0 ? url : url + "#" + attempt);
37      } else n = this.nextRandom();
38      const code = encode(n % space, this.length);
39      if (!this.db.has(code)) {
40        this.db.set(code, url);
41        return code;
42      }
43    }
44  }
45 
46  resolve(code: string): string | undefined {
47    const hit = this.cache.get(code);
48    if (hit !== undefined) {
49      this.cache.delete(code);
50      this.cache.set(code, hit);
51      return hit;
52    }
53    const url = this.db.get(code);
54    if (url === undefined) return undefined;
55    this.cache.set(code, url);
56    if (this.cache.size > this.cacheSize) {
57      this.cache.delete(this.cache.keys().next().value!);
58    }
59    return url;
60  }
61}