HashMap迭代复杂度

Question

从java doc我知道:

对集合视图的迭代需要与HashMap实例的"容量"(桶的数量)加上其大小(键 - 值映射的数量)成比例的时间.因此,如果迭代性能很重要,则不要将初始容量设置得太高(或负载因子太低)非常重要.

这是否意味着迭代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是您设置的容量或自动计算的容量.

Answer 2

不，这意味着 a 迭代的复杂度HashMap是 O(n + s)，其中n是映射数量，s是大小。它必须线性迭代所有s个桶和所有n个条目。