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

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<K1,K2,V> ...

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.

Why not just drop the requirement that the key has to be a specific type, i.e. just use Map<Object,V>.

Sometimes generics just isn't worth the extra work.

I recommend something like this:

    public class MyMap {

      Map<Object, V> map = new HashMap<Object, V>();


      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.

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) && 
          this.key2.equals(ref.key2) &&
          ...
          this.keyN.equals(ref.keyN)
   }

    @Override
    public int hashCode() {
        return key1.hashCode() ^ key2.hashCode() ^ 
            ... ^ keyN.hashCode();
    }

}

Declaring the Map

Map<Key, Double> map = new HashMap<Key,Double>();

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);

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

I would suggest the structure

Map<K1, Map<K2, V>>

although searching for the second key might not be efficient

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.

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<InnumerableKey, Object> sampleMap = new HashMap<InnumerableKey, Object>();

    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)));
    }
}

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.

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<String, Bond> bondsById = new HashMap<>();

        bondsById.put(key1, bond);
        bondsById.put(key2, bond);
        bondsById.put(key3, bond);

        bond.setName("Alfred Hitchcock");

        for (Map.Entry<String, Bond> entry : bondsById.entrySet()) {
            System.out.println(entry.getValue().getName());
        }

    }

}

The result is:

The Name is Bond... James Bond...

Alfred HitchCock

Alfred HitchCock

Alfred HitchCock

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<>; it's pretty easy but not part of the standard Collections.

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<String, String> map = new HashMap<>();

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.

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<Object, ArrayList<Object>> hmap;

    public HashBucket() {
        hmap = new HashMap<Object, ArrayList<Object>>();
    }

    public void add(Object key, Object value) {
        if (hmap.containsKey(key)) {
            ArrayList al = hmap.get(key);
            al.add(value);
        } else {
            ArrayList al = new ArrayList<Object>();
            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<Object> empty = Collections.emptyList();
            return empty.iterator();
        }

    }

Inserting

Event e1 = new Event();
e1.setName("Bob");
e1.setTitle("Test");
map.add("key",e1);

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.

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<k1,k2,...,kn,v> multiMap = ??

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.

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.

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....

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) && 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=>v as well as key2=>v

Proposal, as suggested by some answerers:

public interface IDualMap<K1, K2, V> {

    /**
    * @return Unmodifiable version of underlying map1
    */
    Map<K1, V> getMap1();

    /**
    * @return Unmodifiable version of underlying map2
    */
    Map<K2, V> getMap2();

    void put(K1 key1, K2 key2, V value);

}

public final class DualMap<K1, K2, V>
        implements IDualMap<K1, K2, V> {

    private final Map<K1, V> map1 = new HashMap<K1, V>();

    private final Map<K2, V> map2 = new HashMap<K2, V>();

    @Override
    public Map<K1, V> getMap1() {
        return Collections.unmodifiableMap(map1);
    }

    @Override
    public Map<K2, V> getMap2() {
        return Collections.unmodifiableMap(map2);
    }

    @Override
    public void put(K1 key1, K2 key2, V value) {
        map1.put(key1, value);
        map2.put(key2, value);
    }
}

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..

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...

I'm still going suggest the 2 map solution, but with a tweest

Map<K2, K1> m2;
Map<K1, V>  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.

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

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.

Yet another solution is to use Google's Guava

import com.google.common.collect.Table;
import com.google.common.collect.HashBasedTable;

Table<String, String, Integer> 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<String, String, Integer> table = Tables.newCustomTable(
        Maps.<String, Map<String, Integer>>newHashMap(),
        new Supplier<Map<String, Integer>>() {
    public Map<String, Integer> 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.

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