背景：之前介绍了《软考路之线性表》，在顺序表和树表中查找数据元素要进行一系列的键值比较过程。为了使数据元素的存储位置和键值之间建立某种联系，以减少比较次数，现在介绍用散列表技术实现动态查找表。
一、散列表
数据元素的键值和存储位置之间建立的对应关系H称为散列函数，用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为散列表（Hash Table），这一映射过程称为散列。
如果选定了某种散列函数H及相应的散列表L，则对每个数据元素X，函数值H（X.key）就是X在散列表L中的存储位置，这个存储位置也称为散列地址。
散列文件是一种计算寻址文件。
二、常用散列法
1、数字分析法
又称为数字选择法，其方法是收集所有可能出现的键值，排列在一起，对键值的每一位进行分析，选择分布较均匀的若干位组成散列地址。
所取的位数取决与散列表的表长，见表长为100，则取2位即可。
假定已知可能出现的所有键值如下：
对所有的键值分析不能看出，左起前三位都是“7 1 2”，第五位只能取1、4，第七位只能取6、7、8、，故这五位都不可取。剩下的第4、6、8、9位都是分布比较均匀的，可考虑将它们或它们中的几位组织起来作为散列地址。
2、除数余数法
是一种简单有效且常用的构造方法，其方法是选择一个不大于散列表长n的正整数p,以键值除以p所得的余数作为散列地址，即
H（key）=key mod p (p<=n)
mod是取余数运算，在C语言中，这一运算符是“%”。值得注意的是这一方法的关键在于p的选取。
如果选p为偶数，则所得的散列函数总是将奇数键值映射成奇数地址，偶数键值映射为偶数地址，因而增加了冲突的机会。通常选p为小于散列表长度n的素数。
3、平均取中法
以键值平方的中间几位作为散列地址。
通常在选定散列函数时不一定能知道键值的分布情况。取其中哪几位也不一定合适，而一个数平方的中间几位与这个数的每一位都有关，所得散列地址比较均匀。
4、基数转换法
将键值看成另一种进制的数再转换成原来进制的数，然后选其中几位作为散列地址。例：
对于十进制键值443730，先把它看成是十三进制的数再转换为十进制数：
然后，根据散列表的长度从中选取几位作为散列地址。
三、散列表的实现
1、线性探测法
对于任何键值key，设H（key）= d ，设散列表的容量为m ，则线性探测法生成的后继散列地址序列为：
d+1,d+2,d+3,...,m-1,0,1,...,d-1
例：表长为13，其散列函数为H（key）= key mod 13,在下列的散列表中插入29
从上面可以看出，用线性探测法生成后继散列地址计算简单，但由于探测的是一个连续的地址序列，这也引出新的问题。表中30和29本来不是同义词，但是发生了冲突，这种非同义词之间对同一个散列地址的争夺现象称为“堆积”。为了减少堆积的机会，应设法使后继散列地址尽量均匀地分散在整个散列表中。
2、二分探测法
基本思想：生成的后继散列地址不是连续的，而是跳跃的，以便为后继数据元素留下空间从而减少堆积。
键值为key的散列地址序列为：
d(0)=H(key)
d(i)=(d(0)+i) mod m
m为散列表的表长，i=1^2,-1^2,2^2,-2^2,...±k^2(k≤m/2)
二次探测法的缺点是不易探测到整个散列表的所有空间，也就是说，上述后继散列地址可能难以包括散列表的所有存储位置。
3、链地址法
是对每一个同义词都建一个单链表来解决冲突。
设选定的散列函数为H，H的值域（即散列地址的范围）为0~（n-1）。设置一个指针向量“Pointer HP[n]”,其中的每个指针HP[i]指向一个单链表，该单链表用于存储所有散列地址为i的数据元素。
每一个这样的单链表称为一个同义词子表。例：
4、多重散列法
此法要求设立多个散列函数H（i）,i=1,...,k。当给定值key与散列表中的某个键值是相对于某个散列函数H（i）的同义词而发生冲突时，继续计算这个给定值key在下一个散列函数H（i+1）下的散列地址，直到不再产生冲突为止。
这种方法的优点时不易产生“堆积”，缺点是计算量较大。
5、公共溢出区法
按照这种方法，散列表由两个一维数组组成。一个称为基本表，它实际上就是上面所说的散列表，另一个称为溢出表。插入首先在基本表上进行，假如发生冲突，则将同义词存入溢出表，这样，基本表不可能发生“堆积”。
四、学习心得
本来很简单的东西，自己从心里恐惧，就会造成知识没学到，心情变得糟糕，为了考试不得不再次复习此处的内容，再次感到很难，恐惧.....于是乎，掉入了恶性循环中，不可自拔。
每每遇到一个新的事物。首先我们做的就是从心里面认为它很简单，这样，让自己有了信心，才有动力去解决它，自此，一位“学霸”就诞生了，学什么会什么，会什么精通什么，心情变好了，人自然就变漂亮了，变帅了，嘿嘿......
自信，是每个人不可缺少的东西。是成功的第一秘诀。