提到哈希表大部分人第一反应是链地址法C标准库里的std::unordered_map底层也是这么干的。直到我前阵子看Google的SwissTable源码和abseil的flat_hash_map时才意识到开放定址法在实际工程里的地位远被低估。正巧面到一道“开放定址法删除元素时怎么处理”的题当时回答得不算透彻回来后干脆把整个实现重写了一遍。这篇就来聊聊开放定址法的完整C实现从原理、删除为什么难、扩容怎么处理到能直接编译运行的代码最后再讲几个教材不会告诉你的坑。1. 为什么选开放定址法链地址法与开放定址法的本质差异1.1 两者在内存布局和冲突处理上的根本区别链地址法的思路很直白每个桶后面挂一个链表冲突的键都往这个链表里塞。std::unordered_map的经典实现就是桶数组加单链表每个节点还额外存了哈希值和next指针。这样做的好处是实现简单删除也好办链表摘掉节点就行坏处也明显——节点是堆上单独分配的每次插入都伴随一次new键和值分散在不同内存地址遍历和查找时Cache Miss率很高。对于现代CPU来说内存访问局部性往往比算法复杂度更影响最终耗时。开放定址法反过来所有元素都存在一个连续的数组里不发生“额外分配”。冲突时顺着探查序列找下一个空位理解了这一点就理解了它的全部核心。因为没有链表任何查找都是从哈希计算出来的起始位置开始沿着同样的规则往后扫直到碰到空槽或者找到目标键。1.2 开放定址法真正适合的场景我在做缓存类组件、小对象字典、读多写少的配置表时比较倾向开放定址法。这些场景有几个共同点元素数量规模可控能把载荷因子压住查频率远高于增删缓存命中率收益明显数据是值语义不需要稳定的引用或指针希望省内存不想每个节点带指针域。反过来如果数据量不确定、删除很频繁、或者元素构造代价很高链地址法会更稳妥。工程选型没有银弹所谓“更高级”的方案换来的往往是另一方面的代价。2. 探查序列是灵魂线性探测、二次探测和双重哈希2.1 探查序列怎么定义哈希函数算出初始下标idx后如果table[idx]已经被占用不能直接换一个哈希函数重算而是用一种确定性的规则在数组里继续找空位。这个规则就叫探查序列。三种经典方案方案第i次探查位置特点线性探测(hash(key) i) % capacity最简单但容易产生一次聚集二次探测(hash(key) i^2) % capacity缓解一次聚集但只覆盖部分槽位双重哈希(hash(key) i * h2(key)) % capacity需要第二个哈希函数覆盖更均匀2.2 线性探测的过程拆解线性探测看似简单却是最容易被坑的一个。比如容量是7的哈希表依次插入键12, 15, 26, 19哈希函数取模712 % 7 5插入下标515 % 7 1插入下标126 % 7 5冲突探查6空插入下标619 % 7 5冲突查6已被占再查0空插入下标0。这个过程中5、6、0连成了一条拥挤的探测链。下次任何一个哈希到5的键都要先经过5、6才能到达空位。这就是教科书上说的“一次聚集”。用大白话说冲突的键会挤在一小片区域导致这片区域查询次数急剧增加。2.3 为什么要引入二次探测和双重哈希二次探测让后续探查位置跳跃起来而不是一格一格挪这样能分散聚集。但注意二次探测的探查序列可能只覆盖表的一部分。比如容量16的表i^2 % 16只产生0,1,4,9几个位置很多槽位永远访问不到。所以二次探测对表容量有要求通常要选形如4k3的质数工程上比线性探测麻烦不少。双重哈希是另一种思路它相当于把“步长”也哈希化。两个哈希函数一个定位一个定步长。这样不容易聚集但代价是每次探查要算两次哈希CPU开销上去了。而且h2(key)的值最好和表大小互质否则同样可能漏掉部分槽位。如果以代码简单和可预测性优先线性探测是第一选择如果哈希质量足够好双重哈希是最稳的。我个人做封装时默认线性探测把优化重心放在哈希函数上因为哈希函数质量差再花哨的探查策略都救不了。3. 删除为什么这么难三态标记与惰性删除3.1 直接置空会毁掉整个查找链这是开放定址法最容易翻车的点。如果删掉的槽位直接标记成EMPTY后续查找某个键时探查序列走到这个位置就会提前终止。问题是那个键可能本来排在后面的某个槽位里但它前面的一个槽被删空后查找过程就会误以为“后面不可能有相等的键”然后提前结束。举个例子。容量7的哈希表依次插入26和19这两个键哈希值都是5。26先进下标519冲突后进下标6。现在删除26如果直接把下标5置为EMPTY再查19时会发现起始位置5是空的立刻返回“不存在”而实际上19就活在隔壁下标6。数据直接丢失在逻辑层。所以开放定址法删除时不能置空只能打一个“已删除”标记查找时遇到这个标记不能停要继续往后探查。这就是惰性删除的基本逻辑。3.2 用枚举定义三种槽位状态我实现时给每个槽位设计了三态enum class State : uint8_t { EMPTY, // 从未使用过查找遇到它可以直接停 OCCUPIED, // 实实在在存着数据 DELETED // 被删除过但查找时不能停在这里 };为什么查找遇到EMPTY可以停因为插入算法是往第一个空位放的如果某个键存在它和它的所有“前辈”之间不可能出现从未使用过的空槽。一旦出现EMPTY说明探查序列后半段从来没被这个哈希族使用过目标键不可能藏在这里。反过来DELETED说明有元素曾经占据过这个位置可能是目标键的前驱所以必须穿越。3.3 DELETED槽位多了会有什么后果标记删除省了真删的麻烦但数组里DELETED越积越多查找路径上全是“死人”平均探查次数会逐步增大性能劣化非常隐蔽。我在实测中发现当删除量达到总容量的三成左右一次查找可能要扫过七八个DELETED才能碰到EMPTY。更麻烦的是DELETED槽不计数也不贡献有效元素载荷因子按有效元素算可能很低触发不了扩容。这时候需要引入另一个指标——脏槽率或者干脆用有效元素和删除槽之和来判断要不要这做一次rehash。这个问题我在第6节详细说。4. 扩容与rehash什么时候扩、怎么迁最安全4.1 载荷因子为何是性能的杠杆载荷因子 有效元素数 / 表容量。对开放定址法来说这个值越高探查序列越长性能断崖式下降。为什么不是线性下降因为当表越来越满新插入的键找到空位平均要走的步数增长远快于线性。工程上常见的经验阈值线性探测建议 0.5 ~ 0.7二次探测建议 0.5 ~ 0.6双重哈希建议 0.7 以下。我把阈值设成0.7插入前检查size_ * 10 capacity * 7超过就触发rehash。注意一定要在插入前检查否则插入后可能超载下一次查询性能就已经劣化了。4.2 扩容时的细节不能直接搬数据表扩容后容量变了每个键的hash(key) % capacity结果可能完全变掉。所以迁移必须逐个重算哈希并重新插入不能像数组扩容那样平滑拷贝。这也是开放定址法里最耗时的操作之一实测容量从16扩到32需要把老数组里所有活着的元素一个个重新插进新表。我实现rehash时用了一个技巧先把旧表std::move到临时变量再给table_分配新容量并重新初始化。然后遍历旧表只处理OCCUPIED的槽位调用一个不检查载荷因子的内部插入函数避免递归触发扩容。4.3 扩容后的迭代器失效问题开放定址法在扩容后所有元素的下标都变了所以任何指向元素的迭代器、指针、引用都会失效。这个和std::vector扩容导致迭代器失效是一个道理但unordered_map的链地址法在rehash之后迭代器不失效两者行为差异很大。如果外部代码长期持有指向哈希表内部元素的指针扩容就是隐性地雷。我在实际项目里会刻意回避存这种指针改用查找后立即消费的模式。5. 代码实现一个可直接编译的开放定址哈希表5.1 类骨架设计我用模板实现支持任意键值类型的HashMap核心成员只有三个存储槽位的vector、有效元素数elem_count_、删除槽数deleted_count_。节点的键值对放在Slot里Slot本身默认构造时不初始化键值只有真正插入才构造减少无谓开销。template typename Key, typename Value class OpenAddressingHashTable { public: explicit OpenAddressingHashTable(size_t init_capacity 8) : table_(std::max(init_capacity, (size_t)4), Slot{}), elem_count_(0), deleted_count_(0) {} void insert(const Key key, const Value val) { if (needRehash()) rehash(); insertNoResize(key, val); } Value* find(const Key key) { /* 核心实现 */ } bool erase(const Key key) { /* 核心实现 */ } size_t size() const { return elem_count_; } bool empty() const { return elem_count_ 0; } private: enum class State : uint8_t { EMPTY, OCCUPIED, DELETED }; struct Slot { State state; std::pairKey, Value kv; Slot() : state(State::EMPTY) {} }; std::vectorSlot table_; size_t elem_count_; size_t deleted_count_; };5.2 核心的insert / find / erase实现insert是最容易写错的函数。不能一遇到DELETED就立刻占位必须先记录第一个DELETED位置继续探查确认整个探查链上不存在相同键之后再回头插入。否则可能发生同一个键插两次、或者更新不到某个位于DELETED槽之后的键。void insertNoResize(const Key key, const Value val) { size_t idx hash(key); size_t firstDeleted table_.size(); // 哨兵值表示“没遇到过DELETED” while (table_[idx].state ! State::EMPTY) { if (table_[idx].state State::OCCUPIED table_[idx].kv.first key) { table_[idx].kv.second val; // 键已存在更新值 return; } if (table_[idx].state State::DELETED firstDeleted table_.size()) { firstDeleted idx; } idx (idx 1) % table_.size(); } size_t target (firstDeleted ! table_.size()) ? firstDeleted : idx; table_[target].state State::OCCUPIED; table_[target].kv std::make_pair(key, val); elem_count_; if (firstDeleted ! table_.size()) --deleted_count_; }find的逻辑则简单得多遇到EMPTY直接返回空指针遇到OCCUPIED就比较键遇到DELETED继续走Value* find(const Key key) { size_t idx hash(key); while (table_[idx].state ! State::EMPTY) { if (table_[idx].state State::OCCUPIED table_[idx].kv.first key) { return table_[idx].kv.second; } idx (idx 1) % table_.size(); } return nullptr; }erase同样顺着探查链走找到匹配键后不能直接销毁对象替换成EMPTY只置为DELETED并把键值对重置为默认值防止大对象占着内存不释放。这里注意要把elem_count_减一、deleted_count_加一bool erase(const Key key) { size_t idx hash(key); while (table_[idx].state ! State::EMPTY) { if (table_[idx].state State::OCCUPIED table_[idx].kv.first key) { table_[idx].state State::DELETED; table_[idx].kv std::pairKey, Value(); --elem_count_; deleted_count_; return true; } idx (idx 1) % table_.size(); } return false; }5.3 rehash与辅助函数rehash把旧表整体搬过去新容量建议翻倍并取质数。为什么取质数我用的哈希是std::hashKey{}(key) % capacity如果容量是2的幂哈希结果的低位会主导下标分布一旦哈希值的低位模式有规律冲突就很严重。取质数能打散这种规律。当然这是“用除法换分布”的经典做法现代CPU对取模已经优化得不错这点代价大部分时候值得。void rehash() { size_t oldCap table_.size(); size_t newCap nextPrime(oldCap * 2); std::vectorSlot oldTable std::move(table_); table_.assign(newCap, Slot{}); elem_count_ 0; deleted_count_ 0; for (auto slot : oldTable) { if (slot.state State::OCCUPIED) { insertNoResize(slot.kv.first, slot.kv.second); } } } bool needRehash() const { return (elem_count_ deleted_count_) * 10 table_.size() * 7; } size_t hash(const Key key) const { return std::hashKey{}(key) % table_.size(); } static bool isPrime(size_t n) { if (n 2) return false; for (size_t i 2; i * i n; i) if (n % i 0) return false; return true; } static size_t nextPrime(size_t n) { while (!isPrime(n)) n; return n; }这里有个细节needRehash看的不是有效元素数而是有效元素数加删除槽数。因为DELETED虽然不算有效元素但它一样会拖累查找。如果只看有效元素可能表空了七成但要查一个已删除的键还是得趟过一片DELETED性能照样差。把deleted_count_算进去之后脏槽多了也会触发扩容重建等于自动洗掉垃圾。5.4 一个简易的测试驱动验证下面这段代码可以直接跑覆盖了插入、更新、删除、扩容后查找几个核心场景#include iostream #include string int main() { OpenAddressingHashTablestd::string, int scores; scores.insert(alice, 90); scores.insert(bob, 85); scores.insert(carol, 78); scores.insert(dave, 92); // 触发扩容的候选 if (auto* val scores.find(bob)) { std::cout bob: *val std::endl; } scores.insert(bob, 99); // 更新 if (auto* val scores.find(bob)) { std::cout bob updated: *val std::endl; } std::cout erase carol: scores.erase(carol) std::endl; std::cout find carol after erase: (scores.find(carol) ? found : not found) std::endl; std::cout size: scores.size() std::endl; return 0; }6. 实测与避坑记录这些细节教材不会写6.1 边界行为验证清单写完代码别急着上线先用一个checklist把边界过一遍空表里find任意键必须返回nullptr插入重复键值要更新表大小不能变删除不存在的键返回false且表状态不变删除后再插入相同键应复用DELETED槽而不是把表撑大插入大量数据触发多次rehash之后所有键仍能找回来键被删除后同哈希族其他键不能丢。第六条是最典型的回归测试。我用26和19这类哈希值相同的键专门测过删除26后19必须还能找到。之前说过一旦删除逻辑把槽置成EMPTY这条用例直接挂掉。所以我在测试代码里专门构造了一组冲突键来验证不要只拿顺序整数测那样哈希值天然均匀测不出探查链问题。6.2 三态标记引入的连锁坑第一个坑是DELETED槽被填时elem_count_和deleted_count_的增减容易算错。插入到DELETED槽时有效元素加一、删除槽减一这个逻辑没错但如果你忘了减deleted_count_下次needRehash会把实际使用量估高导致频繁扩容性能反而变差。第二个坑是键值对象被重置。我在erase里执行table_[idx].kv std::pairKey, Value()这一步是为了及时释放键或值里可能持有的堆资源。但如果Key或Value是不可默认构造的编译就过不了。工业级做法通常给Slot再加一个hasValue标记析构时手动调用析构函数而不是依赖赋值重置。为了demo简洁我没这么做但你自己用的时候要意识到这个限制。第三个坑是关于哈希函数的。std::hashstd::string质量没问题但如果你用自定义结构体当键而忘了提供好的哈希特化所有键都会挤到少数几个槽位开放定址法会退化成数组遍历。排查方法很简单往表里塞几千个数据观察elem_count_不变的情况下平均查找步数是否异常增长。我在某次用自定义坐标结构体当键时踩过一次坐标哈希只算了x没算y结果同x的键全排成一条长队。6.3 和链地址法的实测对比心得我用10万条随机整数分别测了链地址法和线性探测开放定址法。链表版用的std::unordered_map开放定址版用的上面这个实现。在载荷因子0.7附近开放定址的查找时间大约是链地址的60%到75%。原因是所有槽位都在一块连续内存里CPU缓存一次拉进一条cache line一次能检查多个槽位。链地址的节点分散在堆上每次跳转都可能cache miss。但在频繁删除场景下开放定址的优势会缩小因为DELETED槽让查找路径变长。我试过连续删除一半元素后继续查找未删除的元素开放定址的耗时比新鲜rehash之后慢了一倍以上。这就是为什么我强调脏槽率要和有效载荷一起监控。如果你做的是写多删多的缓存层链地址法更省心做读多写少的查找表开放定址值得认真考虑。工程选择永远是对trade-off的取舍没有绝对优劣。还有个小技巧如果确定键的数量上限可以提前把表容量设到大一点的质数让载荷因子一开始就很低这样rehash的次数会明显减少插入性能更稳定。我自己做配置表加载时会先扫描一遍键数量再调用带初始容量的构造函数实测启动耗时能降不少。 开放定址法C++实现：原理、删除与扩容实战指南
提到哈希表大部分人第一反应是链地址法C标准库里的std::unordered_map底层也是这么干的。直到我前阵子看Google的SwissTable源码和abseil的flat_hash_map时才意识到开放定址法在实际工程里的地位远被低估。正巧面到一道“开放定址法删除元素时怎么处理”的题当时回答得不算透彻回来后干脆把整个实现重写了一遍。这篇就来聊聊开放定址法的完整C实现从原理、删除为什么难、扩容怎么处理到能直接编译运行的代码最后再讲几个教材不会告诉你的坑。1. 为什么选开放定址法链地址法与开放定址法的本质差异1.1 两者在内存布局和冲突处理上的根本区别链地址法的思路很直白每个桶后面挂一个链表冲突的键都往这个链表里塞。std::unordered_map的经典实现就是桶数组加单链表每个节点还额外存了哈希值和next指针。这样做的好处是实现简单删除也好办链表摘掉节点就行坏处也明显——节点是堆上单独分配的每次插入都伴随一次new键和值分散在不同内存地址遍历和查找时Cache Miss率很高。对于现代CPU来说内存访问局部性往往比算法复杂度更影响最终耗时。开放定址法反过来所有元素都存在一个连续的数组里不发生“额外分配”。冲突时顺着探查序列找下一个空位理解了这一点就理解了它的全部核心。因为没有链表任何查找都是从哈希计算出来的起始位置开始沿着同样的规则往后扫直到碰到空槽或者找到目标键。1.2 开放定址法真正适合的场景我在做缓存类组件、小对象字典、读多写少的配置表时比较倾向开放定址法。这些场景有几个共同点元素数量规模可控能把载荷因子压住查频率远高于增删缓存命中率收益明显数据是值语义不需要稳定的引用或指针希望省内存不想每个节点带指针域。反过来如果数据量不确定、删除很频繁、或者元素构造代价很高链地址法会更稳妥。工程选型没有银弹所谓“更高级”的方案换来的往往是另一方面的代价。2. 探查序列是灵魂线性探测、二次探测和双重哈希2.1 探查序列怎么定义哈希函数算出初始下标idx后如果table[idx]已经被占用不能直接换一个哈希函数重算而是用一种确定性的规则在数组里继续找空位。这个规则就叫探查序列。三种经典方案方案第i次探查位置特点线性探测(hash(key) i) % capacity最简单但容易产生一次聚集二次探测(hash(key) i^2) % capacity缓解一次聚集但只覆盖部分槽位双重哈希(hash(key) i * h2(key)) % capacity需要第二个哈希函数覆盖更均匀2.2 线性探测的过程拆解线性探测看似简单却是最容易被坑的一个。比如容量是7的哈希表依次插入键12, 15, 26, 19哈希函数取模712 % 7 5插入下标515 % 7 1插入下标126 % 7 5冲突探查6空插入下标619 % 7 5冲突查6已被占再查0空插入下标0。这个过程中5、6、0连成了一条拥挤的探测链。下次任何一个哈希到5的键都要先经过5、6才能到达空位。这就是教科书上说的“一次聚集”。用大白话说冲突的键会挤在一小片区域导致这片区域查询次数急剧增加。2.3 为什么要引入二次探测和双重哈希二次探测让后续探查位置跳跃起来而不是一格一格挪这样能分散聚集。但注意二次探测的探查序列可能只覆盖表的一部分。比如容量16的表i^2 % 16只产生0,1,4,9几个位置很多槽位永远访问不到。所以二次探测对表容量有要求通常要选形如4k3的质数工程上比线性探测麻烦不少。双重哈希是另一种思路它相当于把“步长”也哈希化。两个哈希函数一个定位一个定步长。这样不容易聚集但代价是每次探查要算两次哈希CPU开销上去了。而且h2(key)的值最好和表大小互质否则同样可能漏掉部分槽位。如果以代码简单和可预测性优先线性探测是第一选择如果哈希质量足够好双重哈希是最稳的。我个人做封装时默认线性探测把优化重心放在哈希函数上因为哈希函数质量差再花哨的探查策略都救不了。3. 删除为什么这么难三态标记与惰性删除3.1 直接置空会毁掉整个查找链这是开放定址法最容易翻车的点。如果删掉的槽位直接标记成EMPTY后续查找某个键时探查序列走到这个位置就会提前终止。问题是那个键可能本来排在后面的某个槽位里但它前面的一个槽被删空后查找过程就会误以为“后面不可能有相等的键”然后提前结束。举个例子。容量7的哈希表依次插入26和19这两个键哈希值都是5。26先进下标519冲突后进下标6。现在删除26如果直接把下标5置为EMPTY再查19时会发现起始位置5是空的立刻返回“不存在”而实际上19就活在隔壁下标6。数据直接丢失在逻辑层。所以开放定址法删除时不能置空只能打一个“已删除”标记查找时遇到这个标记不能停要继续往后探查。这就是惰性删除的基本逻辑。3.2 用枚举定义三种槽位状态我实现时给每个槽位设计了三态enum class State : uint8_t { EMPTY, // 从未使用过查找遇到它可以直接停 OCCUPIED, // 实实在在存着数据 DELETED // 被删除过但查找时不能停在这里 };为什么查找遇到EMPTY可以停因为插入算法是往第一个空位放的如果某个键存在它和它的所有“前辈”之间不可能出现从未使用过的空槽。一旦出现EMPTY说明探查序列后半段从来没被这个哈希族使用过目标键不可能藏在这里。反过来DELETED说明有元素曾经占据过这个位置可能是目标键的前驱所以必须穿越。3.3 DELETED槽位多了会有什么后果标记删除省了真删的麻烦但数组里DELETED越积越多查找路径上全是“死人”平均探查次数会逐步增大性能劣化非常隐蔽。我在实测中发现当删除量达到总容量的三成左右一次查找可能要扫过七八个DELETED才能碰到EMPTY。更麻烦的是DELETED槽不计数也不贡献有效元素载荷因子按有效元素算可能很低触发不了扩容。这时候需要引入另一个指标——脏槽率或者干脆用有效元素和删除槽之和来判断要不要这做一次rehash。这个问题我在第6节详细说。4. 扩容与rehash什么时候扩、怎么迁最安全4.1 载荷因子为何是性能的杠杆载荷因子 有效元素数 / 表容量。对开放定址法来说这个值越高探查序列越长性能断崖式下降。为什么不是线性下降因为当表越来越满新插入的键找到空位平均要走的步数增长远快于线性。工程上常见的经验阈值线性探测建议 0.5 ~ 0.7二次探测建议 0.5 ~ 0.6双重哈希建议 0.7 以下。我把阈值设成0.7插入前检查size_ * 10 capacity * 7超过就触发rehash。注意一定要在插入前检查否则插入后可能超载下一次查询性能就已经劣化了。4.2 扩容时的细节不能直接搬数据表扩容后容量变了每个键的hash(key) % capacity结果可能完全变掉。所以迁移必须逐个重算哈希并重新插入不能像数组扩容那样平滑拷贝。这也是开放定址法里最耗时的操作之一实测容量从16扩到32需要把老数组里所有活着的元素一个个重新插进新表。我实现rehash时用了一个技巧先把旧表std::move到临时变量再给table_分配新容量并重新初始化。然后遍历旧表只处理OCCUPIED的槽位调用一个不检查载荷因子的内部插入函数避免递归触发扩容。4.3 扩容后的迭代器失效问题开放定址法在扩容后所有元素的下标都变了所以任何指向元素的迭代器、指针、引用都会失效。这个和std::vector扩容导致迭代器失效是一个道理但unordered_map的链地址法在rehash之后迭代器不失效两者行为差异很大。如果外部代码长期持有指向哈希表内部元素的指针扩容就是隐性地雷。我在实际项目里会刻意回避存这种指针改用查找后立即消费的模式。5. 代码实现一个可直接编译的开放定址哈希表5.1 类骨架设计我用模板实现支持任意键值类型的HashMap核心成员只有三个存储槽位的vector、有效元素数elem_count_、删除槽数deleted_count_。节点的键值对放在Slot里Slot本身默认构造时不初始化键值只有真正插入才构造减少无谓开销。template typename Key, typename Value class OpenAddressingHashTable { public: explicit OpenAddressingHashTable(size_t init_capacity 8) : table_(std::max(init_capacity, (size_t)4), Slot{}), elem_count_(0), deleted_count_(0) {} void insert(const Key key, const Value val) { if (needRehash()) rehash(); insertNoResize(key, val); } Value* find(const Key key) { /* 核心实现 */ } bool erase(const Key key) { /* 核心实现 */ } size_t size() const { return elem_count_; } bool empty() const { return elem_count_ 0; } private: enum class State : uint8_t { EMPTY, OCCUPIED, DELETED }; struct Slot { State state; std::pairKey, Value kv; Slot() : state(State::EMPTY) {} }; std::vectorSlot table_; size_t elem_count_; size_t deleted_count_; };5.2 核心的insert / find / erase实现insert是最容易写错的函数。不能一遇到DELETED就立刻占位必须先记录第一个DELETED位置继续探查确认整个探查链上不存在相同键之后再回头插入。否则可能发生同一个键插两次、或者更新不到某个位于DELETED槽之后的键。void insertNoResize(const Key key, const Value val) { size_t idx hash(key); size_t firstDeleted table_.size(); // 哨兵值表示“没遇到过DELETED” while (table_[idx].state ! State::EMPTY) { if (table_[idx].state State::OCCUPIED table_[idx].kv.first key) { table_[idx].kv.second val; // 键已存在更新值 return; } if (table_[idx].state State::DELETED firstDeleted table_.size()) { firstDeleted idx; } idx (idx 1) % table_.size(); } size_t target (firstDeleted ! table_.size()) ? firstDeleted : idx; table_[target].state State::OCCUPIED; table_[target].kv std::make_pair(key, val); elem_count_; if (firstDeleted ! table_.size()) --deleted_count_; }find的逻辑则简单得多遇到EMPTY直接返回空指针遇到OCCUPIED就比较键遇到DELETED继续走Value* find(const Key key) { size_t idx hash(key); while (table_[idx].state ! State::EMPTY) { if (table_[idx].state State::OCCUPIED table_[idx].kv.first key) { return table_[idx].kv.second; } idx (idx 1) % table_.size(); } return nullptr; }erase同样顺着探查链走找到匹配键后不能直接销毁对象替换成EMPTY只置为DELETED并把键值对重置为默认值防止大对象占着内存不释放。这里注意要把elem_count_减一、deleted_count_加一bool erase(const Key key) { size_t idx hash(key); while (table_[idx].state ! State::EMPTY) { if (table_[idx].state State::OCCUPIED table_[idx].kv.first key) { table_[idx].state State::DELETED; table_[idx].kv std::pairKey, Value(); --elem_count_; deleted_count_; return true; } idx (idx 1) % table_.size(); } return false; }5.3 rehash与辅助函数rehash把旧表整体搬过去新容量建议翻倍并取质数。为什么取质数我用的哈希是std::hashKey{}(key) % capacity如果容量是2的幂哈希结果的低位会主导下标分布一旦哈希值的低位模式有规律冲突就很严重。取质数能打散这种规律。当然这是“用除法换分布”的经典做法现代CPU对取模已经优化得不错这点代价大部分时候值得。void rehash() { size_t oldCap table_.size(); size_t newCap nextPrime(oldCap * 2); std::vectorSlot oldTable std::move(table_); table_.assign(newCap, Slot{}); elem_count_ 0; deleted_count_ 0; for (auto slot : oldTable) { if (slot.state State::OCCUPIED) { insertNoResize(slot.kv.first, slot.kv.second); } } } bool needRehash() const { return (elem_count_ deleted_count_) * 10 table_.size() * 7; } size_t hash(const Key key) const { return std::hashKey{}(key) % table_.size(); } static bool isPrime(size_t n) { if (n 2) return false; for (size_t i 2; i * i n; i) if (n % i 0) return false; return true; } static size_t nextPrime(size_t n) { while (!isPrime(n)) n; return n; }这里有个细节needRehash看的不是有效元素数而是有效元素数加删除槽数。因为DELETED虽然不算有效元素但它一样会拖累查找。如果只看有效元素可能表空了七成但要查一个已删除的键还是得趟过一片DELETED性能照样差。把deleted_count_算进去之后脏槽多了也会触发扩容重建等于自动洗掉垃圾。5.4 一个简易的测试驱动验证下面这段代码可以直接跑覆盖了插入、更新、删除、扩容后查找几个核心场景#include iostream #include string int main() { OpenAddressingHashTablestd::string, int scores; scores.insert(alice, 90); scores.insert(bob, 85); scores.insert(carol, 78); scores.insert(dave, 92); // 触发扩容的候选 if (auto* val scores.find(bob)) { std::cout bob: *val std::endl; } scores.insert(bob, 99); // 更新 if (auto* val scores.find(bob)) { std::cout bob updated: *val std::endl; } std::cout erase carol: scores.erase(carol) std::endl; std::cout find carol after erase: (scores.find(carol) ? found : not found) std::endl; std::cout size: scores.size() std::endl; return 0; }6. 实测与避坑记录这些细节教材不会写6.1 边界行为验证清单写完代码别急着上线先用一个checklist把边界过一遍空表里find任意键必须返回nullptr插入重复键值要更新表大小不能变删除不存在的键返回false且表状态不变删除后再插入相同键应复用DELETED槽而不是把表撑大插入大量数据触发多次rehash之后所有键仍能找回来键被删除后同哈希族其他键不能丢。第六条是最典型的回归测试。我用26和19这类哈希值相同的键专门测过删除26后19必须还能找到。之前说过一旦删除逻辑把槽置成EMPTY这条用例直接挂掉。所以我在测试代码里专门构造了一组冲突键来验证不要只拿顺序整数测那样哈希值天然均匀测不出探查链问题。6.2 三态标记引入的连锁坑第一个坑是DELETED槽被填时elem_count_和deleted_count_的增减容易算错。插入到DELETED槽时有效元素加一、删除槽减一这个逻辑没错但如果你忘了减deleted_count_下次needRehash会把实际使用量估高导致频繁扩容性能反而变差。第二个坑是键值对象被重置。我在erase里执行table_[idx].kv std::pairKey, Value()这一步是为了及时释放键或值里可能持有的堆资源。但如果Key或Value是不可默认构造的编译就过不了。工业级做法通常给Slot再加一个hasValue标记析构时手动调用析构函数而不是依赖赋值重置。为了demo简洁我没这么做但你自己用的时候要意识到这个限制。第三个坑是关于哈希函数的。std::hashstd::string质量没问题但如果你用自定义结构体当键而忘了提供好的哈希特化所有键都会挤到少数几个槽位开放定址法会退化成数组遍历。排查方法很简单往表里塞几千个数据观察elem_count_不变的情况下平均查找步数是否异常增长。我在某次用自定义坐标结构体当键时踩过一次坐标哈希只算了x没算y结果同x的键全排成一条长队。6.3 和链地址法的实测对比心得我用10万条随机整数分别测了链地址法和线性探测开放定址法。链表版用的std::unordered_map开放定址版用的上面这个实现。在载荷因子0.7附近开放定址的查找时间大约是链地址的60%到75%。原因是所有槽位都在一块连续内存里CPU缓存一次拉进一条cache line一次能检查多个槽位。链地址的节点分散在堆上每次跳转都可能cache miss。但在频繁删除场景下开放定址的优势会缩小因为DELETED槽让查找路径变长。我试过连续删除一半元素后继续查找未删除的元素开放定址的耗时比新鲜rehash之后慢了一倍以上。这就是为什么我强调脏槽率要和有效载荷一起监控。如果你做的是写多删多的缓存层链地址法更省心做读多写少的查找表开放定址值得认真考虑。工程选择永远是对trade-off的取舍没有绝对优劣。还有个小技巧如果确定键的数量上限可以提前把表容量设到大一点的质数让载荷因子一开始就很低这样rehash的次数会明显减少插入性能更稳定。我自己做配置表加载时会先扫描一遍键数量再调用带初始容量的构造函数实测启动耗时能降不少。