说起哈希表，hen多人第一反应是「键值对」和「O」的神奇速度。可当我们把视线投向实现细节时会发现背后隐藏着一套精妙的冲突处理“武器库”。本文不走套路，像在咖啡馆里闲聊一样，把四大主流开放寻址方案逐一拆开聊聊，顺带抛出几段代码片段、实测数据以及选型建议，帮助你在项目中Zuo出geng合适的决定。

Ru果把所有键直接映射到一个固定大小的数组里冲突几乎是必然的——鸽巢原理告诉我们：当键的数量超过数组槽位数时必定会有两个键落在同一个位置。传统的链式哈希会在每个槽位后面挂一条链表，而开放寻址则坚持“所有数据dou必须占据主数组”。当碰撞发生时它们不去找别处，而是沿着预先约定好的路径继续搜索下一个可用格子。

这种“全员搬家”式的思路让 CPU 缓存受益匪浅：连续存取意味着硬件预取器Ke以提前把后面的几个槽位拉进 L1，查找过程往往只要一次或两次缓存命中就Neng完成。

Zui直白、Zui常见的一种方式——遇到占用格子就往后挪一步，直到找到空位。其探测公式极其简洁：

// idx 为初始位置，i 为探测次数
size_t probe {
    return  % m;
}

优点：

实现代码几乎Ke以写成十行；

内存布局极度紧凑，对现代 CPU 的预取友好；

在负载因子低于 0.7 时平均探测次数只有 1~2 次。

痛点：

出现一次聚集——相邻位置形成长队，新元素hen容易被迫加入同一段，使得后续查找代价指数级增长；

删除操作需要标记为 “墓碑”，否则会导致查找提前终止，从而产生额外空间浪费。

小贴士：Ru果你的业务对查询延迟极为敏感，而且Ke以接受稍微高一点的负载因子，线性探测依然是首选。

为了解决一次聚集的问题，人们把步幅改成二次函数：

size_t probe {
    return  % m;   // c1、c2 为常数
}

这里每一步跳跃距离dou会越来越大，从而把冲突分散到geng宽广的区域。

优势：

聚集现象显著减弱；

仍保持较好的缓存局部性，因为跳转仍然在同一块连续内存里。

局限：

Ru果表容量不是素数或 2 的幂，可Neng出现循环不完整的问题，需要额外保证容量满足特定数学条件；

与线性探测相比，在极端负载情况下平均探测次数略高。

顾名思义，这种策略使用两套哈希函数。第一次得到基准槽位，第二次提供步长：

size_t probe {
    return  % m;   // h2 必须非零且与 m 互质
}

为什么要双重？

每个键dou有自己独立的跳跃序列，冲突概率进一步降低；

理论上Ke以Zuo到近似完美均匀分布，即使负载因子逼近 0.9 也不会出现明显退化。

实现难点：

需要精心挑选第二个哈希函数，以确保它与表大小互质，否则可Neng出现循环不覆盖全部槽位的问题；

计算成本比单函数略高，对性Neng要求极致的场景要权衡一下。

"抢劫者"名字听起来有点戏剧化，但核心思想其实非常温柔：让“贫穷”的元素抢走“富裕”元素的一次机会，从而整体上缩小查找路径差距。

// 插入时记录Yi有元素离理想位置的距离
void robin_insert {
    size_t pos = hash % m->cap;
    size_t dist = 0;
    while  {
        if  { … }
        if  {   // 抢劫！交换
            swap; swap;
        }
        pos =  % m->cap;
        ++dist;
    }
}

Loved by:

C++20 的 #include 在某些实现里采用了该策略；

Cassandra、Rust 的 AHashMap也借鉴了 Robin Hood 的思想。

The good side：

Ave‑search depth 与Zui大深度之间差距被压缩到几乎kan不见；

L‑probe 长度随负载因子上升仍保持平稳，大约在 4–5 步左右即止步。

Tombstone 不再是硬伤，因为被抢走的位置会被新元素填补。

The trade‑off：

P​robe‑len 必须随每个槽一起保存，会稍微增大结构体大小；

P​robe‑swap 操作导致写入频率提升，对写放大的 SSD 场景需谨慎评估。

"跳房子"式地把元素搬进离它Zui近且空闲的位置，同时维护一个 “邻域位图”，记录哪些近邻格子Yi经被占用。这让查找只需要检查至多 32/64 个相邻格子即可定位目标，大幅提升缓存命中率。

// 每个 bucket 保存 bitmap + 实际数据指针
typedef struct {
    uint32_t hopinfo;      // 位图
    uint64_t key;
    uint64_t value;
} HBucket;

Smooth scaling： 当装填率逼近 90% 时只需要轻微迁移几个相邻 bucket 即可完成插入，不必像线性/二次探测那样遍历整张表；

Clever locality： 因为所有候选位置dou在同一个 cache line 范围内，所以 L1 命中率常常超过 95%。

Slight overhead： 每个 bucket 多出一个 bitmap，占用额外几字节，但相对于整体内存而言可忽略不计。