任何人都知道Java HashMap中keySet的摊销分析是什么？ O(1)?
是否遍历它们O(n)？
问问题
2065 次
2 回答
6
map.keySet()只需返回对存储在映射中的键集的引用，因此它显然是一个 O(1) 操作。
然后迭代是对该集合的循环，它本身在内部使用映射桶上的循环，因此操作花费的时间与 n+m 成正比，其中 n 是键集的大小，m 是映射的容量。
因此，如果您的地图容量非常大，只有一个条目，那么即使只有一个键，对 keySet 的迭代也会遍历所有桶。
不知道你是如何用大o表示法翻译的。
我刚刚对两张地图进行了快速测试，每张地图都有一个条目。一张地图的容量为 1000 万，另一张的容量为 1。在密钥集上的迭代（两种情况下都是一项）在大地图上花费了 3,500 倍以上的时间（18,843,092 ns 对 5434 ns）。
ps：类似于HashSet的javadoc所说的：
迭代这个集合需要的时间与 HashSet 实例的大小（元素的数量）加上支持 HashMap 实例的“容量”（桶的数量）的总和成正比。因此，如果迭代性能很重要，那么不要将初始容量设置得太高（或负载因子太低），这一点非常重要。
于 2012-08-10T14:05:24.660 回答