java - 大O : Getting all of the keys in a Java HashMap

Question

有人知道Java HashMap中keySet的摊销分析是什么吗？ O(1)？

迭代它们O(n)吗？

Answer 1

map.keySet() 只是返回对存储在映射中的键集的引用，因此它显然是一个 O(1) 操作。

迭代是对该集合的循环，它本身在映射的存储桶上使用循环，因此操作所需的时间与 n+m 成正比，其中 n 是键集的大小，m 是映射的容量.

因此，如果您的 map 容量非常大，只有一个条目，那么即使只有一个键，对 keySet 的迭代也会遍历所有存储桶。

不确定你如何将其翻译为大 o 表示法。

我刚刚用 2 张 map 进行了快速测试，每张 map 都有一个条目。一张 map 的容量为 1000 万，另一张 map 的容量为 1。对于大 map ，键集(两种情况下均为一项)的迭代需要多出 3,500 倍的时间(18,843,092 ns vs 5434 ns)。

ps:类似于javadoc of HashSet说:

Iterating over this set requires time proportional to the sum of the HashSet instance's size (the number of elements) plus the "capacity" of the backing HashMap instance (the number of buckets). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.