How to implement a Map with multiple keys

Question

I need a data structure which behaves like a Map   but uses multiple  differently-typed  keys to access its values   Let s not be too general  let s say two keys   Keys are guaranteed to be unique   Something like   MyMap lt K1 K2 V gt        With methods like   getByKey1 K1 key     getByKey2 K2 key     containsKey1 K1 key     containsKey2 K2 key       Do you have any suggestions   The only thing I can think of is  Write a class which uses two Maps internally   EDIT Some people suggest me to use a tuple  a pair  or similar as a key for Java s Map  but this would not work for me  I have to be able  as written above  to search values by only one of the two keys specified  Maps use hash codes of keys and check for their equality

User · Answer

It would seem to me that the methods you want in your question are supported directly by Map. The one(s) you'd seem to want are

put(K1 key, K2 key, V value)
put(K1 key, V value)
put(K2 key, V value)

Note that in map, get() and containsKey() etc all take Object arguments. There's nothing stopping you from using the one get() method to delegate to all the composite maps that you combine (as noted in your question and other answers). Perhaps you'd need type registration so you don't get class casting problems (if they're special + implemented naively.

A typed based registration would also allow you to retrieve the "correct" map to be used:

Map<T,V> getMapForKey(Class<T> keyClass){
  //Completely naive implementation - you actually need to 
  //iterate through the keys of the maps, and see if the keyClass argument
  //is a sub-class of the defined map type.  And then ordering matters with 
  //classes that implement multiple interfaces...
  Map<T,V> specificTypeMap = (Map<T,V) maps.get(keyClass);
  if (specificTypeMap == null){
     throw new IllegalArgumentException("There is no map keyed by class" + keyClass);
  }
  return maps.get(keyClass);
}

V put(Object key, V value) {
  //This bit requires generic suppression magic - but 
  //nothing leaves this class and you're testing it right? 
  //(You can assert that it *is* type-safe)
  Map map = getMapForKey(key.getClass());
  map.put(object, key);
}

void put(Object[] keys, V value) { //Or put(V value, Object ... keys)
   //Might want to catch exceptions for unsupported keys and log instead?
   .....
}

Just some ideas...

User · Answer

A dirty and a simple solution  if you use the maps just for sorting lets say  is to add a very small value to a key until the value does not exist  but do not add the minimum  for example Double MIN VALUE  because it will cause a bug   Like I said  this is a very dirty solution but it makes the code simpler

User · Answer

I used such implementation for multiple key objects  It allows me to use innumerable number of keys for map  It s scaleable and quite simple  But it has limitations  keys are ordered according to order of arguments in constructor and it would not work with 2D arrays  because of using Arrays equals    To fix it - you could use Arrays deepEquals     Hope it will help you  If you know any reason why it could not be used as a solution for such issues - please  let me know   public class Test        private static Map lt InnumerableKey  Object gt  sampleMap   new HashMap lt InnumerableKey  Object gt          private static class InnumerableKey            private final Object   keyParts           private InnumerableKey Object    keyParts                this keyParts   keyParts                      Override         public boolean equals Object o                if  this    o  return true              if    o instanceof InnumerableKey   return false               InnumerableKey key    InnumerableKey  o               if   Arrays equals keyParts  key keyParts   return false               return true                      Override         public int hashCode                 return keyParts    null   Arrays hashCode keyParts    0                       public static void main String    args            boolean keyBoolean   true          double keyDouble   1d          Object keyObject   new Object             InnumerableKey doubleKey   new InnumerableKey keyBoolean  keyDouble           InnumerableKey tripleKey   new InnumerableKey keyBoolean  keyDouble  keyObject            sampleMap put doubleKey   DOUBLE KEY            sampleMap put tripleKey   TRIPLE KEY                prints  DOUBLE KEY          System out println sampleMap get new InnumerableKey true  1d                prints  TRIPLE KEY          System out println sampleMap get new InnumerableKey true  1d  keyObject                prints null         System out println sampleMap get new InnumerableKey keyObject  1d  true

User · Answer

See Google Collections   Or  as you suggest  use a map internally  and have that map use a Pair   You ll have to write or find Pair lt    it s pretty easy but not part of the standard Collections

User · Answer

