java - HashMap 迭代复杂度

Question

从java doc我知道:

Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.

这是否意味着在 HashMap 上迭代的时间复杂度是 O(n²)？这个问题听起来很傻，但实际上我有点困惑。

Answer 1

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

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

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

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

只有当您手动设置容量时，您引用的段落才有意义。它告诉您性能是 O(c)，而不是 O(n)，其中 c 是您设置的容量或自动计算的容量。