|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 查找 > 哈希查找 >
|
|
相关知识点：3个
|
|
|
|
|
解决冲突就是为出现冲突的关键字找到另一个“空”的哈希地址。常见的处理冲突的方法有开放定址法、链地址法（拉链法）、再哈希法、建立公共溢出区法等，在处理冲突的过程中，可能得到一个地址序列，记为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，使用链地址法构造的哈希表如下图所示。
|
|
|
|
|
|
|
