std::unordered_map默认用链地址法且不可替换为开放定址法；手写链地址法需桶数组+链表、质数容量与负载因子控制；开放定址法需删除标记和探测策略，二者适用场景不同。
哈希表碰撞时，std::unordered_map 默认用链地址法，但你无法直接控制底层实现
标准库的 std::unordered_map 和 std::unordered_set 确实基于哈希，且主流实现（如 libstdc++、libc++）内部采用链地址法（separate chaining），每个桶（bucket）挂一个链表或小动态数组来存冲突元素。但这是封装好的——你调用 insert() 或 find() 时完全感知不到碰撞逻辑，也**不能替换为开放定址法**。想自定义碰撞处理？必须手写容器。
手写链地址法：用 std::vector + std::list 实现简易哈希表
核心是维护一个桶数组，每个桶存一个链表；哈希函数决定下标，冲突时往对应链表尾部插入。注意三点：
-
std::hash<T>可复用标准哈希，但需特化自定义类型（否则编译失败） - 桶数量应为质数，减少聚集；扩容时需重新哈希全部元素（
rehash） - 查找/删除需遍历链表，最坏 O(n)，但平均 O(1) —— 前提是负载因子（
size() / bucket_count()）控制在 0.75 以下
template <typename K, typename V>
class SimpleHashMap {
std::vector<std::list<std::pair<K, V>>> buckets;
size_t num_elements = 0;
static size_t next_prime(size_t n) { /* 返回大于 n 的最小质数 */ }
<p>public:
SimpleHashMap(size_t init_buckets = 11) : buckets(init_buckets) {}</p><pre class='brush:php;toolbar:false;'>void insert(const K& key, const V& val) {
size_t idx = std::hash<K>{}(key) % buckets.size();
for (auto& p : buckets[idx]) {
if (p.first == key) { p.second = val; return; }
}
buckets[idx].emplace_back(key, val);
++num_elements;
if (num_elements > buckets.size() * 0.75) rehash();
}private: void rehash() { auto old = std::move(buckets); size_t new_size = next_prime(buckets.size() * 2); buckets.assign(new_size, std::list<std::pair<K, V>>{}); for (const auto& list : old) for (const auto& p : list) insert(p.first, p.second); } };
开放定址法难点在探测序列与删除标记，线性探测最易写但容易聚集
所有元素存于单一数组，碰撞时按固定规则（如线性、二次、双重哈希）找下一个空位。关键问题不是“怎么找”，而是：
- 删除不能真删（否则断开探测链），得用特殊标记（如
EMPTY、DELETED）区分“从未用过”和“曾用过已删” - 线性探测（
(hash + i) % capacity）实现简单，但连续冲突会形成“聚集”，性能骤降 - 二次探测（
(hash + i*i) % capacity）缓解聚集，但可能找不到空位（即使有），需容量为质数且负载因子严格 < 0.5 - 双重哈希（
(hash1 + i * hash2) % capacity）效果最好，但hash2必须与容量互质，实现稍复杂
template <typename K, typename V>
class OpenAddressingMap {
struct Entry { K key; V val; enum { EMPTY, VALID, DELETED } state; };
std::vector<Entry> data;
size_t num_valid = 0;
<pre class='brush:php;toolbar:false;'>size_t probe(size_t hash, size_t i) const {
return (hash + i * i) % data.size(); // 二次探测
}public: V& operator[](const K& key) { size_t h = std::hash<K>{}(key); for (size_t i = 0; i < data.size(); ++i) { size_t idx = probe(h, i); if (data[idx].state == Entry::EMPTY) { data[idx] = {key, V{}, Entry::VALID}; ++num_valid; return data[idx].val; } if (data[idx].state == Entry::VALID && data[idx].key == key) { return data[idx].val; } } throw std::runtime_error("Hash table full"); } };
选链地址法还是开放定址法？看场景，别只看理论平均复杂度
链地址法内存开销略大（指针 + 动态分配），但实现鲁棒、支持任意负载因子、删除即释放；开放定址法缓存友好（数据连续）、无指针开销，但扩容成本高、删除麻烦、对哈希质量更敏感。实际选型时：
立即学习“C++免费学习笔记（深入）”；
- 元素小（如
int键值对）、读多写少、内存敏感 → 开放定址法更合适 - 键类型复杂、需频繁增删、不希望手动管理探测逻辑 → 链地址法更省心
- 用
std::unordered_map就别纠结——它已针对通用场景优化过桶结构（如 libc++ 用小数组代替链表，减少分配） - 真正要极致性能？别自己写，用
absl::flat_hash_map（开放定址+混合策略）或tsl::robin_map
手写开放定址法时，DELETED 标记状态和探测终止条件最容易漏判，一错就导致查不到或无限循环。
