CODEWITHSUNDEEP
data-structures
Prasanna
Prasanna

Reputation: 3771

Key lookup from a data structure based on range

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.

Upvotes: 4

Views: 1617

Answers (4)

Nitin Rahoria
Nitin Rahoria

Reputation: 39

It's better to use object of class to store as key of hashmap.

Here in class you can define Fields as upperbound, lower bound and should override equals and hashCode methods.

In equals you can write logic to compare key object's upperbound and lowerbound is in between this.upperbound and this.lower bound.

To get the value create the key object with same upperbound = lowerbound = key_val;

Upvotes: 0

Kaganar
Kaganar

Reputation: 6570

Amit is correct. With ranges that do not overlap, a simple ordered data structure is sufficient. To be a bit more clear:

Sort your ranges by, say, their minimum bound. When searching, blitz through the tree checking to see if you're in the range of each node you traverse.

Upvotes: 1

amit
amit

Reputation: 178411

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.

Upvotes: 3

eugene_che
eugene_che

Reputation: 1997

You can create pairs of <interval,associated value> and build segment tree. It will work fine with overlapping intervals.

If intervals are never overlapped it still could be fine because segment tree requires less memory than the hash based solution. If the range is wide any plain structure will require a lot of memory.

EDIT: I realized that usual vector can fit you purposes better than hash in case the intervals are located close to each other.

Upvotes: 1

Related Questions