值在范围内时返回键

user201411 发表于 Dev

用户201411

我有一个很大的数据集，其中值是不重叠的范围，并按升序排序。范围之间有孔，并且键（类型很长）可以分配给多个范围：

[100,300] K1
[310,400] K1
[401,600] K2
[650,1000] K3
...

我需要找到给定值的键。如果value不属于任何范围，我应该返回0。

我的方法是建立

NavigableMap<Long, Range> map = new TreeMap<>();

然后

map.put(K1, new Range(100,300);
...

这将导致一个非常大的地图，并按键排序。这不是我想要的，因为我希望有一个按范围值排序的地图，这样我就可以轻松进行二进制搜索。我的问题是我不知道如何使用此地图来查找给定值的键。例如，值101应该返回K1，500应该返回K2，301应该返回0。有什么方法可以使用NavigableMap实现我想要的功能，或者我使用了错误的方法？

吉姆·加里森

由于您已经声明了范围不能重叠但可能存在间隙，因此应使用NavigableMap<Range,Long>和的Range表示形式仅对hashCode和equals实现使用范围的下限。

请注意，我NavigableMap从代码示例中显示的内容中颠倒了泛型类型的顺序。

要搜索一个值，您希望最大的条目（即具有最大下限的条目）小于搜索键。

相反，如果您使用Range对象的上限，则希望最小的条目大于搜索键。

找到适当的Map条目后，由于可能存在间隙，您必须再次检查键值是否确实在范围内。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。