散列（哈希）是每个写 C++ 的人迟早都要正面刚的内容。平时用std::unordered_map挺顺手，可一旦面试或者性能调优问到“它内部怎么解决冲突”，很多人就卡住了。开放定址法（Open Addressing）正是解决哈希冲突的两大流派之一，和拉链法不一样，它不挂链表，所有元素都住在同一个数组里，冲突了就顺着探测序列找下一个空位。这篇我用一个完整可编译的 C++ 实现，把开放定址的三种探测方式、槽位状态设计、扩容再散列、负载因子调优，以及我在实际调试中踩过的几个隐蔽的坑，一次讲透。适合刚学完 C++ 基础、想把手写哈希表弄明白的人，也适合想跟unordered_map内部实现做对比的老手——别看拉链法用得广，开放定址在很多高性能场景才是主角。

1. 从冲突谈起：开放定址法到底解决什么问题

1.1 哈希表的基本模型：数组加哈希函数

哈希表的核心其实一句话就能说清：把 key 通过哈希函数换算成一个数组下标，然后直接在下标位置存 value。数组的随机访问是 O(1)，所以理论上一次查找、插入、删除都应该是 O(1)。这个模型比树形结构好理解，也比树更适合“键值对”这种访问模式。

问题出在“换算成下标”这一步。哈希函数把无限大的 key 空间映射到有限的数组长度上，哪怕哈希函数设计得再均匀，也一定存在两个不同的 key 算出同一个下标的情况，这就是哈希冲突。别觉得这事罕见，抽屉原理加上“生日悖论”告诉我们，往 365 个格子里放 23 个人就有一半概率撞一起；往容量的哈希表里塞元素，冲突是迟早的事。所以所有哈希表实现的核心工作，其实就是一件事：冲突了怎么办。

我习惯拿停车位来打比方。哈希函数相当于告诉你应该停在几号车位；车位被占了，你就得往前开，找下一个空位；等你要走的时候，又得从你记忆中那个车位开始找自己的车。开放定址法的思路和找车位一模一样。

1.2 拉链法 vs 开放定址法：两条路线的取舍

处理冲突的世界里基本上就两大门派。拉链法（也叫链地址法）是每个桶挂一条链表，冲突的 key 往链表后面挂；std::unordered_map默认走的就是这条路。开放定址法则是所有元素共用一个数组，冲突了就用一套探测规则去找另一个空槽。

为什么要关心开放定址？首先，连续数组意味着缓存友好。哈希表的数据量一大，缓存命中率对性能的影响远超你想象，拉链法那种“查个 key 要跳好几个链表节点”的访问模式，在数据量百万级的时候和开放定址差距就出来了。其次，不少语言和框架在底层实现里都倾向开放定址，你在面试的时候能把它讲清楚，和只会用unordered_map完全是两个层次的认知。

但开放定址也不是没有代价。它最烦人的地方是删除：怎么删、删完怎么保证后续查找还能找到其他元素，这里全是细节。后面我会专门用一整节来拆。

2. 三种探测方式：公式、代码与踩坑点

探测序列是开放定址的灵魂。冲突发生后按什么顺序去访问后续槽位，直接决定存取效率和能不能遍历到所有槽。三种经典方案：线性探测、二次探测、双重散列。

2.1 线性探测：最简单也最容易聚集

公式就一行：

index = (hash(key) + i) % table_size, i = 0, 1, 2, ...

冲突了就往下一个槽挪，一个接一个，直到找到空位。这是最直白的思路，代码写起来几乎没有心智负担，而且因为探测的是连续位置，缓存局部性最好。但它有个臭名昭著的毛病叫主聚集（primary clustering）：一旦几个元素扎堆形成一个连续块，后续哈希到这一带的元素都会被推到这个块的末尾，块越滚越大，最远的查找探测次数会越来越多。

