algorithm - 在通用哈希表中查找项目？

Question

如果项目是随机组织的，表格如何知道从哪里开始查找？

在非随机表中，项目是根据某些特征组织的。 (即名称)。因此，如果该表需要查找有关“John”的一些任意信息，它可以开始在“J”存储桶中查找。

虽然在通用哈希表中，项目是随机排列的。没有明确的特征。因此，要查找有关“John”的一些任意信息，表格是否必须遍历每个存储桶？

这不是浪费时间吗？这就像翻遍您家中的每个橱柜来寻找一把勺子。

Answer 1

虽然前面的答案基本上是正确的，但它们并没有直接解决通用哈希算法的随机部分。通用哈希算法在计算 key 的哈希值时不使用随机性。随机数仅在哈希表初始化期间用于从哈希函数族中选择一个哈希函数。这可以防止有权访问散列函数细节的对手设计出最坏情况的 key 集。

换句话说，在哈希表的生命周期内，给定键的桶是一致的。但是，不同的实例(例如下次程序运行时)可能会将相同的 key 放在不同的存储桶中。