是否有一个最近的键映射数据结构？ [英] Is there a nearest-key map datastructure?

问题描述

我有一个情况我需要找到关键最接近一个我要求的数值。这有点像一个定义按键之间距离最近的映射。

I have a situation where I need to find the value with the key closest to the one I request. It's kind of like a nearest map that defines distance between keys.

例如，如果我在地图上的键{A，C，M，Z}，程序D请求将返回C'S价值。

For example, if I have the keys {A, C, M, Z} in the map, a request for D would return C's value.

你知道吗？

推荐答案

大多数树的数据结构使用某种排序算法存储和查找键。这样的许多实现可以找到一个接近关键看你用探测的关键（通常它要么低于最接近或高于最近的）。例如Java的 TreeMap的实现这样的数据结构，你可以告诉它让你在下面的查找键最接近的键，或最接近键上方的查找键（ higherKey 和 lowerKey ）。

Most tree data structures use some sort of sorting algorithm to store and find keys. Many implementations of such can locate a close key to the key you probe with (usually it either the closest below or the closest above). For example Java's TreeMap implements such a data structure and you can tell it to get you the closest key below your lookup key, or the closest key above your lookup key (higherKey and lowerKey).

如果你可以计算出距离（它并不总是那么容易 - Java的接口只需要你知道，如果任何给定的关键是低于或高于其他任何给定的键），那么你可以要求上述两个最接近及以下最接近和然后计算自己哪一个更接近。

If you can calculate distances (its not always easy - Java's interface only require you to know if any given key is "below" or "above" any other given key) then you can ask for both closest above and closest below and then calculate for yourself which one is closer.

这篇关于是否有一个最近的键映射数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！