java - 访问/查找 HashMap 存储桶(不是存储桶中的值)的时间复杂度是多少？

Question

假设我们有两个不同的 hashMap，例如 map1 和 map2。

• map1 有 1000 个条目和 1000 个存储桶。
• map2 有 999999 个条目和 999999 个存储桶。

假设我们有一个哈希码为“1234”的对象“obj1”，我们将这个对象作为map1和map2中的键(值为“xyz”)。

在map2中找到“obj1”值会需要更多时间吗？从map1和map2访问obj1的时间复杂度仍然是O(1)吗？

Answer 1

在 HashMap 中查找存储桶的时间复杂度始终为 O(1)，与容量(存储桶数量)无关。

假设您的 obj1 的哈希代码为 1234567。 HashMap 的核心不是搜索正确的存储桶(如 TreeMap 那样)，而是计算其位置，并立即访问具有该数字的存储桶。这就是哈希码发挥作用的地方。

计算结果为 obj.hashCode() %capacity，结果数字给出了 bucketsArray 的索引。

• 对于小型 HashMap ，它是 1234567 % 1000 = 567，这意味着相关存储桶是 bucketsArray[567] 。

• 对于大的，它是 1234567 % 999999 = 234568，结果是 bucketsArray[234568]。

计算除法余数所需的时间是常数，与值无关。访问具有给定索引的数组的时间也是恒定的，因此它是 O(1)。

我们只讨论了寻找水桶的问题。如果存储桶包含多个条目，则线性搜索完成 HashMap 访问，这是 O(K)，其中 K 是存储桶中的条目数(平均？最大？)。