哈希表——O(1) 平均查找的数据结构。ds4.c 使用开放寻址哈希表实现 BPE 分词查找和 DSML replay map。

为什么需要哈希表

BPE 分词时需要在 129280 个 token 的词表中快速查找子串。线性搜索太慢（O(n)），二分搜索需要排序（O(log n)）。哈希表提供 O(1) 平均查找。

核心原理

开放寻址法（Open Addressing）:
  hash(key) → slot
  如果 slot 被占用且 key 不同 → 线性探测下一个 slot
  直到找到空 slot（插入）或匹配 key（查找）

vs. 链式哈希（Chaining）:
  每个 slot 是一个链表，冲突时追加到链表
  开放寻址缓存更友好（连续内存），适合 C 实现

在 ds4.c 中的实现

BPE 分词器中的哈希表（ds4.c）用于 token 词表查找：

• 开放寻址 + 线性探测
• 固定大小（词表大小 × 负载因子）
• 初始化时插入所有 token，之后只做查找

DSML replay map 使用 rax.c（Redis 的 radix tree 实现），不是哈希表，但用途类似——快速查找 token 序列到函数调用的映射。

实战用例：Metal 张量活跃集合（含墓碑）

ds4_metal.m 维护了一张活跃 Metal 张量句柄集合，是开放寻址 + 墓碑的教科书级实战：每个 ds4_gpu_tensor 句柄是一个 retained Objective-C 对象，alloc/view 时插入集合，free 时先查集合——不在集合里说明是双重释放，直接拒绝（否则会把已释放对象再交给 ARC，触发 malloc corruption）。因为句柄会频繁删除，删除时写**墓碑（UINTPTR_MAX）**而非清零，避免断开后续探测链；负载因子到 70% 时翻倍 rehash 顺带回收墓碑。详见 Part 6 §张量句柄的双重释放守卫。

相关概念

• bpe — BPE 分词依赖哈希表在词表中快速查找合并规则
• moe — 前 3 层的 hash 路由使用简单的 ID 查找表

详见 Part 2 — BPE 分词器。