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

Question

I am trying to implement a plane sweep algorithm and for this I need to know the complexity of java.util.HashMap class' keyset() method. What i feel, it would be O(n log n). Am I correct?

**Edit I am talking about the time complexity of the method keySet(), the walking over will take surely O(n) time. But I am not sure, how it retrieves all the keys in constant time (O(1)). **

Please help me guys.

Thanks in advance

Answer 1

This should be doable in O(n) time... A hash map is usually implemented as a large bucket array, the bucket's size is (usually) directly proportional to the size of the hash map. In order to retrieve the key set, the bucket must be iterated through, and for each set item, the key must be retrieved (either through an intermediate collection or an iterator with direct access to the bucket)...

**EDIT: As others have pointed out, the actual keyset() method will run in O(1) time, however, iterating over the keyset or transferring it to a dedicated collection will be an O(n) operation. Not quite sure which one you are looking for **

Answer 2

Surely it would be O(1). All that it is doing is returning a wrapper object on the HashMap.

If you are talking about walking over the keyset, then this is O(n), since each next() call is O(1), and this needs to be performed n times.

Answer 3

Java collections have a lot of space and thus don't take much time. That method is, I believe, O(1). The collection is just sitting there.

Answer 4

Actually, 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!