你可以想象一条街上连续停了一排车，后来的车只能在队尾找位置，找车的时候也得从街口一路走过来。车越多，这条“车龙”越长。主聚集让线性探测在负载因子升高后性能急剧恶化，所以用线性探测必须严格控制负载因子。

说句实在话，我实际写代码时仍然经常选线性探测，理由很简单：在负载因子控制在 0.7 以内的前提下，它实现最简单、缓存最友好，性能在三种方案里往往反而是最好的。只有在删除频繁的场景，线性探测的墓碑问题才会让人头疼。

2.2 二次探测：从聚集里跳出来，但别忽略表长

公式变成了：

index = (hash(key) + i^2) % table_size, i = 0, 1, 2, ...

第一次冲突往后跳 1 格，第二次跳 4 格，第三次跳 9 格。因为跳跃的步长在变大，所以不容易形成线性探测那种连续大块，主聚集被明显缓解了，剩下的是次聚集（secondary clustering）：相同哈希前缀的 key 还是会走同一条探测路线，只是没连成片而已。

二次探测有个初学者特别容易踩的坑：表长不能是 2 的幂。i^2对 2 的幂取模会快速循环，比如表长 16 时，i^2 mod 16只会得到 0、1、4、9 四个值，你最多只能探测到 4 个位置，表明明没满，插入却可能失败。教科书上给的安全用法是：表长取素数，并且保证负载因子不超过 0.5，这样前大约一半的探测位置都是互不相同的，一定能找到空位。

2.3 双重散列：用第二个哈希函数打乱节奏

双重散列的设计思路和前面完全不同：它用两个哈希函数生成探测序列。

index = (hash1(key) + i * hash2(key)) % table_size

hash1决定起点，hash2决定每一步的“步长”。因为步长本身依赖 key，即使两个 key 的hash1相同，只要hash2不同，探测路线也不同，这是三种方案里唯一能真正打散聚集的方案。

但这里有个数学前提：hash2(key)必须和表长互质，否则探测序列走不完整个表，会提前循环。两种常见做法：

• 表长取素数：任何hash2(key)在 1 到table_size - 1之间都和表长互质。
• 表长取 2 的幂：必须保证hash2(key)总是奇数。

工程上有一个常用技巧，hash2可以这么写：

size_t hash2(const K& key) const { return 1 + (hash_(key) % (table_size() - 1)); }

前提是表长得是素数。双重散列的代价是每次探测要做两次哈希计算，计算开销略高，但换来的是更均匀的分布和更少的聚集。

3. C++ 手写开放定址哈希表：完整实现

3.1 槽位设计：为什么非要三种状态

数组里每个槽不只是存 key 和 value，还得记录状态。这是开放定址最容易忽略的部分。我最早写实现时只设计了两个状态：空和占用，结果一删除就出 bug。后来才明白，必须有三种状态：

enum class SlotState : std::uint8_t { EMPTY, DELETED, OCCUPIED };

拉链法删除可以直接摘节点，开放定址不行。删除一个槽如果直接把它置为 EMPTY，会把后面元素的探测链“拦腰截断”，查找就会误报“元素不存在”。所以删除的槽要标记为 DELETED，它占着位置、保留探测链的连续性，但同时允许后续插入重新使用它。DELETED 在业界有个形象的名字：墓碑（tombstone）。

槽位结构我这样定义：

struct Slot { K key{}; V value{}; SlotState state = SlotState::EMPTY; };

用std::uint8_t存状态而不是bool，是为了槽的内存更紧凑；真实项目里还要考虑 K/V 的移动语义，这里先保证清晰。整个表用一个std::vector<Slot>承载，天然连续内存，扩容时也省心。

3.2 三个核心方法：插入、查找、删除

下面是完整可编译的核心实现，采用线性探测，表长始终是 2 的幂，用位运算& (size - 1)替代取模提速。需要 C++17 以上的std::optional。

