目录
一、散列函数
1、散列存储
选取某个函数，依该函数按关键字计算元素的存储位置
Loc(i)=H(keyi)
冲突：不同的关键码映射到同一个散列地址
key1≠key2,但是H(key1) = H(key2)
在散列查找方法中，冲突是不可能避免的，只能尽可能。
二、散列函数的构造方法
1、构造要求
要求一: n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。
要求二:无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。
2、常用的方法：直接定址法、除留余数法
3、直接定址法：以关键码key的某个线性函数值为散列地址，如下图所示：
4、除留余数法,如下图所示：（下图的mod表示求余，注意p和m的取值）
三、处理冲突的方法
1、开放定址法（开地址法）
基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。如下图所示：
?2、线性探测法
3、 二次探测法
4、 伪随机探测法
四、链地址法（拉链法）
1、基本思想:相同散列地址的记录链成一单链表，m个散列地址就设m个单链表，然后用一 个数组将m个单链表的表头指针存储起来，形成一个动态的结构。如下图所示的典例：
2、链地址法建立散列表步骤
Step1: 取数据元素的关键字key,计算其散列函数值(地址)。 若该地址对应的链表为空，则将该元素插入此链表;否则执行Step2解决冲突。
●Step2:根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。
3、链地址法的优点:
●非同义词不会冲突，无“聚集"现象。
●链表上结点空间动态申请，更适合于表长不确定的情况。
五、散列表的结论
1、散列表技术具有很好的平均性能，优于一些传统的技术。
2、链地址法优于开地址法。
3、除留余数法作散列函数优于其它类型函数。