Yet another solution is to use Google s Guava  import com google common collect Table  import com google common collect HashBasedTable   Table lt String  String  Integer gt  table   HashBasedTable create      The usage is really simple   String row    a   String column    b   int value   1   if   table contains row  column         table put row  column  value      System out println  value       table get row  column      The method HashBasedTable create   is basically doing something like this   Table lt String  String  Integer gt  table   Tables newCustomTable          Maps  lt String  Map lt String  Integer gt  gt newHashMap            new Supplier lt Map lt String  Integer gt  gt          public Map lt String  Integer gt  get             return Maps newHashMap                if you re trying to create some custom maps  you should go for the second option  as  Karatheodory suggests  otherwise you should be fine with the first one

User · Answer

Proposal  as suggested by some answerers   public interface IDualMap lt K1  K2  V gt                    return Unmodifiable version of underlying map1            Map lt K1  V gt  getMap1                    return Unmodifiable version of underlying map2            Map lt K2  V gt  getMap2         void put K1 key1  K2 key2  V value       public final class DualMap lt K1  K2  V gt          implements IDualMap lt K1  K2  V gt         private final Map lt K1  V gt  map1   new HashMap lt K1  V gt          private final Map lt K2  V gt  map2   new HashMap lt K2  V gt           Override     public Map lt K1  V gt  getMap1             return Collections unmodifiableMap map1               Override     public Map lt K2  V gt  getMap2             return Collections unmodifiableMap map2               Override     public void put K1 key1  K2 key2  V value            map1 put key1  value           map2 put key2  value

User · Answer

Another possile solution providing the possibility of more complicated keys can be found here  http   insidecoffe blogspot de 2013 04 indexable-hashmap-implementation html

User · Answer

Define a class that has an instance of K1 and K2  Then use that as class as your key type

User · Answer

How about something like this   His statement says that keys are Unique  so saving the same value objects against different keys is quite possible and when you send any key matching the said value  we would be able to get back to the value object   See code below   A value Object Class       public class Bond       public Bond             System out println  The Name is Bond    James Bond                 private String name      public String getName     return name       public void setName String name    this name   name       public class HashMapValueTest        public static void main String   args             String key1    A           String key2    B           String key3    C            Bond bond   new Bond            bond setName  James Bond Mutual Fund             Map lt String  Bond gt  bondsById   new HashMap lt  gt              bondsById put key1  bond           bondsById put key2  bond           bondsById put key3  bond            bond setName  Alfred Hitchcock             for  Map Entry lt String  Bond gt  entry   bondsById entrySet                  System out println entry getValue   getName                           The result is   The Name is Bond    James Bond     Alfred HitchCock  Alfred HitchCock  Alfred HitchCock

User · Answer

all multy key s probably fail  cause the put  key1  key2   val  and the get  null  key2   end up using the equals of  key1  key2  and  null  key2   If the backing map doesnt contains hash buckets per key then lookups are real slow to   i think the way to go is using a index decorator  see the key1  key2 examples above  and if the extra index key s are properties of the stored value you can use the property name s and reflection to build the secondairy maps when you put key  val  and add an extra method get propertyname  propertyvalue  to use that index   the return type of the get propertyname  propertyvalue  could be a Collection so even none unique key s are indexed

User · Answer

Why not just drop the requirement that the key has to be a specific type  i e  just use Map lt Object V gt    Sometimes generics just isn t worth the extra work

User · Answer

Commons-collections provides just what you are looking for   https   commons apache org proper commons-collections apidocs   Looks like now the commons-collections is typed   A typed version can be found at   https   github com megamattron collections-generic  This will exactly support your use case    MultiKeyMap lt k1 k2     kn v gt  multiMap

User · Answer

Sounds like a Python tuple   Following in that spirit  you can create an immutable class of your own devising that implements Comparable and you ll have it

User · Answer

I created this to solve a similar issue    Datastructure  import java util ArrayList  import java util HashMap  import java util Iterator   public class HashBucket       HashMap lt Object  ArrayList lt Object gt  gt  hmap       public HashBucket             hmap   new HashMap lt Object  ArrayList lt Object gt  gt                public void add Object key  Object value            if  hmap containsKey key                 ArrayList al   hmap get key               al add value             else               ArrayList al   new ArrayList lt Object gt                 al add value               hmap put key  al                        public Iterator getIterator Object key            ArrayList al   hmap get key           return hmap get key  iterator                Retrieve a value     Note  Cast the Object back to the inserted type  In my case it was my Event Object       public Iterator getIterator Object key            ArrayList al   hmap get key           if  al    null                return hmap get key  iterator              else               List lt Object gt  empty   Collections emptyList                return empty iterator                       Inserting  Event e1   new Event    e1 setName  Bob    e1 setTitle  Test    map add  key  e1

