|
|
|
对于前面讨论的几种查找方法，由于记录的存储位置与其关键码之间不存在确定的关系，所以查找时都要通过一系列对关键字的比较，才能确定被查记录在表中的位置，即这类查找方法都建立在对关键字进行比较的基础之上。理想的情况是依据记录的关键码直接得到对应的存储位置，即要求记录的关键码与其存储位置之间存在一一对应关系，通过这个关系，能很快地由关键码找到记录。哈希表就是按这种思想组织的查找表。
|
|
|
|
|
|
根据设定的哈希函数Hash（key）和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
|
|
|
|
在构造哈希表时，是以记录的关键字为自变量计算一个函数（称为哈希函数）来得到该记录的存储地址并存入元素，因此在哈希表中进行查找操作时，必须计算同一个哈希函数，首先得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
|
|
|
|
对于某个哈希函数Hash和两个关键字K1和K2，如果K1≠K2而Hash（K1）=Hash（K2），则称为出现了冲突，对该哈希函数来说，K1和K2则称为同义词。
|
|
|
|
一般情况下，只能尽可能地减少冲突而不能完全避免，所以在建造哈希表时不仅要设定一个“好”的哈希函数，而且要设定一种处理冲突的方法。
|
|
|
|
釆用哈希法主要考虑的两个问题是哈希函数的构造和冲突的解决。
|
|
|
|
|
|
解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。常见的处理冲突的方法有开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区法等，在处理冲突的过程中，可能得到一个地址序列，记为Hi（i=1，2，…，k）。下面简要介绍开放定址法和链地址法。
|
|
|
|
|
|
Hi=（Hash（key）+di）%mi=l，2，…，k（k≤m-1）
|
|
|
|
其中，Hash（key）为哈希函数；m为哈希表的表长；di为增量序列。
|
|
|
|
|
|
.di=1，2，3，…，m-1，称为线性探测再散列。
|
|
|
|
.di=12，-12，22，-22，32，…，±k2（k≤m/2），称为二次探测再散列。
|
|
|
|
|
|
最简单的产生探测序列的方法是进行线性探测。也就是发生冲突时，顺序地到存储区的下一个单元进行探测。
|
|
|
|
例如，某记录的关键字为key，哈希函数值H（key）=j。若在哈希地址j发生了冲突（即此位置已存放了其他元素），则对哈希地址j+1进行探测，若仍然有冲突，再对地址j+2进行探测，以此类推，直到将元素存入哈希表。
|
|
|
|
|
|
|
|
|
|
（b）根据哈希函数，计算出关键码47的哈希地址为3，在该单元处无冲突，因此插入47。此后关键码34和19需要插入的哈希地址1和8处也没有冲突，因此在对应位置直接插入后如下所示。
|
|
|
|
|
|
（c）将关键码12存入哈希地址为1的单元时发生冲突，探测下一个单元（即哈希地址为2的单元），不再冲突，因此将12存入哈希地址为2的单元后如下所示。
|
|
|
|
|
|
（d）将关键码52存入哈希地址为8的单元时发生冲突，探测下一个单元（即哈希地址为9的单元），不再冲突，因此将52存入哈希地址为9的单元后如下所示。
|
|
|
|
|
|
（e）在哈希地址为5的单元存入关键码38，没有冲突；在哈希地址为0的单元中存入关键码33，没有冲突。因此将38和33先后存入哈希地址为5和0的单元后如下所示。
|
|
|
|
|
|
（f）在哈希地址为2的单元存入关键码57时发生冲突，探测下一个单元（即哈希地址为3的单元），仍然冲突，再探测哈希地址为4的单元，不再冲突，因此将57存入哈希地址为4的单元后如下所示。
|
|
|
|
|
|
（g）在哈希地址为8的单元存入关键码63时发生冲突，探测下一个单元（即哈希地址为9的单元），仍然冲突，再探测哈希地址为10的单元，不再冲突，因此将63存入哈希地址为10的单元后如下所示。
|
|
|
|
|
|
（h）在哈希地址为10的单元存入关键码21时发生冲突，用线性探测法解决冲突，算出哈希地址11，不再冲突，因此将21存入哈希地址为11的单元后如下所示，此时得到最终的哈希表。
|
|
|
|
|
|
线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“聚集”起来的现象，大大降低了查找效率。为此，可采用二次探测再散列法或随机探测再散列法，以降低“聚集”现象。
|
|
|
|
（2）链地址法。链地址法是一种经常使用且很有效的方法。它将具有相同哈希函数值的记录组织成一个链表，当链域的值为NULL时，表示已没有后继记录。
|
|
|
|
例如，哈希表表长为11、哈希函数为Hash（key）=key mod 11，对于关键码序列47，34，13，12，52，38，33，27，3，使用链地址法构造的哈希表如下图所示。
|
|
|
|
|
|
|
|
|
|
在线性探测法解决冲突的方式下，进行哈希查找有两种可能：第一种情况是在某一位置上查到了关键字等于key的记录，查找成功；第二种情况是按探测序列查不到关键字为key的记录而又遇到了空单元，这时表明元素不在表中，表示查找失败。
|
|
|
|
在用链地址法解决冲突构造的哈希表中查找元素，就是根据哈希函数得到元素所在链表的头指针，然后在链表中进行顺序查找的过程。
|
|
|
