拉链法哈希表通过哈希桶数组与单向链表解决冲突：1.定义Node含key/value/next；2.模板类维护vector，初始容量为质数；3.哈希函数为std::hash取模；4.插入时先查重再头插；5.删除需处理头节点与前驱；6.查找线性扫描并保证读安全；7.负载因子超阈值时扩容重哈希。
一、使用拉链法构建哈希桶数组
哈希拉链法通过将冲突的键值对链接到同一哈希桶的单向链表中，避免地址空间浪费并支持动态扩容。核心是为每个桶维护一个链表头指针，并在插入时根据哈希函数定位桶位。
1、定义哈希节点结构体，包含 key、value、next 指针三个成员，key 类型为 std::string，value 类型为 std::any 或模板化类型 T。
2、声明哈希表类模板，内部维护 std::vector<:unique_ptr>> buckets 成员，初始容量设为默认质数（如 101）。
3、实现哈希函数：对 std::string key 调用 std::hash<:string>{}(key) 后对 buckets.size() 取模，得到索引位置。
4、在构造函数中调用 resize 方法初始化所有桶为 nullptr。
二、插入操作中处理键重复与链表遍历
插入时需先检查键是否已存在，若存在则更新值；否则在对应桶链表头部或尾部插入新节点。该步骤确保数据一致性且避免冗余存储。
1、计算 key 对应的 hash_index = hash_func(key) % buckets.size()。
2、从 buckets[hash_index] 开始遍历链表，逐个比对节点的 key 是否等于待插入 key。
3、若发现匹配节点，则执行 value 赋值操作：直接覆盖原 value 字段，不新建节点。
4、若遍历至链表尾部未匹配，则创建新 Node 实例，将其 next 指针指向当前桶头节点，并将 buckets[hash_index] 更新为新节点指针。
三、删除操作中维持链表完整性
删除指定 key 时需定位其所在桶及前驱节点，以正确调整指针关系，防止内存泄漏或悬空指针。特别注意头节点即为目标的情况。
1、计算 hash_index 并获取桶头指针 current = buckets[hash_index].get()。
2、若 current 为空，直接返回 false 表示未找到。
3、若 current->key == key，则执行buckets[hash_index] = std::move(current->next)，完成头删并释放原节点。
4、否则遍历链表，维护 prev 指针，在找到匹配节点后令 prev->next = std::move(current->next)，再销毁 current。
四、查找操作中优化平均时间复杂度
查找过程本质为桶内链表顺序搜索，其性能依赖于负载因子与哈希分布均匀性。可通过缓存最近访问节点或引入跳表结构辅助，但基础实现仅依赖线性扫描。
1、计算 hash_index 并获取桶头指针。
2、从头节点开始逐个比较 key，直至匹配或到达 nullptr。
3、若匹配成功，返回对 value 的 const 引用；若遍历结束仍未匹配，抛出 std::out_of_range 异常或返回 std::nullopt（C++17）。
4、所有查找路径均不修改链表结构，保证线程读操作的无锁安全性（在单写多读前提下）。
五、动态扩容与重哈希触发机制
当插入导致负载因子（元素总数 / 桶数量）超过阈值（如 0.75），需分配更大容量的新桶数组，并将全部现有节点重新散列到新结构中，以维持查询效率。
1、在 insert 成功后检查 load_factor() > threshold，满足则调用 rehash(new_size)，new_size 通常取下一个质数。
2、创建新 buckets_new 向量，大小为 new_size，并全部初始化为 nullptr。
3、遍历原 buckets 中每个非空桶，对其中每个节点调用 hash_func(key) % new_size 得到新索引，并插入至 buckets_new 对应位置链表头部。
4、完成迁移后，执行buckets = std::move(buckets_new)，原桶数组自动析构，所有旧节点被转移。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
