哈希表在相同或冲突值上是如何线性的?

哈希表在概念上类似于链表的数组(表)( 水桶 在表格中)。不同之处在于管理和访问该数组的方式:使用函数生成用于计算数组索引的数字。

一旦将两个元素放在同一个bucket中(相同的计算值,即碰撞),那么问题就变成了在列表中进行搜索。列表中的元素数有望低于哈希表中的元素总数(意味着其他bucket中存在其他元素)。

但是,您跳过了该段中的重要介绍:

如果你使用 线性探测或双哈希 ,查找散列到相同值的所有项意味着您需要散列该值,然后遍历表中非空项的“链”,以查找散列到相同值的项的数量。但对于散列到相同值的项数来说,这并不是线性的-- 它与散列到相同或冲突值的项数成线性关系 。

Linear probing 是哈希表的另一种实现,其中不使用任何列表(链)进行冲突。相反,您只需在阵列中找到最近的可用点,从预期位置开始,然后向前。数组填充的越多,发现下一个位置也在使用的机会就越大,因此只需继续搜索即可。位置由使用 散列为相同或冲突值的项 ,尽管您永远不会(也不在乎)这两种情况是哪一种,除非您在那里明确看到现有元素的哈希。

This CppCon presentation video 对哈希表进行了很好的介绍和深入分析。