Dual-keyed map without additional data, is it possible?

user_5529197 0
Viewed 40

Let's assume that we have a huge map where each element need to be accessed by 2 different keys, K1 and K2. We have both K1 and K2 when we add data to the tree, but we need to retrieve data using either K1 or K2. This means both K1 and K2=ignored and K1=ignored and K2 while retrieving data refer to the data defined by K1 and K2. Is it possible to do this with a correct comparison method, without duplicating data or using secondary map for showing relationship between K1 and K2 (because these 2 methods are obvious but both need to secondary data)? What about hash maps? Because hash maps need both comparison and hash methods.

data-structures algorithm
1 Answers

You can solve this the following way.

Lets say you maintain a single Map <Key,Value> map to store your info.

Now, you when you want to store 2 keys K1 and K2 to a value. Store it in a hierarchial form with a parent-child relationship between K1 and K2.

For, example, the map structure would look like this.

K1 - Value
K2 - <child_of_identifier>K1

So, whenver you want to query using K1 or K2, you can do the following:

if(map.exists(key)){
   if(map.get(key).startsWith("<child_of_identifier>"){
       // Parse parent key value
       return map.get(parent_key)
   }else{
       return map.get(key);
   }
}

About the solution:

  • Does not duplicate data
  • Does not have another auxillary map
  • Two lookups for child keys
  • Flat storage of keys instead of merging 2 keys.
user_58412970
Related