Getting random value from java HashMap in O(1) time

Question

All

I have read these links,

using toArray() on keySet and list.get() is not an option. Because these methods take O(n) time.

All the methods described in the above links take O(n) worst case to get a random value from hash map. Is it possible to do this in O(1) time?.

You can pretty much optimize for reads, or optimize for writes. If you want to optimize for reads, you can rebuild the array of keys every time the hashmap changes. — Mike Christensen, Jun 26 '14 at 18:28
The iteration order for a HashMap is not guaranteed. So if you're just looking for "some" value in the map, do getValues().iterator().next() and you won't be able to predict which value you get. What is the actual problem you are trying to solve? — jackrabbit, Jun 26 '14 at 18:34
I am not trying to solve any particular problem. This was an interview question. — Loki, Jun 26 '14 at 18:41
I can't think of a way unless you had some separate structure tracking keys or values that got added. — Chris Kessel, Jun 26 '14 at 19:31
I agree with you Chris Kessel. But maintaining that separate structure is again a challenge whenever elements are deleted from the HashMap. — Loki, Jun 26 '14 at 19:50

score 1 · Accepted Answer · answered Jun 26 '14 at 19:09

You can get the first value returned by the keySet().iterator().next() It is random but will be the same every time until the collection is changed.

The only alternative is to use reflection to grab the underlying array and navigate it yourself.

In short a HashMap is not designed for this purpose. If you need this, use another data structure.

1 Answers1