哈希表在相同或冲突值上的线性程度如何？

Question

为了更好地理解散列，我查看了这个StackOverflow答案，并看到了以下内容（关于我们需要在恒定时间内获得桶大小的事实）：

如果使用线性探测或双重散列，查找散列到相同值的所有项意味着需要对值进行散列，然后遍历表中非空项的“链”，以查找散列到相同值的项的数量。这与散列到相同值的项数不是线性的，而是与散列到相同值或冲突值的项数成线性的。

这意味着它“在散列到相同或冲突值的项目数量上是线性的”吗？它不会在哈希表中的项目总数上是线性的吗，因为它可能需要在线性探测期间遍历每个值？我不明白为什么它必须遍历碰撞的那些。

例如，如果我在一个哈希表上使用线性探测（步长1），我有不同的键（不冲突，所有哈希都是唯一值）映射到奇数索引槽1,3,5,7,9




Answer 1

哈希表在概念上类似于链表（表中的bucket）的数组（表）。不同之处在于管理和访问该数组的方式：使用函数生成用于计算数组索引的数字。

一旦有两个元素放在同一个桶中（相同的计算值，即碰撞），那么问题就变成了在列表中搜索。列表中的元素数有望低于哈希表中的元素总数（这意味着其他存储桶中存在其他元素）。

但是，您跳过了该段中的重要介绍：

如果使用线性探测或双重散列，查找散列到相同值的所有项意味着需要对值进行散列，然后遍历表中非空项的“链”，以查找散列到相同值的项的数量。这与散列到相同值的项数不是线性的，而是与散列到相同值或冲突值的项数成线性的。

线性探测是哈希表的另一种实现，在该哈希表中，您不使用任何列表（链）进行冲突。相反，您只需在阵列中找到最近的可用点，从预期位置开始，然后继续。数组的填充量越大，发现下一个位置也被使用的几率就越高，所以你只需要继续搜索。这些位置由散列到相同或冲突值的项使用，尽管您永远不会（也不在乎）这两种情况中的哪一种是，除非您明确地看到现有元素的散列。

本CppCon演示视频对哈希表进行了很好的介绍和深入分析。