Which data structure should be used for range look up?

Question

I was thinking to use HashMap but I think either I have to customize it or I have to create custom data structure for it. As we know HashMap stores Key-Value pair but I need a data-structure where instead of a single key I should be able to put a range. For example:

Range        Should return
0 to 50      Object1
51 to 100    Object2
90 to 150    Object3

So if user search for 10. He should be able to get Object1, if user search for 55. He should be able to get Object2, if user search for 95. He should be able to get Object2 and Object3 both.

I was thinking to put range inside each object and putting all the objects into an ArrayList or LinkedList and then I can iterate it and find the all Objects which are satisfying the input. But its time complexity will be more. For every input I have to traverse whole list. I thought for tree also but in case of overlapping range (like 51 to 100 and 90 to 150), I could not figure out how that will be helpful.

Let me know your views, my target is time complexity should be less like or near to hashmap

score 1 · Accepted Answer · edited May 23 '17 at 12:08

1

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: R-Tree Structure 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.

edited May 23 '17 at 12:08

Community

1
1

answered Mar 11 '15 at 13:48

Evan Bechtol

2,855
2
18
36

I was thinking for tree but I could not understand how overlapping of ranges will be handled in that, any Idea? – Rahul Kulshreshtha Mar 11 '15 at 13:55
@RahulKulshreshtha Check my updated post, I added the Treemap – Evan Bechtol Mar 11 '15 at 13:56
@ Evan Bechtol, I like TreeMap way suggested by another S.O. user. I am still thinking how that will work with overlapping ranges. – Rahul Kulshreshtha Mar 11 '15 at 14:12
@RahulKulshreshtha Well, if you are unable to make distinctly unique ranges, you could use an R-Tree, made for this exact approach: Please see update. – Evan Bechtol Mar 11 '15 at 15:09
@ evan Yes it seems better approach – Rahul Kulshreshtha Mar 13 '15 at 09:55

Which data structure should be used for range look up?

1 Answers1