链地址法核心在于指针数组管理、哈希函数选型与扩容时原地迁移节点；需用vector存头指针、自定义HashNode含_next、头插免遍历，扩容仅搬指针不new节点，哈希函数须模板特化且string用const引用+BKDR算法。
链地址法解决哈希冲突，核心不是“怎么写链表”，而是“指针数组怎么管、哈希函数怎么选、扩容时怎么不重分配节点”——这三点没对齐，代码跑得越快，出的 bug 越隐蔽。
哈希桶结构必须用 vector<node></node>，不能用 vector<list>>></list>
用 vector<list>></list> 看似省事，但实际破坏了链地址法的本质优势：节点内存连续性可控、插入无拷贝、支持原地迁移。标准库 list 每次 push_front 都要 new 一个节点，而哈希桶中所有 HashNode 应该由你统一管理（比如用 std::allocator 或自定义内存池）。
正确做法是：vector<hashnode></hashnode> 存头指针，每个 HashNode 自带 _next 指针；插入一律头插，避免遍历找尾；节点构造时只初始化 _kv 和 _next，不依赖 list 的迭代器或 size 成员。
- 头插比尾插快，且无需判断空链表（
h[idx] == nullptr就直接赋值） - 扩容时可直接把旧节点指针挪到新桶，不用重新
new节点，时间复杂度从 O(N) 降到 O(1) 搬指针 - 若后续想升级为红黑树桶（如 C++11
unordered_map在桶过长时转树），结构也兼容
DefaultHashFunc 必须支持模板特化，且 string 版本不能漏掉 const 引用
哈希函数返回 size_t 是硬性要求，但不同 key 类型转换逻辑差异极大。裸 int 可直转，string 必须走 BKDR 或类似算法，否则所有字符串都映射到 0 —— 这会导致所有字符串全挤进第一个桶，查找退化成 O(N)。
常见错误写法：template struct DefaultHashFunc<string> { size_t operator()(string str) { ... } };</string> —— 这里 str 是值传递，每次调用都触发 string 拷贝，性能爆炸且可能因短字符串优化（SSO）导致哈希值不稳定。
- 正确签名必须是
size_t operator()(const string& str) - 乘数推荐 131 或 31（非 256，避免高位信息丢失）
- 浮点类型需先转整型位表示（如
memcpy(&u, &f, sizeof(u))），不能直接强转，否则 1.0 和 1 会得到相同哈希
扩容阈值设为负载因子 > 1 时触发，但 rehash 必须重算每个节点的新桶索引
开放定址法要求负载因子
关键陷阱在于：扩容不是简单把 _tables resize 一下再循环 insert。旧桶中每个节点的 key 必须重新走一遍哈希函数，因为新表大小变了（比如从 23 扩到 47），key % 23 和 key % 47 完全不同。
- 不能复用旧哈希值，必须调用
_hash(key)重算 - 新桶索引 =
_hash(key) % new_capacity，不是old_idx % new_capacity - 建议预存素数表（如 {23, 47, 97, 197, ...}），扩容时取第一个 ≥ 2×current_size 的素数，避免模运算分布不均
最易被忽略的是：哈希函数和桶索引计算必须全程使用同一套取模逻辑。比如 f(x) = (x % N + N) % N 是为了处理负数，但如果哈希函数返回的是无符号 size_t，这层冗余反而引入分支预测失败。一致性比“看起来安全”更重要。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
