HashMap迭代复杂度

Question

根据Java文档：

遍历集合视图的时间与HashMap实例（桶的数量）的“容量”成正比，以及它的大小（键值映射的数量）。因此，如果迭代性能很重要，则不要将初始容量设置得太高（或负载因子太低）。

这是否意味着遍历HashMap的时间复杂度是O(n²)？这个问题听起来有点傻，但我确实有些困惑。

- jarosik

Answer 1

不，这并不意味着迭代复杂度是O(n²)。

当容量c自动设置时，它随项目数量的增加而以O(n)增长，而不是以项目的O(n²)增长。根据源代码，目标容量计算如下：

int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);

其中loadFactor是一个默认设置为0.75f的float值。

你引用的这段话只有在手动设置容量时才变得相关。它告诉你性能是O(c)，而不是O(n)，其中c是你设置或自动计算的容量。

- Sergey Kalinichenko

Answer 2

不，这意味着对 HashMap 进行迭代的复杂度为 O(n + s)，其中 n 表示映射数量，s 表示大小。必须在所有 s 桶上进行线性迭代，并在所有 n 条目上进行线性迭代。

- rgettman