Robin Hood Hashing 是什么？为什么说它能缩短最坏探测距离？
简化版
Robin Hood Hashing 是开放寻址的一种策略：插入时比较元素离理想桶的距离，距离更远的元素可以“抢占”距离更近的元素位置。它试图让探测距离更均匀，减少极端长探测链。
详细版
普通线性探测中，后来者遇到占用槽位就继续往后找。Robin Hood 的想法是“劫富济贫”：如果新元素已经探测了很远，而当前位置的旧元素离自己的理想位置更近，就交换两者，让更“可怜”的元素靠前。
关键概念：
- 理想位置：
hash(key) % capacity。 - 探测距离：当前位置距离理想位置的偏移。
- 插入时比较新旧元素探测距离。
- 新元素距离更大时，和旧元素交换，旧元素继续向后找位置。
- 查找可以利用探测距离提前停止。
它不消除冲突，而是让冲突代价更均匀。
完整版教学
一、普通线性探测的问题在哪里
线性探测简单：冲突了就往后找空位。但随着负载上升，连续占用区间会变长，某些 key 的探测距离会很大。
理想桶：3
实际位置：9
探测距离：6平均表现可能还行，但最倒霉的 key 查找很慢。Robin Hood Hashing 就是想降低这种“不公平”的探测距离差异。
二、Robin Hood 的名字怎么理解
Robin Hood 的规则像“劫富济贫”。这里的“穷”是探测距离远，说明这个元素已经被冲突挤得很惨；“富”是探测距离近，说明它离理想位置很近。
插入时，如果新元素探测距离大于当前位置旧元素的探测距离，就交换：
新元素距离 4，旧元素距离 1
新元素抢当前位置
旧元素继续向后寻找这样做会让探测距离分布更均匀，减少有人特别远、有人特别近的极端状态。
三、插入过程如何执行
插入时维护当前元素和它的探测距离。
while slot occupied:
if dist(newKey) > dist(slotKey):
swap(newKey, slotKey)
move to next slot
dist++
place newKey into empty slot数字例子：容量 10，新 key 理想位置 2，探测到位置 5，距离是 3。位置 5 的旧 key 理想位置 4，距离是 1。新 key 更远，于是交换，新 key 放在 5，旧 key 从 6 继续找。
四、查找为什么可以提前停止
Robin Hood 的一个好处是可以利用探测距离判断“不可能再找到”。查找某个 key 时，如果当前查找距离已经大于槽内元素的探测距离，说明目标如果存在，早就应该把这个槽抢走了。
查找距离 = 5
槽内元素距离 = 2
目标不存在，可以停止这个性质来自插入时的交换规则。它不是普通线性探测天然具备的，需要 Robin Hood 的距离有序倾向支持。
五、和普通线性探测对比
| 维度 | 普通线性探测 | Robin Hood Hashing |
|---|---|---|
| 插入逻辑 | 找到空位就放 | 可能多次交换 |
| 探测距离 | 可能分布不均 | 更趋于均匀 |
| 查找失败 | 到空槽停止 | 可用距离提前停止 |
| 实现复杂度 | 低 | 较高 |
Robin Hood 的目标不是让所有操作都神奇变成更低复杂度，而是改善高负载下的探测距离分布和尾部延迟。
六、删除为什么也要小心
开放寻址删除本来就麻烦。Robin Hood 可以使用墓碑，也可以使用 backward shift deletion，把后续元素往前搬，维持探测距离性质。
记忆钩子：Robin Hood Hashing 看的是“离家多远”；谁离理想桶更远，谁优先占更靠前的位置。
七、常见误区与追问
- 误区：Robin Hood Hashing 能避免哈希冲突。 它不能避免冲突，只是重新分配冲突带来的探测距离。
- 误区：它一定比所有哈希表都快。 它改善探测距离分布，但插入和删除实现更复杂。
- 误区：探测距离只是调试信息。 探测距离是插入交换和查找提前停止的核心依据。
- 追问：和墓碑删除能一起用吗？ 可以，但墓碑太多仍会影响性能；也可用后移删除维护性质。
- 追问：为什么叫 Robin Hood？ 因为让探测距离远的“穷元素”抢占距离近的“富元素”位置。
八、加强记忆
Robin Hood Hashing 的核心是公平化探测距离。普通线性探测是先来先占，Robin Hood 会比较“离家距离”，远的优先。它换来更均匀的查找成本，代价是插入删除逻辑更复杂。