当前课程知识点：数据结构 > 第7章 查找 > 7.5 哈希表 > 讲解（下）
既然无论采用什么样的哈希函数，冲突都是不可避免的
那我们就得想办法，来解决冲突
现在，我们来介绍第一种处理冲突的方法
开放定址法
冲突发生的时候
我们逐一试探下一位置
直到找出可用的位置
也就是没有存放关键字的位置
这时候，我们试探的下一个哈希地址是多少呢
是当前算出来的哈希地址
加上一个数，再对p取余
因为无论怎么样
我们要保证
值域落在0到p-1的范围内
这里的di
实际上是可变的
如果di采用1、2、3这样的序列
这时候，冲突处理方法叫做线性探测法
就是逐个试探下一个位置
直到找到可用位置
采用线性探测
是容易产生二次聚集的，所谓二次聚集，就是原来不是同义词的关键字
但它们的地址却冲突
我们通过一个例子来说明，我们现在将这11个关键字，存放到一个长度为11的哈希表当中
我们采用的p
也是11，跟m相同，采用的哈希函数就是k对11取余
来作为哈希地址
最终的哈希表是这样的，很简单
第1个，25对11取余，得到的余数是3
3里面是没有存放东西的
所以，25直接放到这里，第2个关键字16
它对11取余，得到的余数是5
那么，直接放到下标为5的位置
第3个关键字38
它对11取余，得到的余数也是5
这时候，下标为5的位置，已经被16占据了
所以，我们采用线性探测(解决冲突)，di取第1个值
那么
再对11取余，会得到6
38就放到6的位置
16和38，它们的关键字值不一样
但是，计算出来的哈希地址都是5
所以，16和38互称为同义词
这个刚才我们已经说过了，下一个关键字
47
它对11取余，得到的余数
是3，3已经被25占据了
所以，di取1，下一个值(余数)是4
可以，放到这里
然后，79
它对11取余，余数是2，没问题(没有被占用)，放到下标为2的位置
82对11取余，余数也是5
那么，5这个位置，已经被16占据了
di取1，算出来是6
被38占据了
然后，di取下一个值
没问题，放到下标为7的位置
再下一个关键字
51对11取余，得到的余数是7
余数为7
但是，下标为7的位置，已经被82占据了
于是，大家发现一个现象，就是82和51这两个关键字
它们的哈希地址不一样
但是却产生了冲突
也就是说，它们不是同义词
但冲突了
这种现象，就叫做二次聚集
后面的关键字存放，我就不说了
红色的
都是表示算出来的哈希地址
已经被别的元素占据了
那要试探下一个位置，线性探测
容易产生二次聚集
我们可以换一种探测策略
比如，我们采用二次探测
只不过，它选的这个数的序列不一样而已
它选1、-1、4、-4
一会往后，一会往前，这样去探测
我们还可以采用伪随机探测
就是用计算机产生下一个随机数
通常来说
计算机产生的随机数，都是伪随机数
我们产生下一个随机数
作为di的值，就是让探测的前后方向(和距离)尽量地随机一点
现在，我们来看第二种冲突处理方式
再哈希法，所谓再哈希法
就是当冲突发生的时候
我们换一个哈希函数
如果还冲突，再换一个哈希函数
我们不断地选取下一个哈希函数
直到算出来的哈希地址是可用的
当然，这里哈希函数的选取，就比较自由了
我们就不说了
最后一种冲突处理的方式
叫做链地址法
实际上，这种方式并没有真正地处理冲突
它只是把那些同义词放到了一起
具体来说
我们为每个哈希地址，建立一个单链表
我们建立的是单链表，所有哈希地址相同的关键字
放到同一个链表当中
比如，一样地，将11个关键字，放在一个容量为11的数组里面
现在，那些哈希地址相同的关键字
比如37和92
它们对11的余数
都是4
我们就把它们放到以下标为4开头的同一个单链表当中
将来，我们去找的时候
比如给你92
你对11取余
算出余数为4
你就去找这个链表
总能找到92
现在，我们来分析一下哈希表的查找性能
关键字比较的次数，取决于以下几个方面
第一
你所选用的哈希函数，第二，是你所采用的冲突处理策略
第三，是负载因子
负载因子很简单
就是你要存放的元素个数，除上哈希表的容量，容量越大
负载因子就越低
容量越小
也就是，哈希表将来越来越满
这时候，冲突的可能性是比较高的
我们现在，还是通过刚才几个关键字
我们看一下
它的平均查找长度
比如，我们现在去找25
25对11取余，余数是3，而下标为3的位置放的就是25
这时候，我们只经历了1次比较，就找到了25
我们去找关键字82
它对11取余，得到的余数是5
但是，我们去找下标为5的位置，发现是16，并不是82
假设，我们采用的是线性探测(来解决冲突)
我们找下一个位置
是38，依然不是82
再找下一个位置，才找到82
这时候，你经历了3次比较，才找到82
我们最终将找所有元素的比较次数累加，等概率情况下，除以一个表长
最终，我们就得到了平均查找长度
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
