哈希表的冲突解决策略：链地址法（Separate Chaining） 1. 问题描述 哈希表是一种通过哈希函数将键映射到数组索引的数据结构，但不同键可能映射到同一索引（称为“冲突”）。链地址法是解决冲突的经典策略之一，它的核心思想是将所有映射到同一索引的键值对存储在同一个链表中。 2. 链地址法的基本原理 数据结构设计 ：哈希表的每个槽位（数组元素）不再直接存储单个键值对，而是存储一个链表（或其他容器，如红黑树）的头指针。 插入操作 ： 计算键的哈希值，得到索引 i = hash(key) % array_size 。 若槽位 i 为空，则初始化一个链表，并将新键值对作为头节点。 若槽位 i 非空，则遍历链表： 如果键已存在，更新对应的值（可选设计）； 如果键不存在，将新键值对插入链表末尾（或头部，取决于实现）。 查找操作 ： 计算索引 i ，遍历该槽位的链表，逐个比较键是否匹配。 删除操作 ： 计算索引 i ，遍历链表找到目标键，删除节点并维护链表结构。 3. 时间复杂度分析 理想情况 ：哈希函数分布均匀，每个槽位的链表长度接近常数，插入、查找、删除的平均时间复杂度为 O(1) 。 最坏情况 ：所有键映射到同一槽位，链表长度为 n，时间复杂度退化为 O(n) 。 优化措施 ： 动态扩容（如负载因子超过阈值时，重新哈希）； 链表过长时转换为红黑树（如 Java 的 HashMap）。 4. 具体示例 假设哈希表大小为 5，哈希函数为 hash(key) = key % 5 ，依次插入键 3、8、13： 插入 3：索引 3，链表 A → (3, value)。 插入 8：索引 3，链表 A → (8, value) → (3, value)（头插法）。 插入 13：索引 3，链表 A → (13, value) → (8, value) → (3, value)。 查找键 8：遍历索引 3 的链表，比较两次后找到目标。 5. 链地址法的优缺点 优点 ： 实现简单，无需复杂的探测逻辑； 可容纳的键值对数量超过数组大小（链表可无限扩展）。 缺点 ： 需要额外空间存储链表指针； 缓存不友好（节点内存不连续）。 6. 对比其他冲突解决策略 开放定址法 （如线性探测）： 优点：内存连续，缓存友好。 缺点：删除操作复杂（需标记伪删除），容易产生聚集现象。 链地址法 更适合存储大数据量，且对负载因子容忍度更高。 通过以上步骤，链地址法的核心思想、操作细节和实际应用场景已全面覆盖。