java - 哈希函数将k个最近的数据映射到同一个桶中

Question

我有一个数组 [1, 2, 3, 4, 5, 10, 12, 6, 200, 300, 500]。我正在尝试开发一个哈希函数，使得所有由相同距离 k 分隔的元素应该在输出数组中的同一位置发生碰撞，在该位置形成一个链表，并在该位置形成链表的 header 地点。这将有助于使用哈希函数根据距离找到最近的元素。我尝试了非常简单的哈希函数 h(j)=int(j/k) 其中 k 是距离，例如 if k=5 then碰撞点将类似于 [1, 2, 3, 4, 5] [6, 10] [12] [200] [300] [500]。我的目标是为哈希函数提供两个数字，例如1 和 2 并且它们应该返回数组中相同的位置 0 告诉我它们是最近的邻居。这应该以预期的 theta n 空间和时间复杂度运行。

Answer 1

除非您计划在多个存储桶中拥有相同的数字，否则这是不可能的。即使在您自己的示例中，5 与 6 位于不同的存储桶中，但实际上比与 6 分组的 10 更接近 6。

如果您允许相同的数字出现在多个存储桶中，那么您可以根据阈值距离获得“近邻”分组，但您的结果看起来更像是这样(假设最大距离 < 5):

[1,2,3,4,5] [2,3,4,5,6] [6,10] [10,12] [200] [300] [500]