Lua VM 字符串池机制详解

Lua 虚拟机（VM）通过字符串池（String Interning）实现字符串的高效管理与复用，核心是全局哈希表结构和字符串去重逻辑。以下分步解析其实现原理。

---

1. 字符串池的核心目标

• 内存优化：避免相同字符串的重复存储，所有字符串在池中唯一存在。
• 快速比较：字符串身份比较（如 str1 == str2）简化为指针比对，时间复杂度 $O(1)$。

---

2. 哈希表实现机制

Lua 使用全局哈希表（stringtable 结构）管理字符串池，关键设计如下：

(1) 数据结构

typedef struct stringtable {
  TString **hash;  // 哈希桶数组
  int size;        // 桶数量（2的幂次）
  int nuse;        // 已用桶数量
} stringtable;

• 哈希函数：对字符串内容计算哈希值，公式为：
  $$
  \text{hash} = \sum_{i=0}^{n-1} s[i] \times 31^{n-1-i} \mod \text{size}
  $$
  其中 $s$ 为字符串内容，$n$ 为长度。

(2) 冲突解决：开放定址法

• 采用线性探测（Linear Probing）处理冲突：
  • 若目标桶被占用，顺序检查下一个桶（index = (index + 1) % size）。
• 扩容机制：当负载因子 $\frac{\text{nuse}}{\text{size}} > 0.75$ 时，哈希表扩容至 $2 \times \text{size}$ 并重哈希所有元素。

---

3. 字符串复用逻辑

当创建新字符串（如 str = "hello"）时，Lua VM 执行以下流程：

1. 计算哈希值：对字符串内容进行哈希运算。
2. 查重检测：
   • 在哈希表中查找相同内容的字符串。
   • 若存在，直接返回已有字符串的引用（指针复用）。
3. 新建与注册：
   • 若未找到，分配新内存存储字符串。
   • 将其插入哈希表，并更新 nuse 计数。

graph TD
  A[创建新字符串] --> B{计算哈希值}
  B --> C[在哈希表中查找]
  C --> D{是否存在？}
  D -- 是 --> E[复用已有字符串]
  D -- 否 --> F[分配新内存]
  F --> G[插入哈希表]
  G --> H[返回新字符串]

---

4. 垃圾回收（GC）协同机制

• 引用标记：字符串作为 GC 对象，其生命周期由引用计数管理。
• 自动清理：当字符串不再被引用时，GC 将其从哈希表移除并释放内存。
• 关键优化：短字符串（如单字符）永久保留在池中，避免频繁创建/销毁。

---

5. 示例：复用现象验证

local s1 = "Lua"
local s2 = "Lua"
print(s1 == s2)         -- true（内容相同）
print(rawequal(s1, s2)) -- true（指针相同，复用发生）

local s3 = string.sub("LuaVM", 1, 3) -- 动态生成 "Lua"
print(rawequal(s1, s3))              -- true（复用成功）

---

总结

• 优势：哈希表实现 $O(1)$ 平均查找复杂度，内存节省显著（尤其重复字符串多的场景）。
• 注意事项：
  • 长字符串哈希计算可能成为性能瓶颈（需优化哈希函数）。
  • GC 压力增大时，字符串池扫描可能影响吞吐量。
    Lua 的字符串池机制是空间-时间权衡的经典实践，适用于嵌入式和高性能场景。