从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²)?这个问题听起来很傻,但实际上我有点困惑。
最佳答案
不,这并不意味着迭代复杂度是O(n2)。
当容量 c
被自动设置时,它随着项目的数量增长为 O(n),而不是项目的 O(n2)。根据源码,目标容量计算如下:
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
其中 loadFactor
是一个 float
值,默认设置为 0.75f
。
只有当您手动设置容量时,您引用的段落才有意义。它告诉您性能是 O(c),而不是 O(n),其中 c
是您设置的容量或自动计算的容量。
关于java - HashMap 迭代复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33836011/