密集探测哈希表vs线性探测哈希表

密集探测哈希表和线性探测哈希表都是基于探测的哈希表实现方式，它们的主要区别在于探测序列的生成方式和解决哈希冲突的策略。线性探测哈希表探测序列：

• 在线性探测中，探测序列是线性的，即如果哈希函数计算的位置已经被占用，则顺序查找下一个位置，直到找到一个空槽。

• 具体来说，如果 h(key) 是初始哈希值，且该位置已被占用，则检查 h(key) + 1，然后是 h(key) + 2，依此类推。

特点：

• 实现简单直观。

• 容易出现“聚集”现象，即连续的多个位置被占用，这会增加后续插入和查找操作的平均时间复杂度。

• 需要定期重新哈希（rehashing）以维持性能。

密集探测哈希表探测序列：

• 密集探测哈希表通常采用更复杂的探测序列生成方式，如二次探测或双重散列。

• 二次探测 使用二次函数来确定探测步长，例如 h(key) + i^2，其中 i 是探测的次数。

• 双重散列 使用第二个哈希函数来计算探测步长，例如 h(key) + i * h'(key)，其中 h'(key) 是第二个哈希函数的结果。

特点：

• 相比线性探测，密集探测能够更有效地分散键值对，减少聚集问题。

• 提供更好的平均查找性能，尤其是在哈希表接近满载时。

• 实现稍微复杂一些，需要额外的哈希函数或计算步骤。

总结

• 线性探测 是最简单的探测方法，但容易导致聚集，影响性能。

• 密集探测 通过使用更复杂的探测序列，如二次探测或双重散列，能够更好地避免聚集，提供更稳定的性能。

在实际应用中，选择哪种探测方式取决于具体的需求和场景。如果对性能有较高要求，尤其是在哈希表可能接近满载的情况下，密集探测通常是更好的选择。

小结：

其实没必要这么区分，线性和二次探测或双重散列解决冲突的方式，也许都可以称为稠密哈希函数。