从基于范围的数据结构进行键查找 [英] Key lookup from a data structure based on range

问题描述

例如，如果我有以下情况

1. 如果键位于1-4之间，请选择A。


2. 如果键的范围为5-6，则选择B。

如果有请求得到值为key，key = 2，那么我应该返回A，为5，返回B等等。持有这种关联的数据结构是什么？我可以通过存储1-A，2-A，3-A，4-A，5-B和6-B创建hashmap，但是想检查是否有更好的方法来实现。

解决方案

对范围内的每个项目使用哈希图似乎太广泛，如果范围是（1-2 ^ 20） ？如果是双倍呢？存储这些将是太贵了。

您可以使用普通的skip-list / tree，其中包括每个范围的下限和上限。注意，当在二进制树中搜索一个值时，如果不存在，搜索将在搜索之前/之后处于下一个值时结束，例如：如果您有范围键1,4，并且搜索3搜索将在您达到1或4时结束，所以我们可以在树中存储范围的上限/下限。

现在，我们还需要存储对于每个这些真正的范围（所以如果我们有1-4,8-​​9，我们搜索7，当我们达到4/8时，我们会知道它是无效的）。所以如果钥匙在法定范围内，我们将在搜索时达到上限/下限！

所以总之，只要添加下限和上限，当你搜索，搜索密钥，并查看绑定是否匹配。

ops应该是这样的（伪代码）：

pre> add（lower，upper，value）：
tree.add（lower / * key * /，（lower，upper，value））
tree.add（upper / * key * /，（lower，upper，value））
search（key）：
node = tree.search（key）
if node.lower< = key< = node.upper：
return node.value
return KEY_NOT_IN_TREE_ERROR
del（lower，upper）：
tree.del（lower）
tree。 del（上）


这些操作中的每一个都将是O（logn），然后哈希更慢，但是将消耗更少的空间。

For example, if I have the following scenario

1. If key is of range 1-4, then select A.
2. If key is of range 5-6, then select B.

If there is a request to get the value for say, key=2, then I should return A, for 5, return B and so on. What is a good data structure to hold this association? I can create a hashmap by storing 1-A, 2-A, 3-A, 4-A, 5-B and 6-B, but wanted to check whether there is a better way of achieving this.

解决方案

using hash map for each item in the range seems too expansive, what if the range is (1-2^20)? and what if it is a double? it will be too expensive to store these.

you can use an ordinary skip-list/tree, which will include the lower and upper bounds of each range. note then when searching in a binary tree for a value, if it does not exist, your search will end when you are at the next value before/after the search, example: if you have range keys 1,4, and you search 3, search will end when you reach 1 or 4. so we can store the upper/lower bounds of the range in the tree.

now, we will also need to store for each of these the true range (so if we have 1-4,8-9 and we search for 7, we'll know it's invalid when we reach 4/8). so if the key is in legal range, we will reach its upper/lower bound when searching!

so in conclusion, just add the lower and upper bounds, when you are searching, search for the key, and look if the bound matches.

ops should be something like that (pseudo code):

add (lower,upper,value):
   tree.add(lower/*key*/,(lower,upper,value))
   tree.add(upper/*key*/,(lower,upper,value))
search (key):
   node = tree.search(key)
   if node.lower <= key <= node.upper: 
      return node.value
   return KEY_NOT_IN_TREE_ERROR
del(lower,upper):
  tree.del(lower)
  tree.del (upper)

each of these ops will be O(logn), slower then hash, but it will consume much less space.

这篇关于从基于范围的数据结构进行键查找的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！