用线性探测法解决冲突时,如何处理被删除的结点

Question

如题所述

Answer 1

用线性探测法解决冲突时，处理被删除的结点：当冲突发生时，使用某种探查（亦称探测）技术在散列表中形成一个探查（测）序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址为止。

按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。

搜索

为了搜索给定的键x，散列表中由h（x）对应的单元开始的相邻单元h（x）+1，h（x）+2都将被检查，直到找到了内容为空的单元或是找到了存储给定键为x的单元。其中，h是散列函数。如果找到了存储给定键的单元，搜索将会返回单元中存储的键对应的值。否则，如果搜索遇到了空的单元，键在表中就不存在，因为键应当被存放在所有未被搜索的单元之前。