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

Question

Anyone know what the amortized analysis is of keySet in Java HashMap? O(1)?

Is iterating through them O(n)?

Answer 1

map.keySet() simply returns a reference to the key set which is stored in the map, so it clearly is an O(1) operation.

The iteration is then a loop over that set, which itself internally uses a loop over the map's buckets, so the operation takes a time proportional to n+m where n is the size of the keyset and m the capacity of the map.

So if your map has a very large capacity with only one entry, an iteration over keySet will loop over all the buckets even if there is only one key.

Not sure how you translate that in big-o notation.

I just ran a quick test with 2 maps, with one entry each. One map has a capacity of 10 millions, the other a capacity of 1. The iteration over the keyset (one item in both cases) takes 3,500 times more time with the large map (18,843,092 ns vs 5434 ns).

ps: it is similar to what the javadoc of HashSet says:

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.

Answer 2

You can check the source code for the keySet.

Iterating through a Set is O(n) based in this