std::unordered_map已足够，其底层用分离链表法（GCC）或线性探测，含负载控制与rehash；手写推荐链地址法（vector+forward_list），桶数取质数，需自定义哈希与相等比较。
用 std::unordered_map 就够了，但得知道它背后怎么处理冲突
绝大多数场景下，直接用 std::unordered_map 是最稳妥的选择——它默认用开放定址法（具体是探测步长为 1 的线性探测）或分离链表法（GCC 实现用的是链地址法），底层已做内存对齐、负载因子控制和 rehash 逻辑。你不需要手写，除非在嵌入式、算法题、教学或想控制内存布局。
手写链地址法哈希表：核心是 std::vector + std::list 或 std::forward_list
这是最易理解、插入删除稳定、且避免假阴性（false negative）的方案。关键点不是“怎么存”，而是“怎么算桶号”和“怎么比较键”：
-
hash(key) % bucket_count得桶索引，bucket_count建议设为质数（如 101、1009），减少聚集 - 必须重载
operator==或提供自定义EqualKey函数对象，否则find会失败 - 不要用
std::vector<std::pair<K,V>>模拟桶——每次查找都要遍历整个 vector，失去哈希意义 - 示例片段：
struct SimpleHashMap { std::vector<std::forward_list<std::pair<int, int>>> buckets; size_t sz = 0; SimpleHashMap(size_t n = 101) : buckets(n) {} size_t hash(int k) { return (k * 2654435761U) % buckets.size(); } // 简单乘法哈希 void insert(int k, int v) { auto& list = buckets[hash(k)]; for (auto& p : list) if (p.first == k) { p.second = v; return; } list.emplace_front(k, v); ++sz; } };
线性探测开放定址法：要小心删除标记和二次探测退化
优势是缓存友好、无指针开销；劣势是删除难处理、容易形成“聚集”。常见错误包括：
- 直接把被删元素置为
nullptr或空值 → 后续查找会中断，必须用“墓碑（tombstone）”标记 - 不控制负载因子（建议 ≤ 0.7）→ 查找性能急剧下降，平均探查次数飙升
- 只用
(hash + i) % size线性探测 → 遇到连续占用块就雪崩；可用二次探测：(hash + i*i) % size，但需保证 size 为质数且 ≡ 3 (mod 4) - 别忘了在
insert时检查是否需要 rehash —— 否则find可能永远找不到
自定义哈希函数与 key 类型：std::hash 不是万能的
当你用 std::string 或 std::pair 作 key 时，std::hash 已有特化；但自定义结构体必须显式提供：
立即学习“C++免费学习笔记（深入）”；
- 要么特化
std::hash<MyStruct>，重载operator() - 要么传入 lambda 或 functor 作为第 3 个模板参数：
std::unordered_map<Point, int, decltype(hash_fn)> m(101, hash_fn);
- 别用
reinterpret_cast<size_t>(this)当哈希值——不同对象地址可能只差几个字节，导致严重冲突 - 哈希函数输出应尽量“打散”，推荐 FNV-1a 或 murmur3 的简化版，而非简单求和
真正难的从来不是写一个能跑的哈希表，而是让它的分布足够均匀、扩容足够平滑、边界情况（如全相同 key、极端负载）不崩。这些细节，往往在压测时才暴露。
