c++ - HashTable 键与取值的复杂性

Question

我刚刚阅读了一个面试问题，该问题询问了哈希键与哈希值的获取复杂性。我总是认为两者是相同的，在 O(1 + n/k) （其中 k 是桶数）。我错过了什么？

Answer 1

获取哈希键的长度为 O(lk)，因为您必须对其进行哈希处理，但n/k对于任何给定的哈希表都应该是恒定的。这通常被称为 O(1)，因为它不依赖于n，但它不是严格的O(1)，除非密钥大小是固定的。

但是获取一个哈希值需要遍历整个表来寻找它，假设你没有预先订购它（你可以设计哈希表，它也可以支持 O(log(n)) 的二进制查找，但这并不常见） .

Answer 2

哈希值是初始查找位置。如果所需的数据未存储在该索引处，则通过迭代获得哈希键，直到找到所需的数据。