#include <cstdint> #include <functional> #include <optional> #include <vector> template <typename K, typename V, typename Hash = std::hash<K>> class OpenAddressingTable { enum class SlotState : std::uint8_t { EMPTY, DELETED, OCCUPIED }; struct Slot { K key{}; V value{}; SlotState state = SlotState::EMPTY; }; public: explicit OpenAddressingTable(size_t init_capacity = 16, double max_load_factor = 0.7) : table_(init_capacity), used_(0), deleted_(0), max_load_factor_(max_load_factor) {} bool insert(const K& key, const V& value) { grow_if_needed(); const size_t mask = table_.size() - 1; const size_t h = hash_(key) & mask; size_t first_deleted = table_.size(); // 哨兵值：还没遇到过墓碑 for (size_t i = 0; i < table_.size(); ++i) { const size_t idx = (h + i) & mask; if (table_[idx].state == SlotState::EMPTY) { const size_t target = (first_deleted != table_.size()) ? first_deleted : idx; if (table_[target].state == SlotState::DELETED) --deleted_; table_[target].key = key; table_[target].value = value; table_[target].state = SlotState::OCCUPIED; ++used_; return true; } if (table_[idx].state == SlotState::DELETED) { if (first_deleted == table_.size()) first_deleted = idx; continue; } if (table_[idx].key == key) { // key 已存在，更新 value table_[idx].value = value; return true; } } return false; } std::optional<V> find(const K& key) const { const size_t mask = table_.size() - 1; const size_t h = hash_(key) & mask; for (size_t i = 0; i < table_.size(); ++i) { const size_t idx = (h + i) & mask; if (table_[idx].state == SlotState::EMPTY) return std::nullopt; if (table_[idx].state == SlotState::OCCUPIED && table_[idx].key == key) return table_[idx].value; } return std::nullopt; } bool erase(const K& key) { const size_t mask = table_.size() - 1; const size_t h = hash_(key) & mask; for (size_t i = 0; i < table_.size(); ++i) { const size_t idx = (h + i) & mask; if (table_[idx].state == SlotState::EMPTY) return false; if (table_[idx].state == SlotState::OCCUPIED && table_[idx].key == key) { table_[idx].state = SlotState::DELETED; --used_; ++deleted_; return true; } } return false; } size_t size() const { return used_; } size_t capacity() const { return table_.size(); } private: void grow_if_needed() { if (used_ + deleted_ + 1 > table_.size() * max_load_factor_) rehash(table_.size() * 2); } void rehash(size_t new_capacity) { std::vector<Slot> old = std::move(table_); table_.assign(new_capacity, Slot{}); used_ = 0; deleted_ = 0; for (Slot& s : old) { if (s.state == SlotState::OCCUPIED) insert(s.key, s.value); } } std::vector<Slot> table_; Hash hash_{}; size_t used_; size_t deleted_; double max_load_factor_; };

注意grow_if_needed里统计的是used_ + deleted_，不是used_。只算有效元素的话，墓碑多了会出现“表里其实已经塞满非空槽，但used_还没到阈值”的情况，插入循环会白扫一整遍。这个细节等我讲坑的时候再展开。

查找逻辑里最关键的一行是：遇到 EMPTY 就返回不存在。这是开放定址的正确性基石——一个 key 的探测链从它的哈希位置开始，一旦碰到从未被占用的空槽，后面的槽位就不可能是这个 key 的合法位置（插入方向决定了链只会连到空槽为止）。DELETED 槽不能停，它只是“曾经有人住过”的标志，要继续往后找。

3.3 扩容与再散列：为什么元素必须全部重插

当负载因子超标，就要扩容。我选择直接翻倍，保证均摊插入复杂度是 O(1)。扩容有个关键动作：所有元素要重新计算位置，而不是简单复制。

原因很直白：下标 =hash(key) & (capacity - 1)，容量一变，掩码就变，旧下标在新数组里不再是同一个语义位置。甚至同一个 key 在新表的探测链起点都变了。所以 rehash 就是把旧表里所有 OCCUPIED 的元素重新insert到新表。

