How to hash a range of numbers to a single position in the hash table

Question

Basically I have a 2xN array of ints to ints, which indicates from which position to which position of an objects location. Then I have a second array of ints and I want to find which ints land on which object. So for example:

First array

A: 0 - 500

B: 501 - 900

C: 901 - 1055

D: 1056 - 9955 etc.

Second array: 1, 999, 3, 898, 55, 43, 1055, 593, 525, 3099, etc.

This should return the A, C, A, B, A, A, C, B, B, D, etc.

What I am trying to figure out is if there is a way to hash the first array, using some hash functions, such that when hashing the second array I will get a collision if it falls within the range of an object. Any ideas how to do this or if its possible?

Thanks!

Answer 1

You can use a NavigableMap.

Example Code:

NavigableMap<Integer, String> map = new TreeMap<Integer, String>();
map.put(0, "A");
map.put(501, "B");
map.put(901, "C");
map.put(1056, "D");

System.out.println(map.floorEntry(1).getValue());
System.out.println(map.floorEntry(999).getValue());
System.out.println(map.floorEntry(3).getValue());
System.out.println(map.floorEntry(898).getValue());

Output:

A C A B

Answer 2

You can use some data structure like an interval tree to store the first array.

http://en.wikipedia.org/wiki/Interval_tree

Then when you go through the second array, you can simply query the tree for a matching interval. This way, you will require O(log n) time to query each element of the second array.