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

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

Cyanogen

I'm astounded that this question has not been improved despite almost 200K views. – Effeminate

Answer 1

Two maps. One Map<K1, V> and one Map<K2, V>. If you must have a single interface, write a wrapper class that implements said methods.

Ruction

Er, yeah, this is exactly what you proposed. Two Maps is the way to go. To extend to an arbitrary number of keys, have a method like getByKey(MetaKey mk, Object k) and then a Map<MetaKey, Map<Object, V>> internally. – Ruction

Always wrap the two maps in a class! – Dola

Why not use a single map and put two entries like put(k1,v) and put(k2,v). You can wrap these two calls in a util method. Similarly do it for delete operation also. Here I am assuming that both keys are like pairs and the order of keys doesn't matter. Like if key1=3 and key2=7, then there cannot be another entry with key1=7 and key2=3 with different value. Also a minor inconvenience with this approach is that we can't use Map with generic types incase the types of K1 and K2 are different – Olivaolivaceous

The question explicitly says that the types of the two keys are different. – Ruction

Answer 2

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 = ??

Diakinesis

I believe using generics (with the alternate collections lib) is only possible if all of your keys are of the same type. MultiKeyMap<k1,k2,v> simply does not compile. – Tuppeny

I think this unswer is wrong. There is no way to get a value from commons MultiKeyMap just by using a second key. You always need to specify both key1 and key2. Why did this answer get so many up votes??? – Surefire

@Zombies, you did not get my point. There is no way you can solve the initial problem with Commons-collections's MultiKeyMap class. If there is, please, explain it. – Surefire

@Surefire I misunderstood both the question and the answer, but ended up getting what I needed :) – Mobcap

@Surefire it got so many upvotes because it is a very useful answer, as many people (like myself) ended up on that question to find that answer. It's just the question that is wrong ;) – Tm

This solution is more like a complex (composite) unique key in DB. Where two keys are required to identify particular object. Still, as @Surefire pointed out, one key is not sufficient to perform any operation on value. – Fidget

Answer 3

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.

Magalymagan

The only problem with this is if you dont have K1. – Peres

Milhous: Yes that is a problem with this solution. – Magalymagan

Updating is a problem in my response as well. Eg. you store value "1" with K1=A and K2=B, then you store value "1" with K1=C and K2=D. Now you try to set value = "2" where K1=A. How do you know which K2 to use? Logan, your solution works, but you might also want to keep a Map<K1, K2> as well. This is probably getting a bit theoretical though, as it doesn't look like the original question takes updates into account. – Ruction

This requires two look ups for every value access, which is a 100 % performance penalty. – Foredo

@Peres I'm not sure why updating problem as described by you is applicable to Logan's solution? Here we don't need to update two maps as value updation just need to be done in map m1 e.g. if user says put(k,v) then if k,k1 entry exists in map m2 then we will put k1,v in map m2, else we will put k,v in map m1 as new entry. Also, if user request to put(k2,v) and k1,v entry already exists in map m1 then we will have to store k2,k1 in map m2 instead of storing k2,v in map m1. – Fusty

Also, storing k,k entry in map m2 for every new entry k,v getting stored in map m1 will make searching cleaner i.e. look in map m2 first and if entry exists then fetch value from map m1 – Fusty

great answer, this way I avoid having the value in 2 separate maps (which takes more space) and also if value is updated I have to update it only in one map. – Conferral

Little late to the party here, but this doesn't work for removing(K1), since you have to also remove K2 from M2. Or maybe I am mistaken? – Megasporophyll

Using this vs. two maps really depends on how big your primary map is (both in terms of number of items and bytes per item). By design maps are very efficient to lookup a value by key, no need to loop over items like a list. If the primary map is very small in size, it's fine to duplicate the map without impact to RAM in order to save a lookup. If it's large, this solution is better since it has less impact on RAM (key2-to-key1 map bytes << key1-to-value map bytes). – Doan

Answer 4

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.

Mi

In the example above, it would be better to use Guava's default factory for hash-based tables: HashBasedTable.create(). The newCustomTable() method should only be used for truly custom maps. – Azygous

Answer 5

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

Baily

this approach is more powerful than it looks like on first sight. you may even simply use an Object[] as key – Warta

Are the ellipsis arguments actual ellipses? Or are you just indicating that the user is to specify 1, 2 or up to N when they create the class. In other words, this is not a class that will handle a variable number of keys is it? – Baugher

OP doesn't want to combine keys, but use either seperately. – Effeminate

