题目重点：从碰撞、删除、扩容和负载因子解释两个方案，并用线性探查墓碑反例检查正确性。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练讨论的基本接口是 put(key,value)、get(key)、delete(key)，key 提供一致的 hash 与 equality，更新已有 key 不增加 size。
- 容量有限、可动态扩容；以下线性探查和链式桶均为可讲的实现选择，不冒充题目指定算法。
- 平均 O(1) 需要哈希分布和负载因子控制；恶意碰撞时可能退化 O(n)，线程安全不是天然具备的。
解题路线
- 拉链法：数组桶，按 hash(key) 定位，每桶存若干键值对；查找和更新在该桶内做 equality，删除直接移除节点或数组项。平均桶长取决于 n/capacity，链表分配与指针局部性是代价。
- 开放寻址：键值对存在主数组内，冲突时按探查序列找下一槽。线性探查缓存局部性较好，但容易聚簇；删除不能简单清空，需 tombstone 或后移修复。
- 超过约定负载阈值时扩容并把活跃条目重新 hash 到新表；墓碑过多即使 size 不大也可重建。阈值 0.5/0.75 只是训练示例，取决于探查策略和延迟目标。
- 把 key 相等、hash 碰撞、覆盖写、删除后继续探查、扩容期间失败恢复和迭代器失效作为 API 测试；如果是 Swift，还要说明值语义、引用与自定义 Hashable 的影响。
手动走一遍
容量 4、h(k)=k mod 4，依次插入 1、5、9。线性探查可在槽 1、2、3 存放。删掉 5 后若直接清空槽 2，搜索 9 会在空槽提前终止并错误返回缺失；标墓碑才会继续查到槽 3。拉链法则三项同在桶 1，删除 5 不影响查 9。
规模与取舍
两种方案平均 put/get/delete O(1)，扩容单次 O(n) 但按几何倍增摊还可 O(1)；最坏碰撞 O(n)。空间 O(n+capacity)，开放寻址通常需要控制更低负载率，链式桶另有节点/引用开销。
易错点与追问
容易失分的边界
- 把 hash 值相同当 key 相等，不做 equality 检查。
- 线性探查删除直接设为空，截断后续碰撞链。
- resize 只复制旧槽位置而不重新哈希。
- 忽略墓碑积累使探查越来越长。
- 无条件声称哈希表每个操作严格 O(1)。
继续深挖
- 若 key 是可变对象，hash 改变后会发生什么？
- Robin Hood hashing 怎样减少长尾探查？
- 高并发读写时锁分片、复制更新、无锁方案如何权衡？
- 若需要稳定迭代顺序，哈希表本身要增加哪些结构？
