C++ 浅谈Robin Hood Hash 算法
介绍
“Robin Hood” 在传说中是个 劫富济贫 的英雄，这个策略就像 Robin Hood 一样：
- 探测距离远的元素 = 穷人
- 探测距离短的元素 = 富人
- 插入时发现某位置被占：
- 如果新元素比桶里元素 更穷（探测距离更远），就 抢占 位置，把老元素 往后挤。
这个策略使得：
- 贫富差距变小（探测距离差距减小）
- 查找操作平均探测次数变少
- 最坏情况比普通线性探测更好
核心概念
| 名词 | 含义 |
|---|---|
| 哈希值（Hash） | 元素计算出的理想插入位置 |
| 探测距离（Probe Distance） | 当前桶位置与理想桶位置的距离（从 hash%N 开始向后线性探测） |
| 抢占（Stealing） | 新元素 probe_distance > 当前桶元素的 probe_distance → 抢占位置，并将老元素向后移 |
和普通线性探测相比的优势
1、减小尾部探测长度
- 普通线性探测会随着负载因子增加，形成“初级聚集”（primary clustering），导致一些槽位后面链长急剧增长。
- Robin Hood 则通过“抢劫长探测距离者”的策略，把那些探测距离非常大的元素往前挪，避免“极端长链”形成，从而降低最大探测步数。
2、更均匀的探测分布
- 普通线性探测下，早期插入且发生冲突的元素会一直停留在簇的前端，后续插入的元素全部堆积在其后，导致簇不断加长。
- Robin Hood 会让探测距离大的（通常是后插入或哈希分布差异较大的）元素“往前”，探测距离小的“往后”，链长分布更平滑，平均和 95%、99% 百分位查找代价降低。
3、更稳定的查找延迟
- 在实时或延迟敏感场景下，普通线性探测的最坏情况探测步数会随着负载大幅抖动。
- Robin Hood 保证大部分操作在一个可控范围内完成，抖动更小。
举例说明
下面用更加直观的 Emoji 阵列，分别展示 普通线性探测（🔵）和 Robin Hood 探测（🟠）在容量为 7（索引 0…6）时，依次插入 10, 17, 24, 3, 0, 5, 7 的全过程。
- 空槽：▫️
- 普通线性探测：🔵
- Robin Hood 探测：🟠
索引: 0 1 2 3 4 5 6
初始状态（Step 0）
线性: ▫️ ▫️ ▫️ ▫️ ▫️ ▫️ ▫️
RH : ▫️ ▫️ ▫️ ▫️ ▫️ ▫️ ▫️
Step 1. 插入 10 (h=3)
线性: ▫️ ▫️ ▫️ 🔵10(0) ▫️ ▫️ ▫️
RH : ▫️ ▫️ ▫️ 🟠10(0) ▫️ ▫️ ▫️
Step 2. 插入 17 (h=3)
线性: ▫️ ▫️ ▫️ 🔵10(0) 🔵17(1) ▫️ ▫️
RH : ▫️ ▫️ ▫️ 🟠10(0) 🟠17(1) ▫️ ▫️
Step 3：插入 24 (h=3)
线性: ▫️ ▫️ ▫️ 🔵10(0) 🔵17(1) 🔵24(2) ▫️
RH : ▫️ ▫️ ▫️ 🟠10(0) 🟠17(1) 🟠24(2) ▫️
Step 4：插入 3 (h=3)
线性: ▫️ ▫️ ▫️ 🔵10(0) 🔵17(1) 🔵24(2) 🔵3(3)
RH : ▫️ ▫️ ▫️ 🟠10(0) 🟠17(1) 🟠24(2) 🟠3(3)
Step 5：插入 0 (h=0)
线性: 🔵0(0) ▫️ ▫️ 🔵10(0) 🔵17(1) 🔵24(2) 🔵3(3)
RH : 🟠0(0) ▫️ ▫️ 🟠10(0) 🟠17(1) 🟠24(2) 🟠3(3)
Step 6：插入 5 (h=5)
| 算法 | 过程 | 结果 |
|---|---|---|
| 线性探测 | 5→槽5(24)→槽6(3)→槽0(0)→槽1(▫️) → 放🔵5 → dist=(1−5 mod7)=3 | 🔵0(0) 🔵5(3) ▫️ 🔵10(0) 🔵17(1) 🔵24(2) 🔵3(3) |
| Robin Hood | 5→槽5(24,2)，0<2→槽6；槽6(3,3)，1<3→槽0；槽0(0,0)，2>0 → 交换（槽0放🟠5(2)，踢出🟠0重插到槽1→dist=1） | 🟠5(2) 🟠0(1) ▫️ 🟠10(0) 🟠17(1) 🟠24(2) 🟠3(3) |
线性: 🔵0(0) 🔵5(3) ▫️ 🔵10(0) 🔵17(1) 🔵24(2) 🔵3(3)
RH : 🟠5(2) 🟠0(1) ▫️ 🟠10(0) 🟠17(1) 🟠24(2) 🟠3(3)
Step 7：插入 7 (h=0)
| 算法 | 过程 | 结果 |
|---|---|---|
| 线性探测 | 7→槽0(0)→槽1(5)→槽2(▫️) → 放🔵7 → dist=(2−0)=2 | 🔵0(0) 🔵5(3) 🔵7(2) 🔵10(0) 🔵17(1) 🔵24(2) 🔵3(3) |
| Robin Hood | 7→槽0(5,0)→槽1(0,1)→槽2(▫️) → 放🟠7 → dist=2 | 🟠5(2) 🟠0(1) 🟠7(2) 🟠10(0) 🟠17(1) 🟠24(2) 🟠3(3) |
线性: 🔵0(0) 🔵5(3) 🔵7(2) 🔵10(0) 🔵17(1) 🔵24(2) 🔵3(3)
RH : 🟠5(2) 🟠0(1) 🟠7(2) 🟠10(0) 🟠17(1) 🟠24(2) 🟠3(3)
Step 8: 查找不存在的值31
- 线性查找：只要没找到 key，就一直往后找，直到遇到空槽或者 key。
- Robin Hood 探测：查找元素的探测距离 > 当前槽原有元素的探测距离 → 查找失败！
线性查找：查找31的时候，线性查找的探测距离是7，槽的最大值
Robin Hood 探测：查找到槽0的时候,31的探测距离为4 > 槽0中值5的探测距离2, 则停止探测。所以最终探测距离为4
总结
Robin Hood 探测通过“让探测距离大的元素优先占位”的方式，有效抑制了哈希表中因聚集造成的长尾探测链，提升了在高负载场景下的平均与最坏查找性能。