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
– Mike Christensen, Commented Jun 26, 2014 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
– jackrabbit, Commented Jun 26, 2014 at 18:34
I am not trying to solve any particular problem. This was an interview question. — Loki
– Loki, Commented Jun 26, 2014 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
– Chris Kessel, Commented Jun 26, 2014 at 19:31

Peter Lawrey · Accepted Answer · 2014-06-26 19:09:48Z

1

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.

answered Jun 26, 2014 at 19:09

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1