1
package interning
2

3
import "sync"
4

5
// Interner 字符串驻留器，返回整数 ID 作为符号
6
type Interner struct {
7
    mu      sync.RWMutex
8
    strToID map[string]int
9
    idToStr []string
10
}
11

12
func NewInterner() *Interner {
13
    return &Interner{
14
        strToID: make(map[string]int),
15
    }
16
}
17

18
// Intern 驻留字符串，返回符号 ID
19
// 相同字符串始终返回相同 ID
20
func (it *Interner) Intern(s string) int {
21
    it.mu.RLock()
22
    if id, ok := it.strToID[s]; ok {
23
        it.mu.RUnlock()
24
        return id // 命中：返回已有 ID
25
    }
26
    it.mu.RUnlock()
27

28
    it.mu.Lock()
29
    defer it.mu.Unlock()
30

31
    // 双重检查
32
    if id, ok := it.strToID[s]; ok {
33
        return id
34
    }
35

36
    id := len(it.idToStr)
37
    it.strToID[s] = id
38
    it.idToStr = append(it.idToStr, s)
39
    return id
40
}
41

42
// Resolve 通过 ID 反查原始字符串
43
func (it *Interner) Resolve(id int) (string, bool) {
44
    it.mu.RLock()
45
    defer it.mu.RUnlock()
46
    if id < 0 || id >= len(it.idToStr) {
47
        return "", false
48
    }
49
    return it.idToStr[id], true
50
}
51

52
// Size 返回驻留的唯一字符串数量
53
func (it *Interner) Size() int {
54
    it.mu.RLock()
55
    defer it.mu.RUnlock()
56
    return len(it.idToStr)
57
}

1
func compile(sources []string) {
2
    interner := interning.NewInterner()
3

4
    // 所有标识符通过驻留比较
5
    id1 := interner.Intern("String")
6
    id2 := interner.Intern("String")
7
    // 比较两个标识符：整数比较 O(1)
8
    if id1 == id2 {
9
        // 同一个符号，无需逐字符比较
10
    }
11
}

1
class StringInterner {
2
  private strToId = new Map<string, number>();
3
  private idToStr: string[] = [];
4

5
  // 驻留字符串，返回符号 ID
6
  intern(s: string): number {
7
    const existing = this.strToId.get(s);
8
    if (existing !== undefined) return existing;
9

10
    const id = this.idToStr.length;
11
    this.strToId.set(s, id);
12
    this.idToStr.push(s);
13
    return id;
14
  }
15

16
  // 通过 ID 反查字符串
17
  resolve(id: number): string | undefined {
18
    return this.idToStr[id];
19
  }
20

21
  get size(): number {
22
    return this.idToStr.length;
23
  }
24
}
25

26
// 使用示例：JSON 解析器字段名去重
27
const fieldInterner = new StringInterner();
28

29
function parseObject(keys: string[]): Map<number, unknown> {
30
  const result = new Map<number, unknown>();
31
  for (const key of keys) {
32
    // 重复的字段名（如 "name"、"age"）只存储一份
33
    const symbolId = fieldInterner.intern(key);
34
    result.set(symbolId, null);
35
  }
36
  return result;
37
}