当前课程知识点：数据结构 > 第7章 查找 > 7.5 哈希表 > 讲解（上）
本节，我们来学习哈希表，首先，来看问题的提出，我们之前介绍的各种查找表
无论是静态查找表
涉及到的顺序查找
折半查找
还是动态查找表
涉及到的二叉排序树
平衡二叉树
在这些查找表当中
我们查找一个具体的给定关键字
它的平均查找长度，都是跟表长以及你要查找的那个元素
在表中的位置是有关的
那我们能否在单位时间内，找到给定的任意关键字
也就是说
查找任意一个关键字
平均查找长度，是一个与表长n和你要找的那个元素在表中的位置i无关呢
这时候的平均查找长度，是一个常数
换句话说
元素所在的位置，是计算出来的
而不是通过比较，查找出来的
我们这时候所采用的存储结构，就叫哈希表
为了达到在单位时间内，找到给定的任意关键字
我们必须建立关键字与其存储位置之间的映射关系
也就是，从关键字经过某一个计算法则，算出这个关键字
所落在的存放位置
这里的计算法则H
就是哈希函数
H(k)
对关键字算出来一个值，这个值
就是哈希地址
它表示
关键字k存放在哪一个存储位置
我们将全部关键字对应元素所占据的存储空间
叫做哈希表
现在，我们引入一个例子
我们现在以姓名为关键字
存放一个班级内的50个学生
现在，我们来列一个表
我们以姓名为关键字k，采用的哈希函数
是姓名的拼音首字母
我们这里约定是大写的
我们将拼音首字母的ASCII码相加
最后，再对50取余，保证哈希地址它的值域
是0到49
将来，我们用一个
50个元素所占的存储空间，下标是0到49，来存放每一个关键字
现在，大家看到
张磊这个学生
我们用它的拼音首字母ZL
取ASCII码
累加，对50取余，得到了一个16
那我们用16，来作为张磊这个学生，在数组中的下标
大家会发现一个问题
对于姓名不同的学生
比如，这里的赵克斌和张家超
尽管它们的关键字是不同的
但是，它们算出来的哈希地址，却是一样的
不同的关键字
最后要存储在相同的存储单元
这很明显，是不合理的
我们将这种情况，叫做冲突
我们来看冲突的概念
如果k1和k2这两个关键字不相等
但是，它们算出来的哈希地址，却是相等的
那么，这种现象叫做冲突
对于那些映射到相同存储位置的不同关键字
我们将它们称为同义词
比如，刚才的这两个关键字
ZKB和ZJC
它们算出来的哈希地址，是一样的
但关键字不同
那么，这两个关键字就称为同义词
大多数情况下
冲突是不可避免的
我们后面会看到
无论你采取什么样的哈希函数
对于某些给定的关键字
总会产生一些冲突
那你要权衡，你看重的到底是冲突发生少
还是整个哈希表所占据的存储空间少
如果你完全不在乎存储空间
你用一个很大的空间，去存放少量的关键字
这时候，冲突产生的可能性，是非常低的
但是，占用了非常大的空间
所以，我们后面选取哈希函数的时候
总要在冲突少和空间少之间，做一个合理的权衡
现在，我们来介绍哈希表的构造原则
第一个原则
哈希表的容量，一定是大于等于元素个数的
我们将哈希表容量定为m，元素个数定为n
这个是毫无疑问的
无论哈希表多大
最终要保证存放下n个给定的数据元素
哈希地址的值域，要尽可能地连续
我们保证哈希地址算出来的值
尽可能连续，这样才能让存储空间利用率比较高
否则
要占据大量的空间
这大量的空间里面，很多空间是没有存放元素的
那就浪费空间了
另外
哈希地址在值域上，要尽可能地均匀分布
这个的原因也很简单
主要是减少冲突
比如
给定的哈希函数，对于大多数的关键字
它们落在的地址都比较集中
集中在某一块区域
那么，这些关键字产生冲突的可能性，就比较大
反过来
哈希地址在整个值域上，分布比较均匀
这样，产生冲突的可能性就比较低
另外
计算规则H，也就是哈希函数，要尽可能地简单
这样，CPU能在很短的时间内，算出这个地址
现在，我们来看常见的哈希函数，第一种哈希函数
叫直接定址
这时候，我们采用的，实际上是一个线性函数
a*k+b
这里的a、b
都是常数
比如，我们现在要将这6个关键字
存放起来
我们无论是采用什么样的a和b
我们知道，线性函数
它是一条直线
横轴是关键字
纵轴是哈希地址
无论k值是多少
得到的哈希地址，都会不一样
也就是说
采用直接定址法，是不会产生冲突的
但是，缺点也很明显
因为给定的关键字，通常不是连续的
比如，这里1、8、20，直接跳到101
最后跳到1000，关键字不连续
导致最后的值域也不连续
我们会浪费很多的存储空间
比如，我们这里
a取1，b取0
也就是，直接拿关键字作为哈希地址
最大的值是1000
但是，我们总共只有6个关键字
你至少要划分1000个存储单元
浪费空间
第二种，数位分析，假设关键字的某些数值位，它们是有一定分布规律的
这时候，我们直接用这些有规律的位，作为哈希地址，比如，我们这里列举的例子是学号
一般来说
学号当中每一位，都是有一定意义的
比如，最高位代表校区
这个代表学生的级(18级)，这个代表学院的编号，这个代表专业的编号
这个代表班级
假设，班级最多9个班
所以，我们这里只列了1位
最后，是一位学生在这个班级内部的编号
如果我们分析出关键字
它的某些数值位，是有规律的
那么，我们可以利用这些位当中的某些部分，作为关键字
比如，我现在用什么来作为哈希函数呢
我用关键字减去180000000
这样
比如这个学号
它得到的地址，就是702341
当然
你也可以将这个数，再改一下
但不管你怎么改
你都不能在冲突少和空间少这两个方面，达到最佳
因为
无论你怎么减
最后得到的值
实际上，是不能完全利用的
比如，我们现在假设
编号为1的学院
它的第1个专业
第1个班
里面的第1个人
然后，同一个学院
最后那个专业(假设一共有5个专业)
然后，最后那个班(假设有6个班)
6班的最后一个人(假设编号是50)
你只能去连续地占用这段空间(实际上，该段空间占用也不连续)，下一个哈希地址
就是02这个学院了
然后，它的第1个专业
第1个班，1号学生
从这个值到这个值，中间(的存储空间)
实际上没有利用起来
这时候，空间利用率是比较低的
如果我选的位比较少
比如，我只选后5位作为关键字
这时候，冲突的可能性是比较高的
因为，不同的学院
它有编号相同的专业
(编号)相同的班
里面有(编号)相同的人
所以，数位分析这种方法
首先要知道k的每一位数值位的分布情况
另外
冲突少和空间少都不能达到最佳
现在，我们看下一个，平方(取中)函数
在数学上有一个规律，就是一个数的平方
它的中间几位
和该数的每一位都相关
我们可以利用这个特性
比如
54的平方等于这个数
104的平方等于这个数
那54和104
只有两位不同
但是，它们得到的平方
你看，高两位和低两位，都是一样的
中间的几位，和平方的那个数
它的每一位都相关
所以，我们可以拿中间的几位，作为关键字
后面的两个数，也是类似的
这种方式
它的优点是计算比较简单
但缺点跟刚才讲的一样，发生冲突的可能性也比较高
毕竟，你只选了其中的3位
另外
由于中间几位对应的值域
也是不连续的
你也很难保证空间占用比较少
下一种，折叠相加
它是按照k的数值位划分成若干组
比如，1到3位一组
中间3位一组
后面3位一组
然后，把这些组折叠相加
把相加后的值，作为哈希地址
比如，书号(ISBN)
它很长
我们可以几位一分
然后，把它们折叠起来相加，它的优缺点
其实跟平方取中，跟前面的数位分析，也是差不多的
最后一种，除留余数法
这个是用关键字
除上某一个数p，p的取值
是小于等于m的
因为，我们要保证最后算出来的余数，必须要小于等于m-1，这个m
就是哈希表的长度
p通常取最接近m的质数
它的优点是，空间利用率比较高
因为，最后的值域就是0到p-1
只会落在这个范围里面
是一段连续的值
它的缺点也很明显
虽然空间占用少了
但是，产生冲突的可能性，是非常高的
-讲解
-作业
-讨论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 归并排序
--讲解
--作业
-讨论
