所有图片来自数据结构与算法基础（青岛大学-王卓）的PPT，顺便安利一波，老师的课讲的很好，墙裂推荐！
散列表
一、概念
1、散列表的定义
散列表，是根据关键码值而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
散列函数：H(key) = Addr .
例：
如上，给定散列函数H(key) = key，若给定key = 9，则由散列函数算出地址为 9，也就是9应该存在散列表的9号位置。
2、散列表的相关概念
- 冲突：不同的关键码映射到同一个散列地址。即key1 != key2，但H(key1) == H(key2)。
- 同义词：具有相同散列函数值的关键字。
二、散列函数的构造方法
常用的散列函数：
1、直接定址法
2、除留余数法
p一般取散列表的长度。
3、其他
- 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
- 平方取中法：取关键字平方后的中间几位作为散列地址。
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 随机数法：选择一随机函数，取关键字作为随机函数的种子生成随机值作为散列地址，通常用于关键字长度不同的场合。
三、处理冲突的方法
1、开放定址法（开地址法）
基本思想：有冲突时就去找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存进去。
2、链地址法（拉链法）
基本思想：相同散列地址的记录链成一个单链表，m个散列地址就是m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
例子：
链地址法建立散列表的步骤：
四、散列表的查找
注：ASL，是查找算法的查找成功时的平均查找长度的缩写，是为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。