algorithm - 浮点哈希表

Question

我想使用浮点值作为键来构造查找表。当我使用给定的浮点键查询表时，我希望它返回其键最接近查询键的值。

但是我事先不知道浮点键是否均匀分布。

例如，我的表可能是:

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

如果我查询 1.5，我想返回“blue”。

有没有办法构建表，使其具有 O(n) 内存和 O(1) 查找？ (也就是哈希表)。如果我存储排序的键/值对，显然有一个 O(log(n)) 算法，但我很好奇是否可以改进该界限。

Answer 1

您可以忽略您的 key 是 float 这一事实，因为它实际上不会影响答案。如果您的输入是 32 位(相当于 float )或 64 位(相当于 double )整数，答案将是相同的。而且，我相信答案是否定的。

为了找到最近的邻居，您需要对键进行排序。当你有一个 32 位或 64 位 key 时(弄清楚是哪一个可能会有所帮助)这意味着你真的别无选择，只能有一个排序的数据结构(树？堆？排序数组？)你做一个 O (log(n)) 搜索。

获得对特定条目的恒定时间访问很容易，但是获得对特定条目的最近邻居的恒定时间访问要么需要一个包含 40 亿个条目(对于 float )的查找表，要么需要魔法。