algorithm - 使用多变量 key 散列访问时间

Question

假设字典有 2 个变量键而不是 1 个这样的键

dictionary[3,5] = Something
dictionry[1,2] = Something
dictionary[3,1] = Something

搜索时间是否仍为 O(1)。如果我需要查找 dictionary[1,5] 是否存在，它会产生常数时间吗？

提前致谢。

Answer 1

当你在哈希表中进行查找时，所涉及的成本是

• 散列要查找的项目，以及
• 将该项目与表中的(预期 O(1) 数量)其他条目进行比较。

我们可以将哈希表查找的预期成本写为 O(hash-cost + compare-cost)。

在您的情况下，散列一对而不是单个元素的成本仍然是 O(1) - 只需散列该对的每个元素并对这两个值应用一些散列组合步骤。类似地，比较两对的成本也是 O(1)(假设可以在常数时间内比较该对的每个单独元素)。因此，查找仍将是(预期的)常数时间。

上述论点概括为任何固定大小的三元组作为键。当键具有可变长度时，您通常不得不担心散列和比较键的成本，如果您对没有长度限制的字符串进行散列，就会出现这种情况。