1

Have a LinkedHashMap<Float, Integer>. The keys of this HashMap are points in time in seconds (like 0.031f or 1.4021f). There can be hundreds of thousands of entries.

Given a float value, say 0.6102f, I need to find the HashMap key that is closest to it (like 0.6002f maybe, assuming that's in the keyset).

A trivial answer would be to check key by key of the HashMap. After all, the entries happen to be correctly sorted. But I guess that's an O(n) operation which may not be a great idea given that I have to perform this search several times per second.

Is there an efficient way to find the "closest float key" of a HashMap given a float?

1
  • If you are not bound to the use of HashMap, you may be interested in using a TreeMap. Commented Sep 19, 2015 at 3:24

1 Answer 1

3

There is no efficient way to do this using a HashMap; i.e. nothing that is better than O(N) where N is the number of entries in the map.

However, if you switch to using a TreeMap<Float, Integer> you can find the entry with the closest key in O(logN). You need to use floorEntry and ceilingEntry and then test which of the 2 entry keys is nearest to your given key.


After all, the entries happen to be correctly sorted.

Actually the keys in a HashMap aren't sorted. The hashCode() implementations for some key types may make appear that the HashMap keys are sorted, but what you are seeing is an artifact.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.