阐述冲突解决策略的优缺点

下面解释了一些冲突解决技术的优缺点：

独立链式哈希

独立链式哈希是一种哈希技术，其中使用列表来处理冲突。因此，在同一位置有多个元素，它们在一个列表中。序列以链表的形式维护。

独立链式哈希的优点如下：

• 独立链式技术对表的大小不敏感。

• 思想和实现都很简单。

独立链式哈希的缺点如下：

• 在独立链式中，键分布不均匀。

• 独立链式可能导致表中出现空隙。

• 位置中的列表可能非常长。

线性探测

线性探测是一种简单的冲突解决技术，用于解决哈希表（用于维护哈希表中值的集合的数据结构）中的冲突。如果键值的位 置发生冲突，则线性探测技术会将下一个可用空间分配给该值。

线性探测的优点如下：

• 线性探测需要的内存很少。

• 它不太复杂，实现起来也比较简单。

线性探测的缺点如下：

• 线性探测会导致一种称为“主要聚集”的现象，其中哈希表中存在大量被占用的单元。

• 线性探测中的值倾向于聚集，这使得探测序列更长。

二次探测

二次探测也是一种冲突解决机制，它接收由哈希函数生成的初始哈希值，并继续从生成的函数中添加任意二次多项式的连续值，直到找到一个空闲槽来放置值。

二次探测的优点如下：

• 二次探测不太可能出现主要聚集问题，并且比双哈希更容易实现。

二次探测的缺点如下：

• 二次探测存在次要聚集。当两个键哈希到同一位置时，它们具有相同的探测序列。因此，在进行插入之前可能需要多次尝试。

• 而且探测序列不会探测表中的所有位置。

双哈希

双哈希也是当两个不同的待搜索值产生相同的哈希键时的冲突解决技术。

它使用哈希函数生成的哈希值作为起点，然后通过一个间隔递增位置，该间隔使用第二个独立的哈希函数确定。因此，这里有两个不同的哈希函数。

双哈希的优点如下：

• 双哈希最终克服了聚集问题。

双哈希的缺点如下：

• 双哈希比其他任何方法都更难实现。

• 双哈希可能导致抖动。

Bhanu Priya

更新于：2021年7月8日

浏览量 10K+

开启您的职业生涯

完成课程获得认证

开始学习