第二十六讲哈希表及其查找(编辑修改稿)

第二十六讲哈希表及其查找(编辑修改稿)内容摘要：

所谓开放定 址法，即是由关键码得到的哈希地址一旦产生了冲突，也就是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。 找空哈希地址方法很多，下面介绍三种： 1. 线性探测法 Hi=(Hash(key)+di) mod m ( 1≤ i m ) 其中： Hash(key)为哈希函数 m 为哈希表长度 di 为增量序列 1， 2，„„， m1，且 di=i 【例 】关键码集为 {47， 7， 29， 11， 16， 92， 22， 8， 3}，哈希表表长为 11， Hash(key)=key mod 11，用线性探测法处理冲突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 47 92 16 3 7 29 8 △ ▲ △ △ 4 1 1 92 均是由哈希函数得到的没有冲突的哈希地址而直接存入的 ； Hash(29)=7，哈希地址上冲突，需寻找下一个空的哈希地址： 由 H1=(Hash(29)+1) mod 11=8，哈希地址 8为空，将 29存入。 另外， 2 8 同样在哈希地址上有冲突，也是由 H1找到空的哈希地址的； 而 Hash(3)=3，哈希地址上冲突，由 H1=(Hash(3)+1) mod 11=4 仍然冲突； H2=(Hash(3)+2) mod 11=5 仍然冲突； H3=(Hash(3)+3) mod 11=6 找到空的哈希地址，存入。 线性探测法可能使第 i个哈希地址的同义词存入第 i+1个哈希地址，这样本应存入第 i+1 第七 章 查找 个哈希地址的元素变成了第 i+2 个哈希地址的同义词，„„，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。 为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。 2. 二次探测法 Hi=(Hash(key)177。 di) mod m 其中： Hash(key)为哈希函数 m 为哈希表长度， m 要求是某个 4k+3 的质数 (k 是整数 ) di 为增量序列 12， 12， 22， 22，„„， q2， q2 且 q≤ (m1) 仍以上例用二次探测法处理冲突，建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8。