哈希表的原理与冲突解决 描述 哈希表（Hash Table）是一种基于键（Key）直接访问内存存储位置的数据结构，它通过哈希函数将键映射到数组的特定索引，从而实现平均时间复杂度为 O(1) 的插入、删除和查找操作。核心挑战是 哈希冲突 （不同键映射到同一索引），需通过策略解决。 1. 哈希函数的作用 哈希函数将任意大小的键（如字符串、对象）转换为固定范围的整数（即数组索引）。理想哈希函数需满足： 计算速度快 分布均匀（减少冲突） 例如，对整数键取模： index = key % table_size 。 2. 哈希冲突的成因 若两个键经哈希函数计算后得到相同索引，则发生冲突。例如： 表大小为 10，键 15 和 25 通过 key % 10 均映射到索引 5。 冲突不可避免（鸽巢原理），因此需解决策略。 3. 冲突解决策略：链地址法 原理 ：每个数组索引对应一个链表（或其它数据结构），所有映射到同一索引的键值对存储在同一链表中。 操作示例 ： 插入键 15（索引 5）：在索引 5 的链表末尾添加节点。 插入键 25（索引 5）：继续添加到同一链表。 查找键 25：计算索引 5，遍历链表比较键值。 优点 ：简单有效，链表长度较小时性能接近 O(1)。 缺点 ：链表过长时退化为 O(n)，需动态扩容优化。 4. 冲突解决策略：开放地址法 原理 ：所有元素直接存储在数组中，冲突时按探测序列寻找下一个空槽。 线性探测 ：若索引 i 被占用，尝试 i+1, i+2... 直到空槽。 示例：插入键 25（索引 5 被占）→ 尝试索引 6。 缺点：易产生聚集（连续占用槽），降低效率。 二次探测 ：避免聚集，按平方序列探测（如 i+1², i+2²）。 双重哈希 ：使用第二个哈希函数计算步长，进一步分散分布。 5. 性能优化与扩容 负载因子 （Load Factor）：元素数量 / 表大小。当负载因子超过阈值（如 0.75），需扩容： 创建新数组（通常双倍大小）。 重新哈希所有键到新数组。 动态扩容 ：避免频繁冲突，保证平均时间复杂度接近 O(1)。 总结 哈希表的核心在于哈希函数设计（均匀分布）与冲突解决策略（链地址法或开放地址法）。结合动态扩容，可高效支持快速数据操作。实际应用中，链地址法更常见因易于实现，而开放地址法在内存紧凑场景有优势。