Floating point hash table

Question

I want to build a lookup table using a floating point value as a key. When I query a table with a given floating point key, I want it to return a value whose key is closest to the key query.

However, I do not know in advance if the floating point keys are evenly distributed or not.

For example, my table could be:

key     value
1.0     "red"
1.25    "blue"
2.0     "green"

If I request 1.5, I want to return "blue".

Is there a way to build a table so that it has O (n) memory and O (1) lookup? (That is, a hash table). Obviously, there is an O (log (n)) algorithm if I kept key / value pairs sorted, but I'm curious if this binding can be improved.

Answer 1

You can ignore the fact that your key is a floating point number, since it really does not affect the answer. The answer will be the same if your input was a 32-bit (equivalent to swimming) or 64-bit (equivalent to double) integer. And I think the answer is no.

To find the closest neighbor, you need keys for sorting. When you have a 32-bit or 64-bit key (it may be useful to clarify that), it means that you really have no choice but to have a sorted data structure (tree? Heap? Sorted array?), Which you do O (log (n)) search.

, 4 ( ), .