java - 使用 hashmap 的空间复杂度。应该考虑 key 大小吗？

Question

在java中，我们通常认为使用hashtable的空间复杂度是O(n)。我们是否还应该考虑 key 大小，如果 key 非常大怎么办？

Answer 1

这取决于键的大小与您存储在哈希表中的元素数量(即 n)之间的关系。如果键的大小是 n 的函数，则在计算空间复杂度时必须考虑键的大小。哈希表的取值也是如此。

不过，我认为可以安全地假设在大多数情况下 key 的大小(无论多大)是一个常数而不是 n 的函数。