Tuesday, December 14, 2010

Multi Key Maps.. myth or reality


What the heck ? Never heard of these, is it possible to access the same entry with multiple keys? Just somedays back thought of this, and said y not .

Our good old friend Map allows us to have an unique key which is mapped to a value. To access a value we must have an index which is unique. But what if we want to access the same entry but using multiple indices we need a slightly different mechanism.

Ok , so here I would discuss a way to achieve it. And we will put into use something we learned in school and that is Prime Number. These are basically the numbers that are divisible by themselves except 1.

Euclid’s Fundamental Theorem of Arithmetic states that Every integer can be written as a product of primes in an essentially unique way. And Euclid's second theorem states that the number of prime numbers is infinite.

Now, as per the first rule we conclude that prime numbers are the ones upon multiplication of which we can generate any number. So, can we say they are the basic components of any number.

Based on this we try to create a key of a map. Lets say we want to create a map in which a value can be accessed using 2 keys.
Here are the various keys that we are going to use and the index values they generate.
2*3 = 6
5*7 = 35
11*13 = 143 .. and so on. Note that each of the index has only 2 factors except 1.

Now we create a map from integer to a string with the above indices
6 --> “Hello”
35 --> “ World”
143 ---> “Sanjiv”

Say in c++, the search code will look something like this.

map my_map.begin ;
string get(int key)
{
for(map::iterator iter = my_map.begin(); iter != my_map.end(); iter++)

{

if(iter->first % key == 0) //Key matches with the index

return iter->second;

}

}

It looks so dumb that we are have to traverse the whole map to find the match. This completely denies the whole purpose of an associated storage.

I hope I will be able to come up with a better way to do the same.