Dea*_*n J 0 java amortized-analysis
有人知道Java HashMap中keySet的摊销分析是什么吗？ O(1)？
正在迭代它们O(n)？
map.keySet() 简单地返回对存储在地图中的键集的引用,因此它显然是O(1)操作.
然后迭代就是该集合的循环,它本身在内部使用地图桶上的循环,因此操作需要与n + m成比例的时间,其中n是键集的大小,m是映射的容量.
因此,如果您的地图只有一个条目具有非常大的容量,那么即使只有一个密钥,对keySet的迭代也会遍历所有存储桶.
不知道你是如何用big-o表示法翻译的.
我刚刚用2张地图进行了快速测试,每张地图都有一个条目.一个映射的容量为1000万,另一个映射的容量为1.对于大型映射(18,843,092 ns对5434 ns),对键集的迭代(两种情况下都是一项)需要3,500倍的时间.
迭代此集合需要的时间与HashSet实例的大小(元素数量)加上后备HashMap实例的"容量"(桶数)之和成比例.因此,如果迭代性能很重要,则不要将初始容量设置得太高(或负载因子太低)非常重要.