c++ - 哈希表键与取值复杂性

Question

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

Answer 1

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

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