散列表的基本概念
散列存储
散列方法（杂凑法）
散列函数（杂凑函数）：散列方法中使用的转换函数
散列表（咋抽表）：按上诉思想构造的表
冲突：不同的关键码映射到同一个散列地址
同义词：具有相同函数值的多个关键字就互称为同义词
（如上，23和9计算出来的散列地址一样，出现了冲突，并且其互称为同义词）
散列函数的构造
构造散列函数考虑的因素
构造散列函数的要求
散列函数的构造方法：直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法
1、直接定址法
（线性的函数值是必然没有重复冲突的，除非关键码相同）
2、除留余数法
散列函数冲突情况的处理
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
- 二次探测法
用二次探测法处理冲突问题的示例：（增量不行+1，再不行再-1，再不行+4，再不行-4…）
- 伪随机探测法
方法和上两种方法类似，只不过产生出来的增量为一个伪随机数，这样就没有了规律可言，就不举例子了。
2、链地址法（拉链法）
基本思想：相同的散列地址的记录链成一个单链表
（如上所示便是散列表的链式存储结构）
链地址法构造散列表的步骤
链地址法的优点：
- 非同义词不会冲突，无“聚集”现象
- 链表上结点空间动态申请，更适合于表长不确定的情况
散列表的性能分析
- 开发定址法与拉链法的比较
- 开放定址法
- 拉链法
- 无序表查找的ASL = （n+1）/2 = 6.5
- 有序表折半查找ASL = log2(n+1) - 1 = 2.多
（可见散列表的查找效率还是不错的）
影响散列表的因素
散列的平均查找长度ASL
- 结论：
- 散列表技术具有很好的平均性能，优于一些传统的技术
- 链地址法优于开地址法
- 除留余数法作散列函数优于其他类型函数