实现里的old = std::move(table_)先把旧数据挪出来，然后assign一块新内存，最后逐个重插。重插会再次走insert，而insert开头有grow_if_needed，会不会递归扩容？不会，新容量是旧表两倍，而旧表里最多0.7 * 旧容量个有效元素，重插远够用。

还有一个经验：如果删除了大量元素，即使不扩容也应该做一次“同容量重建”，把墓碑清掉。这个我放在问题排查那一节讲。

4. 负载因子与哈希函数的调优细节

4.1 负载因子定多少：把期望探测次数算给你看

负载因子 α = 有效元素数 / 表容量。开放定址里 α 必须小于 1，不然表满了就只能无限探测。线性探测有一个非常经典的期望探测次数公式：

• 查找成功：约0.5 * (1 + 1 / (1 - α))
• 查找失败：约0.5 * (1 + 1 / (1 - α)^2)

直接代入算一下：

看到没有？α 从 0.7 涨到 0.9，查找成功从 2.17 次涨到 5.5 次，还能忍；但查找失败直接从 6 次飙到 50 次。插入操作本质上是“查找失败”，所以插入性能在 α = 0.9 时会崩得很难看。这就是为什么大多数开放定址实现把默认负载因子定在 0.7 附近——再低浪费内存，再高性能拐点太陡。

如果你内存紧张，可以调到 0.85，但要有心理准备：查找和插入都会明显变慢。如果是写一个长期跑的服务，我建议 0.6~0.7，用一点内存换稳定性很划算。

4.2 哈希函数写不好，一切都白搭

很多人以为哈希函数随便写写就行，其实开放定址对哈希函数的分布要求比拉链法苛刻得多。拉链法哈希值聚成一坨也就链表长一点，开放定址一旦聚集，探测链整体变长，表局部提前“假满”。

三条经验：

• std::hash<int>在主流实现里就是返回原值。如果你的 key 全是偶数，表容量是 16 时key & 15永远落在偶数槽，一半的表空间直接废掉。解决方式是先用一个次级哈希把低位打散，例如乘一个大奇数再取高位，或者干脆让表长取素数后用取模。
• 字符串 key 用std::hash<std::string>就好，它内部的乘法和异或已经够用。
• 自定义类型要么特化std::hash，要么把自定义哈希器作为模板参数传进去。我在代码里给出了Hash模板参数，就是这个目的。

哈希函数到底好不好，别靠猜。写个小程序随机插几十万条数据，统计平均探测次数，和理论公式对比一下，偏差太大就是哈希分布有问题。

4.3 缓存友好到底有多大优势

开放定址最大的王牌是连续内存。线性探测时你访问的是相邻的缓存行，即使探测三五次，命中的也基本是同一块 cache line；拉链法的链表节点在堆上散落着，每跳一次都可能触发 cache miss。

我自己在本地做过一个粗糙的对照实验：一百万个整数 key，随机查询十万次，开放定址线性探测（负载因子 0.6）比std::unordered_map快大约 30%~50%。当然这个数字不能当论文结论，平台、编译选项、key 类型一变结果就不一样了，但趋势是稳定的：低负载、连续内存场景下开放定址确实赢。

反过来，如果负载因子压得很高，或者删除很频繁，开放定址的优势就会被探测次数吃掉，这时候拉链法反而更稳。所以选型从来不是“谁更好”，而是“你的场景是什么”。

5. 实战排查：我踩过的四个经典问题

5.1 删除就出错？墓碑为什么不许清空

第一次写开放定址删除时，我图省事，把要删的槽直接置为 EMPTY，结果表现为：删除某个 key 之后，其他明明存在的 key 找不到了。举个例子：

假设三个 key A、B、C 都哈希到同一个位置。插入顺序是 A 占 1 号槽，B 冲突探测到 2 号槽，C 再冲突探测到 3 号槽。此时删除 B，如果你把 2 号槽置为 EMPTY，那么查找 C 时从 1 号槽开始，1 号是 A，2 号是 EMPTY——根据查找规则直接返回“C 不存在”。这就是探测链被截断。

