数据结构：哈希

哈希函数的概念：哈希函数是哈希表（散列表）的核心组件，其作用是将任意长度的键（Key）映射为固定长度的存储地址，以实现高效的数据存储与检索。以下是哈希函数在数据结构中的关键知识点总结：

一、哈希函数的核心作用

1. 快速定位数据
   通过哈希函数计算键的哈希值，直接定位到数组中的存储位置，使得插入、删除和查找操作的平均时间复杂度为 O(1）。
2. 冲突管理
   不同键可能映射到相同地址（哈希冲突），哈希函数的设计需尽可能减少冲突概率，并通过冲突解决策略处理实际冲突。

二、常见哈希函数构造方法

1. 直接定址法
   • 公式：H(key) = a*key + b
   • 特点：适用于键分布连续的场景（如年龄存储），无冲突但空间利用率低。
   • 示例：年龄为键时，直接以年龄作为数组下标。
2. 除留余数法
   • 公式：H(key) = key % p（p为不大于表长的质数）
   • 特点：简单高效，需选择合适质数以减少冲突。
   • 示例：当表长m=10，选择p=7，键12的哈希值为12%7=5。
3. 平方取中法
   • 步骤：对关键字平方后取中间几位作为哈希值。
   • 适用场景：关键字分布范围大且中间位数较均匀。
4. 折叠法
   • 方法：将关键字分割为多段后叠加求和（如移位叠加或间界叠加）。
   • 适用场景：长关键字且位数分布均匀。
5. 随机数法
   • 公式：H(key) = random(key)
   • 特点：适用于非数值型键，需保证随机性以减少冲突。

三、哈希冲突的解决方案：

一、开放地址法（Open Addressing）

核心思想：当发生冲突时，按规则探测哈希表中的下一个空槽位。
探测方式：

1. 线性探测：按顺序向后逐个查找空位。
   • 公式：H_i = (H(key) + d_i) % m，其中 d_i = 1, 2, 3, ..., m-1
   • 示例：
     哈希表长度 m=11，哈希函数 H(key)=key%11。
     插入序列 {12, 67, 56, 16, 25, 37} 时，37%11=1，但位置1已被25占用。
     线性探测后，依次检查位置2（空），插入37到位置2。
2. 二次探测：按平方增量跳跃式探测。
   • 公式：d_i = ±1², ±2², ..., ±k²
   • 示例：
     若 H(key)=3 冲突，探测顺序为 3+1²=4 → 3-1²=2（若2为空则插入）。
3. 伪随机探测：通过伪随机数生成增量序列。
   • 示例：
     若哈希表长度 m=11，随机序列为 2,5,9,...，冲突时计算 (3+2)%11=5，若仍冲突则继续 (3+5)%11=8。

二、链地址法（Separate Chaining）

核心思想：将哈希地址相同的元素组成链表，头指针存储在哈希表中。
示例：
哈希表长度13，哈希函数 H(key)=key%13，关键字序列 {32,40,36,53,16,46,71,27,42,24,49,64}。

• 处理结果：
  • 地址0：→32→27
  • 地址1：→40→53→16→42
  • 地址10：→49→64
    平均查找长度 (7*1 + 4*2 + 1*3)/12 ≈1.5。

三、再哈希法（Double Hashing）

核心思想：冲突时使用第二个哈希函数重新计算地址。
示例：

• 主哈希函数 H1(key)=key%13，冲突时使用 H2(key)=7-(key%7)。
  插入 key=37 时，若 H1(37)=11 冲突，则计算 H2(37)=7-2=5，新地址 (11+5)%13=3（若空则插入）。

---

四、公共溢出区法（Overflow Area）

核心思想：单独开辟一个区域存储冲突元素。
示例：
哈希表分为主表 HashTable[0..m-1] 和溢出表 OverTable[0..v]。

• 查找时先查主表，未找到则遍历溢出区。

五.方法对比：

方法	优点	缺点
开放地址法	空间紧凑，无需额外结构	易产生聚集，删除复杂
链地址法	无聚集，支持动态插入/删除	需额外存储指针，空间开销大
再哈希法	冲突概率低	计算时间增加
公共溢出区法	实现简单，适合冲突较少场景	溢出区过大时效率下降