根据Java文档:
遍历集合视图的时间与HashMap实例(桶的数量)的“容量”成正比,以及它的大小(键值映射的数量)。因此,如果迭代性能很重要,则不要将初始容量设置得太高(或负载因子太低)。
这是否意味着遍历HashMap的时间复杂度是O(n²)?这个问题听起来有点傻,但我确实有些困惑。
根据Java文档:
遍历集合视图的时间与HashMap实例(桶的数量)的“容量”成正比,以及它的大小(键值映射的数量)。因此,如果迭代性能很重要,则不要将初始容量设置得太高(或负载因子太低)。
这是否意味着遍历HashMap的时间复杂度是O(n²)?这个问题听起来有点傻,但我确实有些困惑。
不,这并不意味着迭代复杂度是O(n2)。
当容量c
自动设置时,它随项目数量的增加而以O(n)增长,而不是以项目的O(n2)增长。根据源代码,目标容量计算如下:
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
其中loadFactor
是一个默认设置为0.75f
的float
值。
你引用的这段话只有在手动设置容量时才变得相关。它告诉你性能是O(c),而不是O(n),其中c
是你设置或自动计算的容量。
HashMap
进行迭代的复杂度为 O(n + s),其中 n 表示映射数量,s 表示大小。必须在所有 s 桶上进行线性迭代,并在所有 n 条目上进行线性迭代。