CODEWITHSUNDEEP
hashmaphashtablerangehash
ElfsЯUs
ElfsЯUs

Reputation: 1218

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

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!

Upvotes: 14

Views: 11541

Answers (4)

Thiago Falcao
Thiago Falcao

Reputation: 5013

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

Upvotes: 7

Bhupesh Chawda
Bhupesh Chawda

Reputation: 86

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.

Upvotes: 3

Cyan
Cyan

Reputation: 13948

You problem seems closely related to BWT decoding.

If i do understand your problem correctly, you receive the first array as a stream.

Then, if you have the second array in memory, you simply need to build the "reverse array" of it. So that, for example :

Second array: 1, 9, 3, 8, 5, 4, 2, 6, 7

Becomes

Inverse second array : 1, 7, 3, 6, 5, 8, 9, 4, 2

So, now, on receiving your stream, you know immediately where to place each character.

Upvotes: 0

user97370
user97370

Reputation:

You can't use hashing, but you can sort the interval end-points and do a bisection search.

Something like this (in python, but hopefully it makes sense to you):

endpoints = [501, 901, 1056, 9956]
for x in [1, 999, 898, 55, 43, 1055, 593, 525, 3099]:
    print x, 'ABCD'[bisect.bisect_left(endpoints, x)]

Upvotes: 1

Related Questions