第 20 章：哈希表（Hash Tables）
原文：Robert Nystrom, Crafting Interpreters, Chapter 20。原书以 CC BY-NC-SA 4.0 协议发布；本译文用于学习与研究。
Hash，名词：这个词没有定义，因为没有人知道 hash 是什么。
Ambrose Bierce，《The Unabridged Devil's Dictionary》
给变量名查值、给实例保存字段、后续按名字查找方法，都需要同一种数据结构：哈希表。Java 称它为 HashMap，C# 与 Python 常称 dictionary，C++ 称 unordered map；JavaScript 的 object 和 Lua 的 table 在底层也都是哈希表。
哈希表将键（key）关联到值（value），每对键值构成 entry。给定键可查询、插入、删除；对已有键插入新值则覆盖旧值。它强大的原因是：在平均情形下，查找时间为常数，和表中键数量无关。最坏情形当然会更差，但实践中可通过合适设计避免退化。
20.1 桶数组（An Array of Buckets）
先设想极端受限的变量名：只能是一个小写字母。只需 26 个元素的数组，每个元素称为桶（bucket），a 对应索引零；字符减去 'a' 即可直接访问存储位置。它紧凑、简单、极快：没有链表指针、节点填充等额外开销。
真实变量名当然不止一个字母。若放宽为最多 8 个字符，可将其打包进 64 位整数；但若直接把这个数作为数组索引，就需要约 295,148 PB 的数组。即便能分配也会极端浪费，因为大多数桶为空。
解决办法是分配适度大小的数组，然后用键数值对数组大小取模，将大范围“折叠”到桶索引。例如 bagel 在小端机器上打包为 64 位字后，对大小 8 取模可得桶 2。容量常取 2 的幂，但也有实现偏好质数或其他规则。
20.1.1 加载因子与回绕键（Load factor and wrapped keys）
取模节省空间，却引入碰撞：不同键可能有相同余数。bagel 与 jam 都可能落在桶 2：
桶越多，碰撞越少但内存越多。加载因子等于 entry 数除以桶数；16 个桶有 5 条 entry 时是 0.3125。加载因子越高，碰撞概率越大。哈希表会在超过预设加载因子前扩容，而不是等数组填满。
20.2 碰撞解决（Collision Resolution）
低加载因子只能让碰撞更少，无法消灭它。生日悖论说明键数增加时碰撞概率上升很快；抽屉原理说明键空间远大于合理桶数时，必有多个键进入同一桶。五只宠物鸟配四个洞，至少一个洞会住两只：
20.2.1 分离链接法（Separate chaining）
第一类方案是分离链接法：每个桶不是一个 entry，而是 entry 集合，经典实现为链表。查找先定位桶，再遍历链表：
最坏时所有 entry 在同一桶，退化为 O(n) 无序链表；但好的哈希、低加载因子通常令每桶只有一两个节点。它概念简单，删除也直观，却不利于现代 CPU：指针开销大，微小节点散落在内存中，缓存局部性差。可把首 entry 内联到桶或每节点存多个 entry 缓解。
20.2.2 开放寻址（Open addressing）
本书选择开放寻址（也被混乱地称为 closed hashing）：所有 entry 直接位于同一个桶数组，每桶一个 entry；目标桶被占时，找另一个空桶。它的“开放”指 entry 可放在偏好的地址之外，“闭合”则指所有 entry 仍在桶数组内。
寻找可用桶称为探测（probing），检查桶的顺序称探测序列。存在 double hashing、cuckoo hashing、Robin Hood hashing 等丰富策略；clox 采用最简单的线性探测：目标桶、下一个桶、再下一个，越过末尾即回到开头。
线性探测沿内存顺序走，对缓存友好；缺点是容易聚集，数值接近的键可能形成连续拥挤区。可把它理解成：分离链接法的链不再由指针连接，而是隐含于桶数组的检查顺序，且多条隐式链可能彼此交错。
以下插入过程展示全部重要情况：
不同探测序列交错并不构成问题：每次都要比较当前桶的键，既能识别同一键，也自然跳过属于其他序列的 entry。
20.3 哈希函数（Hash Functions）
要允许任意长度字符串做键，需将任意大小数据映射为固定大小整数，即哈希函数。好的哈希函数有三项要求：
- 确定性：同一输入始终得到同一哈希码，否则键会跑到不同桶。
- 均匀性：典型输入应广泛且均匀分散，减少碰撞和聚集。
- 快速：每个表操作都要哈希键，慢哈希会抵消数组查找优势。
哈希表曾叫 scatter table，正因其将 entry 散布于数组中。加密哈希要求更严，本书不需要抵抗攻击者。clox 选择历经验证、实现简单的 FNV-1a：
static uint32_t hashString(const char* key, int length) {
uint32_t hash = 2166136261u;
for (int i = 0; i < length; i++) {
hash ^= (uint8_t)key[i];
hash *= 16777619;
}
return hash;
}
实际系统可针对硬件、数据集、吞吐或安全性选择其他哈希函数；值得用真实工作负载比较。
20.4 构建哈希表（Building a Hash Table）
数据结构本身很简单。键在 clox 中始终是字符串，直接保存 ObjString* 比包装为 Value 更小、更快：
// table.h
typedef struct {
ObjString* key;
Value value;
} Entry;
typedef struct {
int count;
int capacity;
Entry* entries;
} Table;
count / capacity 即加载因子。初始化与释放与动态数组类似：
void initTable(Table* table) {
table->count = 0;
table->capacity = 0;
table->entries = NULL;
}
void freeTable(Table* table) {
FREE_ARRAY(Entry, table->entries, table->capacity);
initTable(table);
}
20.4.1 哈希字符串（Hashing strings）
频繁为同一字符串重算哈希需要重复扫描所有字符，因此在 ObjString 中缓存 uint32_t hash：
struct ObjString {
Obj obj;
int length;
char* chars;
uint32_t hash;
};
copyString() 与 takeString() 在构造前调用 hashString(chars, length)，再将 hash 传给 allocateString()。这样后续表操作只读取缓存整数。
20.4.2 插入 entry（Inserting entries）
表最大加载因子取 75%：
#define TABLE_MAX_LOAD 0.75
bool tableSet(Table* table, ObjString* key, Value value) {
if (table->count + 1 > table->capacity * TABLE_MAX_LOAD) {
int capacity = GROW_CAPACITY(table->capacity);
adjustCapacity(table, capacity);
}
Entry* entry = findEntry(table->entries, table->capacity, key);
bool isNewKey = entry->key == NULL;
if (isNewKey && IS_NIL(entry->value)) table->count++;
entry->key = key;
entry->value = value;
return isNewKey;
}
核心 findEntry() 用哈希码定位初始桶、线性探测。真正空桶（key == NULL 且 value == nil）表示键不存在并可插入；相同指针表示已找到已有键：
static Entry* findEntry(Entry* entries, int capacity,
ObjString* key) {
uint32_t index = key->hash % capacity;
Entry* tombstone = NULL;
for (;;) {
Entry* entry = &entries[index];
if (entry->key == NULL) {
if (IS_NIL(entry->value)) {
return tombstone != NULL ? tombstone : entry;
}
if (tombstone == NULL) tombstone = entry;
} else if (entry->key == key) {
return entry;
}
index = (index + 1) % capacity;
}
}
加载因子保证总有真正空桶，因此循环会终止。这里按指针比较字符串暂时看似不正确；第 20.5 节的驻留将保证同文本只有一个对象，令其成立。
20.4.3 分配和扩容（Allocating and resizing）
首次插入需要桶数组，扩容也需要新数组。空 bucket 用 NULL 键和 NIL_VAL 值表示：
static void adjustCapacity(Table* table, int capacity) {
Entry* entries = ALLOCATE(Entry, capacity);
for (int i = 0; i < capacity; i++) {
entries[i].key = NULL;
entries[i].value = NIL_VAL;
}
table->count = 0;
for (int i = 0; i < table->capacity; i++) {
Entry* entry = &table->entries[i];
if (entry->key == NULL) continue;
Entry* dest = findEntry(entries, capacity, entry->key);
dest->key = entry->key;
dest->value = entry->value;
table->count++;
}
FREE_ARRAY(Entry, table->entries, table->capacity);
table->entries = entries;
table->capacity = capacity;
}
不能像普通动态数组一样直接 realloc()：桶位置取决于 hash % capacity，容量变化后每个键可能到不同桶，也会产生不同碰撞。因此必须把每个活 entry 重新插入新数组。tableAddAll() 以 tableSet() 将一个表的每个非空 entry 加入另一个表，后续继承功能会使用它。
20.4.4 取回值（Retrieving values）
查找重用 findEntry()：
bool tableGet(Table* table, ObjString* key, Value* value) {
if (table->count == 0) return false;
Entry* entry = findEntry(table->entries, table->capacity, key);
if (entry->key == NULL) return false;
*value = entry->value;
return true;
}
空表判断不仅是优化，也避免访问 NULL 的桶数组。输出参数承接找到的值。
20.4.5 删除 entry（Deleting entries）
开放寻址的删除最微妙。若同一首选桶的 bagel、biscuit、jam 连续存放：
直接清空中间 biscuit 会让查找 jam 在遇到空槽时错误停止：
使用墓碑（tombstone）替代。墓碑不是查找终止点，但可被未来插入复用：
bool tableDelete(Table* table, ObjString* key) {
if (table->count == 0) return false;
Entry* entry = findEntry(table->entries, table->capacity, key);
if (entry->key == NULL) return false;
entry->key = NULL;
entry->value = BOOL_VAL(true);
return true;
}
NULL 键、非 nil 值代表墓碑；任何不能与空槽和有效 entry 混淆的标记都可用：
findEntry() 记住遇到的第一个墓碑，但持续探测以确认后方没有同键；若最终找到真正空槽，则返回最早墓碑供插入复用。这个行为已包含在前述函数中。
20.4.6 统计墓碑（Counting tombstones）
对加载因子必须把墓碑视为已占用。若当作空槽，反复删除可令数组没有真正空桶，findEntry() 无限循环；若当作占用，只会略早扩容，代价远小于不终止。故删除时不减 count；tableSet() 只在写入真正空槽时增加 count。
扩容重建时不复制墓碑，因探测序列重新生成后它们没有价值。adjustCapacity() 将 count 清零，然后每迁移一个活 entry 加一，这也清除了累积墓碑。墓碑让删除非常快、查找稍慢，是一种惰性删除：代价按后续操作分摊。实测通常比删除时立即回填并重插受影响条目更快。
20.5 字符串驻留（String Interning）
普通 findEntry() 用 == 比较键指针，两个内容相同但不同地址的字符串会失败。可先比 hash、再比字符，但每次查表都可能扫描字符串。字符串驻留（interning）通过去重解决：运行时维护一组互不重复文本的字符串；请求驻留时找到已有者就复用，否则加入。Lua 对全部字符串这样做；Lisp、Scheme、Smalltalk、Ruby 的 symbol 相当于自动驻留；Java 默认驻留常量字符串，也可显式驻留。
一旦全部字符串驻留，指针相同等价于内容相同，指针不同也必然文本不同。因此 findEntry() 的指针比较正确，字符串相等也可降为指针比较。VM 保存一个 string set：
// vm.h
typedef struct {
// ...
Table strings;
Obj* objects;
} VM;
初始化、关闭时管理该表：
void initVM() {
resetStack();
vm.objects = NULL;
initTable(&vm.strings);
}
void freeVM() {
freeTable(&vm.strings);
freeObjects();
}
allocateString() 将新唯一字符串作为 key 插入表，value 仅为 nil，故此处表实际当 set 使用：
tableSet(&vm.strings, string, NIL_VAL);
创建字符串前先按原始字符查驻留表：
uint32_t hash = hashString(chars, length);
ObjString* interned = tableFindString(&vm.strings, chars, length, hash);
if (interned != NULL) return interned;
copyString() 未命中才复制、分配和插入。takeString() 未命中时接管数组；命中时要释放传入的重复字符数组，因为所有权已交给它：
if (interned != NULL) {
FREE_ARRAY(char, chars, length + 1);
return interned;
}
tableFindString() 不能调用 tableGet()，因为此时还没有 ObjString，且正要解决内容相同、指针不同的问题：
ObjString* tableFindString(Table* table, const char* chars,
int length, uint32_t hash) {
if (table->count == 0) return NULL;
uint32_t index = hash % table->capacity;
for (;;) {
Entry* entry = &table->entries[index];
if (entry->key == NULL) {
if (IS_NIL(entry->value)) return NULL;
} else if (entry->key->length == length &&
entry->key->hash == hash &&
memcmp(entry->key->chars, chars, length) == 0) {
return entry->key;
}
index = (index + 1) % table->capacity;
}
}
先比长度和哈希，只有两者相同才逐字节比对；这是 VM 唯一真正检查字符串文本相等的地方。完成去重后，值相等可简化为：
case VAL_OBJ: return AS_OBJ(a) == AS_OBJ(b);
创建字符串略有额外开销，换来运行时快速字符串相等、全局变量查找、字段和方法名查找。对象模型中若名称比较慢，几乎所有操作都会慢；驻留是动态语言中的关键基础优化。
挑战（Challenges）
clox的哈希表只支持字符串键。加入数字、布尔值、nil等原始键；若后来支持用户实例作为键，会增加哪些相等性与可变性复杂度？- 哈希表有许多可调参数：分离链接或开放寻址、每节点 entry 数、探测策略、哈希函数、加载因子、增长率。研究不同开源系统的实现选择，并推断它们适配的域与硬件条件。
- 为本表编写多种基准。哈希表会因键集、规模、删除频率表现不同；哪些测试最能代表你的用户，性能为何会变化？