IT评测·应用市场-qidao123.com技术社区

标题: 数据布局：哈希 [打印本页]

---

作者: 金歌    时间: 2025-2-19 16:34
标题: 数据布局：哈希
哈希函数的概念：哈希函数是哈希表（散列表）的核心组件，其作用是将恣意长度的键（Key）映射为固定长度的存储地址，以实现高效的数据存储与检索。以下是哈希函数在数据布局中的关键知识点总结：
一、哈希函数的核心作用

• 快速定位数据
  通过哈希函数计算键的哈希值，直接定位到数组中的存储位置，使得插入、删除和查找操纵的匀称时间复杂度为 O(1）。
  
• 辩论管理
  差别键可能映射到相同地址（哈希辩论），哈希函数的设计需尽可能淘汰辩论概率，并通过辩论办理策略处理实际辩论。
  

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

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

三、哈希辩论的办理方案：

一、开放地址法（Open Addressing）

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

• 线性探测：按次序向后逐个查找空位。
  
  
  
  • 公式：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。
    
  
  
• 二次探测：按平方增量跳跃式探测。
  
  
  
  • 公式：d_i = ±1², ±2², ..., ±k²
    
  • 示例：
    若 H(key)=3 辩论，探测次序为 3+1²=4 → 3-1²=2（若2为空则插入）。
    
  
  
• 伪随机探测：通过伪随机数生成增量序列。
  
  
  
  • 示例：
    若哈希表长度 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]。

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

五.方法对比：

方法优点缺点开放地址法空间紧凑，无需额外布局易产生聚集，删除复杂链地址法无聚集，支持动态插入/删除需额外存储指针，空间开销大再哈希法辩论概率低计算时间增加公共溢出区法实现简单，适合辩论较少场景溢出区过大时效率下降
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4