I am trying to implement a plane sweep algorithm and for this I need to know the time complexity of java.util.HashMap class' keySet() method. I suspect that it is O(n log n). Am I correct?
Point of clarification: I am talking about the time complexity of the keySet() method; iterating through the returned Set will take obviously O(n) time.
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 obviouslyO(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!