Data Structures That Can Map a Range of Keys to a Value

Data structures that can map a range of keys to a value

Are your ranges non-overlapping? If so you could use a TreeMap:

TreeMap<Double, Character> m = new TreeMap<Double, Character>();
m.put(1.0, 'A');
m.put(2.9, null);
m.put(4.0, 'B');
m.put(6.0, null);
m.put(6.5, 'C');
m.put(10.0, null);

The lookup logic is a bit complicated by the fact that you probably want an inclusive lookup (i.e. 2.9 maps to 'A', and not undefined):

private static <K, V> V mappedValue(TreeMap<K, V> map, K key) {
    Entry<K, V> e = map.floorEntry(key);
    if (e != null && e.getValue() == null) {
        e = map.lowerEntry(key);
    }
    return e == null ? null : e.getValue();
}

Example:

mappedValue(m, 5) == 'B'

More results include:

0.9 null
1.0 A
1.1 A
2.8 A
2.9 A
3.0 null
6.4 null
6.5 C
6.6 C
9.9 C
10.0 C
10.1 null

Java datastructure to map multiple keys to the same value

Any Map<Integer,String> will do - you are only storing a reference to the string, not a copy of it, so it doesn't matter how long it is.

If you are building the same string value multiple times, use intern() to get the same String object for the value each time.

Looking a data structure that is a Map but in which keys can be values, values can be keys

Not in the JDK, but you can find a good BiMap implementation in the Google Collections : http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/BiMap.html

Which data structure should be used for range look up?

You could use a B-Tree: B-Tree
or maybe a Disjoint-set structure: Disjoint-set
Another S.O. user suggests a TreeMap: TreeMap
The final possibility (Possibly solving your overlapping range dilemma) is the R-Tree: R-Tree

---

R-Tree Visualization:

---

With the B-Tree, you can put a small "directory" field in each node object that would immediately be able to tell you what is contained in each Node/object. However, you have to think about what happens when the containing node becomes full of objects and you have to donate/adopt an object to or from another node.

Having said that, the Disjoint-set structure using path compression gives you an amortized runtime of O(1), and a worst-case of O(log*N)! This is also extremely easy to implement; you really only need a handful of core methods, (Union, Find, Union By Size, Find By Size), to get it running.

R-Trees would allow you to handle the case that you have over-lapping ranges, but you also sacrifice a bit of your runtime. In the worst case, you end up with a search time of O(M logMn), which is slower than a HashMap.

Data structures that can map a range of keys to a value

Are your ranges non-overlapping? If so you could use a TreeMap:

TreeMap<Double, Character> m = new TreeMap<Double, Character>();
m.put(1.0, 'A');
m.put(2.9, null);
m.put(4.0, 'B');
m.put(6.0, null);
m.put(6.5, 'C');
m.put(10.0, null);

The lookup logic is a bit complicated by the fact that you probably want an inclusive lookup (i.e. 2.9 maps to 'A', and not undefined):

private static <K, V> V mappedValue(TreeMap<K, V> map, K key) {
    Entry<K, V> e = map.floorEntry(key);
    if (e != null && e.getValue() == null) {
        e = map.lowerEntry(key);
    }
    return e == null ? null : e.getValue();
}

Example:

mappedValue(m, 5) == 'B'

More results include:

0.9 null
1.0 A
1.1 A
2.8 A
2.9 A
3.0 null
6.4 null
6.5 C
6.6 C
9.9 C
10.0 C
10.1 null

Key lookup from a data structure based on range

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.

---

Related Topics