哈希表是一种基于哈希函数实现的高效数据结构，用于实现“键-值”对的快速插入、查找和删除

哈希表是一种基于哈希函数实现的高效数据结构，用于实现“键-值”对的快速插入、查找和删除。其核心思想是通过哈希函数将关键字映射到哈希表的某个地址上，从而实现O(1)平均时间复杂度的操作。然而，由于不同关键字可能映射到同一地址，产生哈希冲突，因此需要采用合适的冲突解决策略。

1. 核心内容解析

哈希函数：取余法（MOD 11）

• 计算方式：Hash(key) = key MOD 表长
• 示例：若表长为11，则Hash(47) = 47 MOD 11 = 3，表示关键字47应存入地址3。
• 优点：简单高效；缺点：对表长选择敏感，需选用质数以减少冲突。

冲突解决方法一：线性探测法（开放定址法）

• 原理：当发生冲突时（目标地址已被占用），按顺序探测下一个地址：
  • 探测序列：(Hash(key) + i) MOD 表长，其中 i = 1, 2, 3, …
• 示例：
  • Hash(12) = 1，但地址1被34占用；
  • 探测地址2（被13占用）→ 地址3（被47占用）→ 最终于地址4插入12。
• 缺陷：
  1. 聚集现象（Primary Clustering）：连续冲突导致元素在局部区域堆积，显著增加后续插入与查找的探测次数。
  2. 溢出处理困难：当表满时无法继续插入，需额外设计溢出区或动态扩容机制。

查找过程分析

• 查找成功：沿探测序列找到关键字等于key的记录。
• 查找失败：沿探测序列未找到key，并遇到空单元（说明无需再查，该key不存在）。
• 溢出情况下的失败：查遍全表仍未找到key且表已满（适用于无空单元的情况）。

冲突解决方法二：链地址法（拉链法）

• 原理：每个哈希地址对应一个链表，所有映射到同一地址的关键字链接成单链表。
• 示例：若47、12、34都映射到地址3，则它们在同一链表中依次存储。
• 优点：
  • 避免聚集现象；
  • 动态扩展性强，适合频繁插入/删除场景；
  • 容易处理大量冲突。
• 缺点：
  • 需额外空间存储指针；
  • 缓存局部性差，访问效率略低于理想情况下的线性探测。

对比总结

应用建议

• 若关键字分布均匀、表大小固定，可使用线性探测法；
• 若冲突较多或数据量动态变化大，推荐使用链地址法；
• 实际应用中（如Java的HashMap），常结合链表与红黑树优化查找性能（当链表过长时转为树结构）。
• 选择合适的哈希表长度是减少冲突、提高查找效率的关键。理想情况下，哈希表的长度应满足以下条件：

1.为什么通常选择质数作为表长？

使用质数（素数）作为哈希表长度可以显著减少关键字聚集和冲突的概率，原因如下：

• 取余运算的均匀性：哈希函数常采用“取余法”（Hash(key) = key MOD m），当m为质数时，key 对 m 取模的结果更可能均匀分布在 0 到 m-1 的范围内。
• 避免周期性模式冲突：
  • 若表长 m 是合数（如 12），而关键字多为某个因子的倍数（如 3 的倍数），则这些 key % 12 的结果会集中在某些地址上（如 0, 3, 6, 9），造成严重冲突。
  • 而质数没有非平凡因子，能打破这种周期性分布，使映射更散列。

✅ 示例对比：

• 设关键字集合为 {3, 6, 9, 12, 15, 18}，若表长 m=12（合数）：
  • 所有 key % 12 的结果都在 {0, 3, 6, 9} 中 → 仅占4个地址，严重冲突。
• 若表长 m=11（质数）：
  • 结果分布更广：3%11=3, 6%11=6, 9%11=9, 12%11=1, 15%11=4, 18%11=7 → 分布在不同位置，冲突减少。

2.如何选择合适的哈希表长度？

原则一：表长应略大于预计元素个数

• 避免高负载因子（α = 元素数 / 表长）
  • 线性探测法建议 α < 0.7
  • 链地址法可容忍 α ≤ 1，但过大会降低性能

原则二：选择最接近 n 的最小质数作为表长

• 如预计存储 100 个元素，可选 101（质数）作为表长。

原则三：避免使用 2 的幂次（除非配合特殊哈希函数）

• 虽然key % (2^n)可用位运算优化（如key & (2^n -1)），但如果原始哈希值低位规律性强，会导致分布不均。
• 若必须用 2 的幂，应先对 key 进行扰动处理（如 Java HashMap 中的扰动函数）。

实际应用中的策略

💡 例如 Java 的HashMap默认初始容量为 16（2^4），通过扰动函数打乱高位，使得即使使用 2 的幂也能实现良好散列。