User · Answer

I would suggest the structure   Map lt K1  Map lt K2  V gt  gt    although searching for the second key might not be efficient

User · Answer

sol  cancatenate both keys and make a final key  use this as key    for key values     concatenate ket-1  and key-2 with a come       in beetween  use this as original key    key   key-1         key-2   myMap put key value     similarly while retriving values

User · Answer

Sounds like your solution is quite plausible  for this need  I honestly don t see a problem with it if your two key types are really distinct  Just makes ure you write your own implementation for this and deal with synchronization issues if needed

User · Answer

Both MultiMap or MultiKeyMap from Commons or Guava will work   However  a quick and simple solution could be to extend Map class buy handling a composite key yourself  considering that keys are of primitive type

User · Answer

If keys are unique then there is no need for 2 maps  map of maps  mapOfWhateverThereIs  There needs to be only 1 single map and just a simple wrapper method that would put your keys and value into that map   Example   Map lt String  String gt  map   new HashMap lt  gt      public void addKeysAndValue String key1  String key2  String value       map put key1  value       map put key2  value      public void testIt        addKeysAndValue  behemoth    hipopotam    hornless rhino        Then use your map as you normally would  You don t even need those fancy getByKeyN and containsKeyN

User · Answer

I m still going suggest the 2 map solution  but with a tweest  Map lt K2  K1 gt  m2  Map lt K1  V gt   m1    This scheme lets you have an arbitrary number of key  aliases    It also lets you update the value through any key without the maps getting out of sync

User · Answer

I recommend something like this       public class MyMap          Map lt Object  V gt  map   new HashMap lt Object  V gt             public V put K1 key V value           return map put key  value                  public V put K2 key V value           return map put key  value                  public V get K1 key               return map get key                  public V get K2 key               return map get key                    Same for conatains          Then you can use it like  myMap put k1 value  or myMap put k2 value   Advantages  It is simple  enforces type safety  and doesn t store repeated data  as the two maps solutions do  though still store duplicate values   Drawbacks  Not generic

User · Answer

Two maps   One Map lt K1  V gt  and one Map lt K2  V gt    If you must have a single interface  write a wrapper class that implements said methods

User · Answer

How about using a trie data structure     http   en wikipedia org wiki Trie  The root of the trie will by blank  The first level siblings will be your primary keys of the map  the second level siblings will be your secondary keys and the third level will be the terminal nodes which will have the value along will null to indicate termination of that branch  You can also add more than two keys using the same scheme   Look up is simple DFS

User · Answer

Depending on how it will be used  you can either do this with two maps Map lt K1  V gt  and Map lt K2  V gt  or with two maps Map lt K1  V gt  and Map lt K2  K1 gt   If one of the keys is more permanent than the other  the second option may make more sense

User · Answer

I can see the following approaches   a  Use 2 different maps  You can wrap them in a class as you suggest  but even that might be an overkill  Just use the maps directly  key1Map getValue k1   key2Map getValue k2   b  You can create a type-aware key class  and use that  untested    public class Key     public static enum KeyType   KEY 1  KEY 2      public final Object k    public final KeyType t     public Key Object k  KeyType t        this k   k      this t  t         public boolean equals Object obj        KeyType kt    KeyType obj      return k equals kt k   amp  amp  t    kt t         public int hashCode        return k hashCode     t hashCode            By the way  in a lot of common cases the space of key1 and the space of key2 do not intersect  In that case  you don t actually need to do anything special  Just define a map that has entries key1  gt v as well as key2  gt v

User · Answer

What about you declare the following  Key  class   public class Key      public Object key1  key2       keyN      public Key Object key1  Object key2       Object keyN          this key1   key1        this key2   key2                  this keyN   keyN            Override       public boolean equals Object obj          if    obj instanceof Key           return false        Key ref    Key  obj        return this key1 equals ref key1   amp  amp             this key2 equals ref key2   amp  amp                          this keyN equals ref keyN             Override     public int hashCode             return key1 hashCode     key2 hashCode                        keyN hashCode               Declaring the Map  Map lt Key  Double gt  map   new HashMap lt Key Double gt       Declaring the key object  Key key   new Key key1  key2       keyN    Filling the map  map put key  new Double 0     Getting the object from the map  Double result   map get key

User · Answer

If you intend to use combination of several keys as one  then perhaps apache commnons MultiKey is your friend  I don t think it would work one by one though

[java] How to implement a Map with multiple keys?

Examples related to java

Examples related to data-structures