第1个回答 2022-07-06
影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的 数据元素 的 哈希值 相同时，就会发生冲突。为减少发生冲突的可能性，哈希函数应该将数据尽可能分散地映射到 哈希表 的每一个表项中。解决冲突的方法有以下两种：
所谓开放定址法，即由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素。我们需要寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。常用的找空哈希地址方法有下列三种。
47，7，11，16，92均是由哈希函数得到的没有冲突的哈希地址，因而是直接存入的。Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址：
H 1 = ( Hash(29) + 1 ) % 11 = 8，哈希地址8为空，所以将29存入。
另外，22，8同样在哈希地址上有冲突，也是由 找到空的哈希地址的；而Hash(3)=3，哈希地址上冲突，因为：
H 1 = ( Hash(3) + 1 ) % 11 = 4，仍然冲突
H 2 = ( Hash(3) + 2 ) % 11 = 5，仍然冲突
H 3 = ( Hash(3) + 3 ) % 11 = 6，找到空的哈希地址，存入。
线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词……因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，或再哈希函数探测法，以改善“堆积”问题。
与关键码寻找空的哈希地址只有3这个关键码不同，Hash(3)=3，哈希地址上冲突，由[图片上传失败...(image-c7d04d-1609756554547)]
H 1 = ( Hash(3) + ) % 11 = 4，仍然冲突
H 2 = ( Hash(3) - ) % 11 = 2，找到空的哈希地址，存入。
将 哈希值 相同的数据元素存放在一个 链表 中，在查找 哈希表 的过程中，当查找到这个链表时，必须采用线性查找方法。这样的好处是，不怕冲突多；缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。
链地址法又称拉链法，设哈希函数得到的哈希地址域在区间[0，m-1]上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组：
ElemType eptr[m]；
建立m个空链表，由哈希函数对关键码转换后，映射到同一哈希地址i的同义词均加入 eptr[i]指向的链表中。
对关键码序列为 {47，7，29，11，16，92，22，8，3，50，37，89，94，21}，哈希函数为Hash(key)=key % 11，用拉链法处理冲突，建表下所示。
设哈希函数产生的哈希地址集为[0，m-1]，则分配两个表：
一个基本表ElemType base_tbl[m]；每个单元只能存放一个元素。
一个溢出表ElemType over_tbl[k]；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的元素一律存入该表中。
查找时，对给定值kx通过哈希函数计算出哈希地址i，先与基本表的base_tbl[i]单元比较，若相等，查找成功；否则，再到溢出表中进行查找。