墓碑方案就是让 2 号槽保持 DELETED，查找时跳过它继续往后走，直到 EMPTY 才停下。这也是find里那种状态判断写法的由来：OCCUPIED 就比对 key，DELETED 就跳过，EMPTY 就停止。

5.2 插入后出现重复 key：一个隐蔽的墓碑 bug

这个坑我在自己的实现里踩过一次，而且不写测试根本发现不了。假设 A 在 1 号槽，B 在 2 号槽，C 在 3 号槽。删除 A 后 1 号槽变成 DELETED。此时如果你“重新插入 C 来更新它的值”，朴素实现会在探测到 1 号槽是 DELETED 时就把它当作空位，把 C 写进去。结果呢？C 同时出现在 1 号槽和 3 号槽，重复了。

正确做法就是我在insert里写的：先继续扫描整条探测链，直到空槽为止；如果中间找到了相同的 key，直接更新并返回；如果找不到，才回填到第一个遇到的墓碑。这个“先查找、后落位”的顺序不能颠倒。

后来我检查过不少网上的示例代码，很多简单教程都忽略了这一点。建议你手写时一定要加一条测试：插入一组元素、删除其中若干、再重新插入之前存在的 key，最后遍历验证没有重复且值更新正确。

5.3 表没满却越来越慢：墓碑堆积

墓碑不会消失，它占着槽位但又被跳过，所以删除操作越多，探测链就越长。更危险的是我之前提过一次：统计负载因子时如果只统计used_，墓碑不会计入，表可能“看起来负载很低”，实际上非空槽已经快占满了。我实现的grow_if_needed把deleted_也计进去了，就是为了防止插入陷入全表扫描。

墓碑堆积的更优雅解法是“同容量重建”：当墓碑数量超过某个阈值时，不扩容，只把表重建成同样大小，让所有 DELETED 槽变回 EMPTY。代码很简单：

void maybe_compact() { if (deleted_ > table_.size() / 4) rehash(table_.size()); }

删除之后调用一下maybe_compact()，墓碑比例就能控制住。如果你的业务模式是“频繁插入、频繁删除”，这个函数能救大命。

5.4 调试技巧：把表打出来看

哈希表的 bug 特别难靠肉眼查，因为探测过程在脑子里模拟几步还行，几千个元素之后就全乱了。我的习惯是写一个dump()函数，把每个槽的状态和 key 打印出来。

void dump() const { for (size_t i = 0; i < table_.size(); ++i) { const char* st = "E"; if (table_[i].state == SlotState::OCCUPIED) st = "O"; else if (table_[i].state == SlotState::DELETED) st = "D"; std::cout << i << ": [" << st << "] "; if (table_[i].state == SlotState::OCCUPIED) std::cout << table_[i].key; std::cout << "\n"; } }

再配合一个探测次数统计，插入完一批数据后，随机查找并累加探测步数，和理论期望值对一下。有一次我发现平均探测次数远高于理论值，一查才发现是哈希函数在偶数 key 上的分布问题，dump()里空槽分布一目了然——这种情况下靠二分查找代码，十天都未必找得到。

我还习惯用两类数据集做压力测试：一类是完全随机的 key，一类是严格递增的 key。随机集能暴露通用逻辑错误，递增集能暴露哈希函数和表长配合的问题。两类都过了，这个表才算基本能信任。

最后再分享一个我的体会：开放定址算法本身不难，难的是所有边界情况都考虑到。空槽、墓碑、重复 key、扩容时序，任何一个环节想当然都会在数据量大了之后冒出来。但正因为如此，手写一遍收获特别大——你以后再用unordered_map，心里是有一张完整的图的，它每一个操作在底层大概怎么走，你都能猜个八九不离十。这种“底层感”是单纯看文档学不来的，建议每个人都亲手写一遍。