How does this work , when you want to lookup by just key1 ? – Lcm

@Lcm If I'm understanding this answer correctly, the effect is that a given value will appear in the map twice (or more), once for each key that points to that value. In this way a single map can used for both keys. Searching the map for either key will return the value. A concise form would declare Map<Object, ValueType> map ... Retrieval would be simple: map.get(someKeyForValue1), map.get(otherKeyForValue1) or map.contains(otherKeyForValue1). It does still have close to the same memory usage as the two map approach in another answer, but might be more straight-forward. – Ukrainian

Answer 6

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

Cyanogen

Answer 7

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.

Wintertide

Answer 8

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.

Plumper

This is actually the best answer for the question as asked, although I think the intent would generally be to supply two keys at the same time so it needs a method put(K1 key, K2 key, V value). I believe It could also be made generic by adding <K1,K2> to the class definition, internally using Object (or better yet ?) should be fine. – Dola

Answer 9

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

Cleave

Could you please comment on consistency of hashcode vs equals of your proposal b)? And why do you say 'overkill' for a)? Thank you – Cyanogen

hashcode seems consistent with equals to me in that any time two objects are equal their hashcodes will be equal. Not that the other way is not a requirement, although a desirable property of the hash function. Using primes is another option as per "Effective Java", e.g. k.hashCode() * 17 + t.hashCode(). More info: ibm.com/developerworks/java/library/j-jtp05273.html – Cleave

To expand on the "overkill" statement, multiKeyMap.getValueByKey1(k) doesn't seem any cleaner to me (subjectively) than key1Map.getValue(k), either in terms of verbosity or the amount of semantic information conveyed. I don't know your specific usecase though. – Cleave

Answer 10

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.

Reasonable

what about all the classes that cant be accurately represented as strings? – Marmion

You can't support getByKey1 and getByKey2 operations with this approach. – Gebler

Answer 11

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

Aurlie

Answer 12

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

Tropous

Answer 13

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.

Holism

-1 This does not answer the question. The asker does not need a compound key, but two distinct single keys that point to the same object but are managed as one entry so to say. Read the question again. MultiKeyMap is nice but only deals with compound keys. – Jello

Didn't answer OP's question, but did answer mine... – Eades

The OP doesn't want to map using keyA and keyB, rather keyA or keyB – Effeminate

Answer 14

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.

Barbaraanne

Answer 15

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

Ferrin

Answer 16

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

Estop

Answer 17

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.

Lovelace

this is a really elegant (partial) solution, but the keys could be from different types (as the question states "I need a data structure which behaves like a Map, but uses multiple (differently-typed) keys to access its values.") – Bimah

Strangely enough I didn't see your reply back in 2019. For differently-typed keys I would use... an Object? Like, Map<Object, String>? – Lovelace

This is really an elegant solution! For keys with different types, find way to convert them all to String with some prefix/suffix/transformation – Cupronickel

Answer 18

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

Ritter

Same here: this would be a problem with equality of keys when searching only for K1 or K2. – Cyanogen

In C++, you could override the equality test to be true if either member is equal, rather than the default that's true only if both are equal. Is that not possible in Java? – Matthew

It is perfectly possible, but it might not have the desired effect; if your map implementation relies upon the object's hash code, as in a HashMap, then that screws everything to hell. – Leduc

Answer 19

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.

Janae

The problem with Pair would be it's equality. If I want to search only by Key1 or only by Key2, such map would never find anything. – Cyanogen

It would not be at all hard to select the set of Pairs satisfying a K1 or K2 constraint, and thence to select the corresponding map elements. – Janae

Answer 20

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.

Crossarm

Answer 21

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

Susurration

I would advice EVERYONE against Apache Collections. Since nearly 6 years we have Java 5 with its generic types, which Apache Collections doesn't support. – Cyanogen

... and they break interface conventions quite a bit - see MultiMap (and how it would be impossible to make it a Map<K,V>) – Favourable

Actually, commons collections was forked to support generics, see this project here: sourceforge.net/projects/collections – Susurration

@ivan_ivanovich_ivanoff: See Is there a viable generic alternative to apache.commons.collections.CollectionUtils?. – Inhalant

Answer 22

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.

Ourselves

Answer 23

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

Favourable

Answer 24

I would suggest the structure

Map<K1, Map<K2, V>>

although searching for the second key might not be efficient

Labana

Answer 25

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

Gorden

Answer 26

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.

Trainee

Answer 27

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.

Hwang