目录
1、散列表的基本概念
在前面介绍的线性表和树表的查找中，记录在表中的位置和记录的关键字之间不存在确定关系，因此，在这些表中查找记录时需进行一些列的关键字比较。这类查找方法建立在“比较”的基础上，查找的效率取决于比较的次数。
散列函数：一个把查找表中的关键字映射称该关键字对应的地址的函数，记为Hash(key) = Addr(这里的地址可以是数组下标、索引或内存地址等)。
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。
散列表：根据关键字而直接进行访问的数据结构。也就是说 ，散列表建立了关键字和存储地址之间的一种直接映射关系。
理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关。
2、散列函数的构造方法
在构造散列函数时，必须注意以下几点
1）散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
2）散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
3）散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。
3、常用的散列函数
3.1、直接定址法
直接取关键字的某个线性函数值为散列地址，散列函数为
式中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
3.2、除留余数法
这是一种最简单、最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用一下公式把关键字转换成散列地址。散列函数为
除留余数法的关键是选好p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可能性。
3.3、数字分析法
设关键字是r进制数（如十进制数），而r个数码在各位上出现的概率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
3.4、平方取中法
顾名思义，这种方法取关键字的平方值的中间几位作为散列地址。具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
在不同的情况下，不同的散列函数具有不同的性能，因此不能笼统地说哪种散列序列函数最好。在实际选择中，采用何种构造散列函数的方法取决于关键字集合的情况，但目标是为了尽量降低发生冲突的可能性。
4、处理冲突的办法
应该注意到，任何设计出来的散列函数都不可能绝对地避免冲突。为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个“空”的Hash地址。用Hi表示处理冲突中第i次探测得到的散列地址，假设得到的另一个散列地址H1仍然发生冲突，只得继续求下一个地址H2，以此类推，直到Hk不发生冲突为止，则Hk为关键字在表中的地址。
4.1、开放定址法
所谓开放定址法，是指可存放新表项的空闲地址既可向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为
式中，H(key)为散列函数：i=0,1,2,...,k（k≤m-1）；m表示散列表表长；di为增量序列。
取定某一增量序列后，对应的处理方法就是确定的。通常有以下4种取法：
1）线性探测法。当di = 0,1,2,...,m-1时，称为线性探测法，这种方法的特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
线性探测法可能使第i个散列地址的同义词存入第i+1个散列地址，这样本应存入第i+1个散列地址的元素就争夺第i+2个散列地址的元素的地址......从而造成大量元素在相邻的散列地址上“聚集”（或堆积）起来，大大降低了查找效率。
2）平方探测法。当di=
时，称为平方探测法，其中k≤m/2，散列表长度m必须是一个可以表示为4k+3的素数（如果散列表长度不是4k+3的素数就有可能有地址探测不到）
平方探测法是一种较好的处理冲突的方法，可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
3）再散列法。当di=Hash2(key)时，称为再散列法，又称双散列法。需要使用两个散列函数，当通过第一个散列函数H(key)得到的地址发生冲突时，则利用第二个散列函数Hash2(key)计算该关键字的地址增量。它的具体散列函数形式如下：
初始探测位置H0=H(key)%m。i是冲突的次数，初始为0.在再散列法中，最多经过m-1次探测就会遍历表中所有的位置，回到H0位置。
4）伪随机序列法。当di = 伪随机数序列时，称为伪随机序列法。
注意：在开放地址的情形下，不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。
4.2、拉链法（链接法，chaining）
显然，对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找、插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况
关键字序列为{19,14,23,01,68,20,84,27,55,11,10,59}，散列函数H(key) = key%13，用拉链法处理冲突，建立的表如上图所示。
5、散列表查找
散列表的查找过程与构造散列表的过程基本一直。对于一个给定的关键字key，根据散列函数可以计算出其散列地址，执行步骤如下：
初始化：Addr = Hash(key)；
① 检测查找表中地址为Addr的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它与key的值，若相等，则返回查找成功标志，否则执行步骤②
② 用给定的处理冲突方法计算“下一个散列地址”，并把Addr置为此地址，转入步骤①
例如，关键字序列{19,14,23,01,68,20,84,27,55,11,10,79}按散列函数H(key) = key%13和现象探索处理冲突构造所得的散列表L如下所示。
给定值84的查找过程为：首先求得散列地址H(84)=6，因L[6]不空且L[6]≠84，则找第一次冲突处理后的地址H1=(6+1)%16=7,而L[7]不空且L[7]≠84，则找第二次冲突处理后的地址H2=(6+2)%16=8，L[8]不为空且L[8]=84,查找成功，返回记录在表中的序号8。
给定值38的查找过程为：先求散列地址H(38)=12，L[12]不为空且L[12]≠38，则找下一地址H1=(12+1)%16=13,由于L[13]是空记录，故表中不存在关键字为38的记录。
查找个关键字的比较次数如下图所示：
平均查找长度ASL=(1*6+3*3+4+9)/12 = 2.5
对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同。
6、散列表的查找过程的性能分析
从散列表的查找过程可见：
（1）虽然散列表在关键字与记录的存储位置之间发生了直接映射，但由于“冲突”的产生。使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量
（2）散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。
填装因子。散列表的填装因子一般记为α，定义为一个表的装满程度，即
散列表的平均查找长度依赖于散列表的填装因子α，而不是直接依赖于n或m。直观地看，α越大，表示填装的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。