【数据结构和算法】散列表的查找算法（开放地址法，链地址法）

散列表的基本概念

• 散列存储
  

• 散列方法（杂凑法）
  

• 散列函数（杂凑函数）：散列方法中使用的转换函数

• 散列表（咋抽表）：按上诉思想构造的表
  

• 冲突：不同的关键码映射到同一个散列地址

• 同义词：具有相同函数值的多个关键字就互称为同义词
  
  （如上，23和9计算出来的散列地址一样，出现了冲突，并且其互称为同义词）

散列函数的构造

• 构造散列函数考虑的因素
  
• 构造散列函数的要求
  
• 散列函数的构造方法：直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法

1、直接定址法

（线性的函数值是必然没有重复冲突的，除非关键码相同）

2、除留余数法

散列函数冲突情况的处理

1、开放地址法（开地址法）

• 基本思想
  
• 增量序列的常用方法
  

1. 线性探测法
   

• 用线性探测法处理冲突问题的示例：（增量不行+1，再不行再+1）
  
  （散列表下面的数据表示为运算的次数，例如关键吗3的底下数字是4，表示如果要找到关键码3，需要进行4次的寻找）

• 平均查找长度的ASL的计算

如上所示，每一个关键码被找到的概率都是1/9，要寻找这些关键码的总次数为底下数字全部相加，sum = （1+2+1+1+1+4+1+2+2），所以ASL = sum/9 = （1+2+1+1+1+4+1+2+2）/9 = 1.67

2. 二次探测法

• 用二次探测法处理冲突问题的示例：（增量不行+1，再不行再-1，再不行+4，再不行-4…）
  

3. 伪随机探测法

方法和上两种方法类似，只不过产生出来的增量为一个伪随机数，这样就没有了规律可言，就不举例子了。

2、链地址法（拉链法）

• 基本思想：相同的散列地址的记录链成一个单链表
  
  （如上所示便是散列表的链式存储结构）

• 链地址法构造散列表的步骤
  

• 链地址法的优点：

1. 非同义词不会冲突，无“聚集”现象
2. 链表上结点空间动态申请，更适合于表长不确定的情况

散列表的性能分析

• 开发定址法与拉链法的比较

1. 开放定址法
   
2. 拉链法
   
3. 无序表查找的ASL = （n+1）/2 = 6.5
4. 有序表折半查找ASL = log2(n+1) - 1 = 2.多

（可见散列表的查找效率还是不错的）

• 影响散列表的因素
  
• 散列的平均查找长度ASL
  
• 结论：

1. 散列表技术具有很好的平均性能，优于一些传统的技术
2. 链地址法优于开地址法
3. 除留余数法作散列函数优于其他类型函数

参考链接：https://space.bilibili.com/40323036