哈希表——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 序列到函数调用的映射。

相关概念

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

详见 Part 2 — BPE 分词器。