二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(21)

以上讨论了如何设定好的散列函数以减少冲突的问题。下面继续讨论对于不可完全避免的冲突，在它发生时应该怎样解决的问题。9.4.3 冲突的解决冲突的解决 collision resolution 或称冲突的处理，其方法基本上有两类：开地址 open addressing 法和拉链 chaining 法。⒈ 开地址法用开地址法解决冲突的做法是：当冲突发生时，用某种方法在散列表的基本区域内形成一个探查 测 序列，沿此探查序列逐个单元地进行查找，直到找到给定的关键字或碰到一个开放的地址 空单元 为止。插入时，碰到开放的地址则可以在这个地址里存放同义词。最简单的探查方法是进行线性探查，就是当碰撞发生时顺序探查表的下一个单元，即：若h key d，但与地址为d的单元中的关键字发生冲突，那么探查序列为d+1, d+2, …, m-1, 0, 1, …, d-1。由于α 1，即散列表的长度m大于实际的记录个数n，因此，沿着这个探查序列总能找到一个空的单元。下面给出用线性探查法解决冲突的算法。算法中用到的存储结构描述如下：const int m 12;typedef structint key;… … ;hashtable;hashtable ht[m];int K, n, i, c;为了判别散列表的单元是否为空，我们假设关键字均不为0，并且用0来表示空单元，而不再另设标志字段来标识。

散列表初始建立时，设基本区已清为0。在进入算法前要查找或插入的关键字已在变量K中。算法中h key 为散列函数，m是一个常量，等于散列表基本区域的长度。算法9.8 散列表的查找和插入⑴ C/C++ 程序：──用线性探查法解决冲突 HashSearch1 hashtable &ht[ ], int K HashSearch1 ht, K int i h K ;1. i ← h K [ 计算散列地址 ] while ht[i].key! K && ht[i]! 02. 循环 当ht[i].key≠K且ht[i].key≠0时,执行 i ++i % m;i ← i+1 % m if ht[i].key K3. 若ht[i].key K cout "retrieval" i ht[i] endl;则print "retrieval", i, ht[i] [ 查找成功 ] else否则ht[i].key ← K [ 插入 ] ht[i].key K;4. [ 算法结束 ] ▌ 例9. 23 设有8个关键字组成的序列 35, 08, 21, 15, 24, 03, 48, 33 ，散列表的长度为12，用除余法构造散列函数，用线性探查法解决冲突，按关键字在序列中的顺序插入，则可得到图9-36 b 所示的散列表。

若每个关键字的查找概率相同，则平均查找长度为ASL 1+1+1+1+2+3+3+1 /813/81.625用线性探查法解决冲突，可能产生另外一个问题，这就是聚集或堆积 clustering 。堆积是散列地址不同的结点争夺同一个散列地址 或两个或多个同义词子表结合在一起 的现象。例如，在用h key 计算的地址去存储时，该位置可能已被非同义词的结点所占用。又例如，在发生冲突后沿着线性探查序列查找时，这些位置上也可能存入非同义词的结点，这时都会造成不是同义词的结点处于同一探查序列之中，从而增加了探查序列的长度，也就降低了查找效率。如果散列函数选择不当，或负载因此过大，都可能使堆积现象加剧。为了改善堆积现象，可以考虑使用双散列函数探查法。这种方法使用两个散列函数h1和h2，其中h1和前面讲述的h相同，以关键字值为自变量，产生一个0 ～ m-1之间散列地址。h2也是以关键字值为自变量，产生一个0 ～ m-1之间的并和m互素的数作为探查序列中探查项的间隔。设h1 key d时发生冲突，通过计算c h2 key ，则得到的探查序列为：d+c %m, d+2c %m, d+3c %m, …从上面的探查序列可以看出，使用双散列函数探查法是跳跃式地散列在基本存贮区域内，而不像线性探查法那样探查一个顺序的地址序列。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-21.html