What is the time complexity of java.util.HashMap class' keySet() method?

algorithm, complexity-theory, hashmap, java

Solution

Getting the keyset is `O(1)` and cheap. This is because `HashMap.keyset()` returns the actual `KeySet` object associated with the `HashMap`.

The returned `Set` is not a copy of the keys, but a wrapper for the actual `HashMap`'s state. Indeed, if you update the set you can actually change the `HashMap`'s state; e.g. calling `clear()` on the set will clear the `HashMap`!

... iterating through the returned `Set` will take obviously `O(n)` time.

Actually that is not always true:

It is true for a `HashMap` is created using `new HashMap<>()`. The worst case is to have all `N` keys land in the same hash chain. However if the map has grown naturally, there will still be `N` entries and `O(N)` slots in the hash array. Thus iterating the entry set will involve `O(N)` operations.

It is false if the `HashMap` is created with `new HashMap<>(capacity)` and a singularly bad (too large) `capacity` estimate. Then it will take `O(Cap) + O(N)` operations to iterate the entry set. If we treat `Cap` as a variable, that is `O(max(Cap, N))`, which could be worse than `O(N)`.

There is an escape clause though. Since `capacity` is an `int` in the current `HashMap` API, the upper bound for `Cap` is 231. So for really large values of `Cap` and `N`, the complexity is `O(N)`.

On the other hand, `N` is limited by the amount of memory available and in practice you need a heap in the order of 238 bytes (256GBytes) for `N` to exceed the largest possible `Cap` value. And for a map that size, you would be better off using a hashtable implementation tuned for huge maps. Or not using an excessively large capacity estimate!

Problem

Original source