Map with multiple keys [duplicate]

StackOverflow https://stackoverflow.com/questions/19176951

  •  30-06-2022
  •  | 
  •  

Question

I am trying to implement a map like 

Map<<key1, key2>, List<value>>

Map should contain 2 keys and corresponding value would be a list. I want to add records in same list if alteast one key value is equal For example consider following records 

R1[key1, key2]
R2[key1, null/empty] - Key1 is equal
R3[null/empty, key2] - Key2 is equal
R4[key1, key2] - Key1 and Key2 both are equal.

all should be inserted in same list like 

Key = <Key1,Key2> 
Value = <R1, R2, R3, R4>

I cant use Guava table or commons MulitKeyMap (dont want include whole library just for this) .

I tried to implement a class (which I can use as a key) which will have both key1 and key2 as attribute but implementing a effective hashcode which don't consider key1 and key2 seems bit (or may be a lot) tricky

public class Key {
    private int key1;
    private int key2;

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        // Cant include key1 and key2 in hashcode 
       /* result = prime * result + key1;
        result = prime * result + key2;*/
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Key other = (Key) obj;
        if(key2 and other.key2 both not blank/null){ // pseudo code
        if (key2 == other.key2)
            return true;
        }
        if(key1 and other.key1 both not blank/null){ //pseudo code
        if (key1 == other.key1)
            return true;
        }
        return true;
    }

}

It will work if I use the same hashcode for all but it will impact the performance as I have thousands of records.

EDIT :
I cant use nested Maps like 

Map<key1, Map< key2, List<value>>>

As some records might have only one key.

  R1[key1, key2]     - Have both keys
  R2[key1, null/empty] - Key1 is equal
  R3[null/empty, key2] - Key1 is missing and key2 is equal

Here R3 dont have key1 and hence cant be inserted in same location as R1 and R2

EDIT 2 :

I also wish to maintain the intertion order.

Was it helpful?

Solution 3

Use a TreeMap instead, this way you can make use a custom comparator for your CustomKey class instead of a Hashcode.

TreeMap<CustomKey, List<value>> map = new TreeMap<CustomKey, List<value>>(myComparator);

eta: instead of creating a comparator class you can make the CustomKey class implement Comparable

OTHER TIPS

Maps by definition have 1 key per value.

You could have a map of maps, or your key could be an object with 2 fields, but that's about as close as you can get.

Map of maps: 

Map myMap<key, Map<otherkey, value>>

Custom object

public class MapKey {
    public Object keyFirstPart;
    public Object keySecondPart;

    // You'll need to implement equals, hashcode, etc
}

Map myyMap <MapKey, value>

If the HashMap like behaviour is required, I'd create two Maps, and do the magic in handling the collections (also, I'd recommend using Sets for this...):

public class MyMap<K1, K2, V> {
  Map<K1, Collection<V>> map1;
  Map<K2, Collection<V>> map2;

  //have to add to both lists
  put(K1 k1, K2 k2, V v) {
     addToCollection(map1, k1, v);
     addToCollection(map2, k2, v);
  }

  //notice T param
  <T> void addToCollection(Map<T, Collection<V>> map, T key, V value ) {
     Collection<V> collection= map.get(key);
     if(collection==null) {
       collection= new HashSet<V>();
       map.put(key, collection);
     }
     collection.add(value );
  }

  public Collection<V> get(K1 k1, K2 k2) {
     Collection<V> toReturn = new HashSet<V>();
     Collection<V> coll1 = map1.get(k1);
     if(coll1!=null) {
        toReturn.addAll(coll1);
     }

     Collection<V> coll2 = map2.get(k2);
     if(coll2!=null) {
        toReturn.addAll(coll2);
     }

     return toReturn;
  }
}

Try this....

Create a class for the key to the Map

public class MapKey {
private Object key1;
private Object key2;

@Override
public boolean equals(Object object) {
    boolean equals = false;
    if (((MapKey) object).key1 == null && ((MapKey) object).key2 == null) {
        equals = true;
    }
    if (((MapKey) object).key1.equals(this.key1) && ((MapKey) object).key2.equals(this.key2)) {
        equals = true;
    }
    if (((MapKey) object).key1 == null && ((MapKey) object).key2.equals(this.key2)) {
        equals = true;
    }
    if (((MapKey) object).key1.equals(this.key1) && ((MapKey) object).key2 == null) {
        equals = true;
    }
    return equals;

}

@Override
public int hashCode() {
    return 1;
}

public Object getKey1() {
    return key1;
}

public void setKey1(Object key1) {
    this.key1 = key1;
}

public Object getKey2() {
    return key2;
}

public void setKey2(Object key2) {
    this.key2 = key2;
}
}

In the above class you can modify the DataTypes of key1 and key2 as required. Here's the main class that will execute the required logic

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MapWithTwoKeys {
private static final Map<MapKey, List<Object>> mapWithTwoKeys = new HashMap<MapKey,     List<Object>>();

public static void main(String[] args) {

// Create first map entry with key <A,B>.
MapKey mapKey1 = new MapKey();
mapKey1.setKey1("A");
mapKey1.setKey2("B");

List<Object> list1 = new ArrayList<Object>();
list1.add("List1 Entry");

put(mapKey1, list1);

// Create second map entry with key <A,B>, append value.
MapKey mapKey2 = new MapKey();
mapKey2.setKey1("A");
mapKey2.setKey2("B");

List<Object> list2 = new ArrayList<Object>();
list2.add("List2 Entry");

put(mapKey2, list2);

// Create third map entry with key <A,>.
MapKey mapKey3 = new MapKey();
mapKey3.setKey1("A");
mapKey3.setKey2("");

List<Object> list3 = new ArrayList<Object>();
list3.add("List3 Entry");

put(mapKey3, list3);

// Create forth map entry with key <,>.
MapKey mapKey4 = new MapKey();
mapKey4.setKey1("");
mapKey4.setKey2("");

List<Object> list4 = new ArrayList<Object>();
list4.add("List4 Entry");

put(mapKey4, list4);

// Create forth map entry with key <,B>.
MapKey mapKey5 = new MapKey();
mapKey5.setKey1("");
mapKey5.setKey2("B");

List<Object> list5 = new ArrayList<Object>();
list5.add("List5 Entry");

put(mapKey5, list5);

for (Map.Entry<MapKey, List<Object>> entry : mapWithTwoKeys.entrySet()) {
System.out.println("MapKey Key: <" + entry.getKey().getKey1() + ","
        + entry.getKey().getKey2() + ">");
System.out.println("Value: " + entry.getValue());
System.out.println("---------------------------------------");
}
}

/**
 * Custom put method for the map.
 * @param mapKey2 (MapKey... the key object of the Map).
 * @param list (List of Object... the value of the Map).
*/
private static void put(MapKey mapKey2, List<Object> list) {
if (mapWithTwoKeys.get(mapKey2) == null) {
    mapWithTwoKeys.put(mapKey2, new ArrayList<Object>());
}
mapWithTwoKeys.get(mapKey2).add(list);
}
}

The code is pretty straight forward and simple to understand. Let me know if this satisfies your requirement.

I think below solution would work for you - I have used MyKey.java object as key of the HashMap. It contains the both keys and hash code. Hash code will be used to identify list of values for different set of combination of the keys you have listed in the question. This hash code is generated when you first register both keys. It is stored against each key so that even if either of the key is null you will get same hash code.

MultiKeyMap.java =>Extends the HashMap and overrides 'put' and 'get' method. populateHashKey() - This method will generate/return same hash code for different combination of the keys you want.

NOTE: Insertion order is maintained by the Arraylist. Also all values for each key combination will be stored in same List in Map.

package test.map;

public class MyKey {

    private String myKey1;
    private String myKey2;
    private int hashKey;

    public MyKey(String key1, String key2) {
       this.myKey1 = key1;
       this.myKey2 = key2;
    }
    /**
     * @return the myKey1
     */
    public String getMyKey1() {
        return this.myKey1;
    }
    /**
     * @param tmpMyKey1 the myKey1 to set
     */
    public void setMyKey1(String tmpMyKey1) {
        this.myKey1 = tmpMyKey1;
    }
    /**
     * @return the myKey2
     */
    public String getMyKey2() {
        return this.myKey2;
    }
    /**
     * @param tmpMyKey2 the myKey2 to set
     */
    public void setMyKey2(String tmpMyKey2) {
        this.myKey2 = tmpMyKey2;
    }
    /**
     * Returns the hash key.
     */
    @Override
    public int hashCode() {
        return this.hashKey;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        MyKey other = (MyKey) obj;
        if(checkEqual(this.myKey1, other.myKey1) 
                || checkEqual(this.myKey2, other.myKey2)) {
            return true;
        }

        return false;
    }
    /*
     * Checks whether key1 equals key2.
     */
    private boolean checkEqual(String key1, String key2) {
        if(key1 != null && key2 != null) {
            return key1.equals(key2);
        }
        return false;
    }
    /**
     * @return the hashKey
     */
    public int getHashKey() {
        return this.hashKey;
    }
    /**
     * @param tmpHashKey the hashKey to set
     */
    public void setHashKey(int tmpHashKey) {
        this.hashKey = tmpHashKey;
    }
}

MultiKeyMap.java - 

  package test.map;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MultiKeyMap extends HashMap<MyKey, List<String>>{

    private static final long serialVersionUID = 3523468186955908397L;
    Map<String, Integer> hashKeyMap = new HashMap<String, Integer>();

    /*
     * Adds single value in the List of values against the key
     */
    public List<String> addValue(MyKey tmpKey, String tmpValue) {
        populateHashKey(tmpKey);
        List<String> orgValue = null;
        if(tmpKey.getHashKey() != -1) {
            orgValue = super.get(tmpKey);
            if(orgValue == null) {
                orgValue = new ArrayList<String>();
                super.put(tmpKey, orgValue);
            }
            orgValue.add(tmpValue);
        }
        return orgValue;
    }

    @Override
    public List<String> put(MyKey tmpKey, List<String> tmpValue) {
        populateHashKey(tmpKey);
        List<String> orgValue = null;
        if(tmpKey.getHashKey() != -1) {
            orgValue = super.get(tmpKey);
            if(orgValue == null) {
                orgValue = new ArrayList<String>();
                super.put(tmpKey, orgValue);
            }
            orgValue.addAll(tmpValue);
        }
        return orgValue;
    }

    @Override
    public List<String> get(Object tmpKey) {
        if(!(tmpKey instanceof MyKey)) {
            return null;
        }
        MyKey key = (MyKey) tmpKey;
        populateHashKey(key);
        return super.get(key);
    }
    /**
     * Populates the hashKey generated for the MyKey combination. If the both Key1 and Key 2 are not null and its hash key is not generated
     * earlier then it will generate the hash key using both keys and stores it in class level map 'hashKeyMap' against both keys.
     * @param tmpKey
     */
    public void populateHashKey(MyKey tmpKey) {
        int hashKey = -1;
        if(tmpKey.getMyKey1() != null && this.hashKeyMap.containsKey(tmpKey.getMyKey1()+"_")) {
            hashKey = this.hashKeyMap.get(tmpKey.getMyKey1()+"_");
        } else if(tmpKey.getMyKey2() != null && this.hashKeyMap.containsKey("_"+tmpKey.getMyKey2())) {
            hashKey = this.hashKeyMap.get("_"+tmpKey.getMyKey2());
        }
        /*
         * Assumption - While insertion you will always add first value with Key1 and Key2 both as not null. Hash key will be build only
         * when both keys are not null and its not generated earlier.
         */
        if(hashKey == -1 && tmpKey.getMyKey1() != null && tmpKey.getMyKey2() != null) {
            hashKey = buildHashKey(tmpKey);
            this.hashKeyMap.put(tmpKey.getMyKey1()+"_", hashKey);
            this.hashKeyMap.put("_"+tmpKey.getMyKey2(), hashKey);
        }
        tmpKey.setHashKey(hashKey);
    }

    public int buildHashKey(MyKey tmpKey) {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((tmpKey.getMyKey1() == null) ? 0 : tmpKey.getMyKey1().hashCode());
        result = prime * result + ((tmpKey.getMyKey1() == null) ? 0 : tmpKey.getMyKey1().hashCode());
        return result;
    }
}

Test class - 

import test.map.MultiKeyMap;
import test.map.MyKey;

public class TestMultiKeyMap {

    public static void main(String[] args) {

        System.out.println("=====Add values for each type of key==========");
        MyKey regKey = new MyKey("Key1", "Key2");
        MultiKeyMap myMap = new MultiKeyMap();
        //Register the MyKey having both keys as NOT null.
        System.out.println("Entry 1:"+myMap.addValue(regKey, "Key Reg"));

        MyKey key1 = new MyKey("Key1", null);
        //Add value against MyKey with only Key2
        System.out.println("Entry 2:"+myMap.addValue(key1, "Key1"));

        MyKey key2 = new MyKey(null, "Key2");
        //Add value against MyKey with only Key1
        System.out.println("Entry 3:"+myMap.addValue(key2, "Key2"));

        MyKey bothKey = new MyKey("Key1", "Key2");
        //Add value against MyKey with only Key1
        System.out.println("Entry 4:"+myMap.addValue(bothKey, "both keys"));

        System.out.println("=====Retrieve values for each type of key==========");
        MyKey getKey1 = new MyKey("Key1", null);
        System.out.println("Values for Key1:"+myMap.get(getKey1));

        MyKey getKey2 = new MyKey(null, "Key2");
        System.out.println("Values for Key2:"+myMap.get(getKey2));

        MyKey getBothKey = new MyKey("Key1", "Key2");
        System.out.println("Values for both keys:"+myMap.get(getBothKey));
    }

}

Output - 

=====Add values for each type of key==========
Entry 1:[Key Reg]
Entry 2:[Key Reg, Key1]
Entry 3:[Key Reg, Key1, Key2]
Entry 4:[Key Reg, Key1, Key2, both keys]
=====Retrieve values for each type of key==========
Values for Key1:[Key Reg, Key1, Key2, both keys]
Values for Key2:[Key Reg, Key1, Key2, both keys]
Values for both keys:[Key Reg, Key1, Key2, both keys]

Check hash code of key1 only, if it matches, then we test in equals method anyways.

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

@Override
public boolean equals(Object obj) {
Key k = (Key)obj;
// Generic equals code goes here
    if(this.key1.equals(k.key1) && this.key2.equals(k.key2) )
        return true;
    return false;
}

Basically the idea to achieve this is to map the keys by the value itself.

So you could have an internal map which does this (here I have a set of keys instead of just 2).

Map<V, Set<K>> keySetMap = new HashMap<V, Set<K>>();

So your Map implementation could look something like this:

public class MultiKeyMap<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;

    private Map<V, Set<K>> keySetMap = new HashMap<V, Set<K>>();

    @Override
    public V put(K key, V value) {
        V v = null;

        Set<K> keySet = keySetMap.get(value);
        if(keySet == null) {
            keySet = new LinkedHashSet<K>();
            keySetMap.put(value, keySet);
        }

        keySet.add(key);
        v = super.put(key, value);

        // update the old keys to reference the new value
        Set<K> oldKeySet =  keySetMap.get(v);
        if(oldKeySet != null) {
            for(K k : oldKeySet) {
                super.put(k, value);
            }
        }

        return v;
    }
}

This works fine for simple (immutable) Objects:

@Test
public void multiKeyMapString() {
    MultiKeyMap<String, String> m = new MultiKeyMap<String, String>();

    m.put("1", "A");
    m.put("2", "B");

    for(Entry<String, String> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    m.put("3", "A");

    System.out.println("----");
    for(Entry<String, String> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    m.put("4", "C");

    System.out.println("----");
    for(Entry<String, String> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    m.put("3", "D");

    System.out.println("----");
    for(Entry<String, String> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    System.out.println("----");
    System.out.println("values=" + m.values());

    System.out.println();
    System.out.println();
}

with the the test above, the output would look like 

K=1, V=A
K=2, V=B
----
K=1, V=A
K=2, V=B
K=3, V=A
----
K=1, V=A
K=2, V=B
K=3, V=A
K=4, V=C
----
K=1, V=D
K=2, V=B
K=3, V=D
K=4, V=C
----
values=[D, B, C]

As you see in last output, the key 1 now maps the value D because the value previously mapped by 3 was the same as the one mapped by 1 in the step before.

But it gets tricky when you want to put a list (or any mutable object) in your map, because if you change the list (add/remove an element) then the list will have another hashCode as the one used to map the previous keys:

@Test
public void multiKeyMapList() {
    List<String> l = new ArrayList<String>();
    l.add("foo");
    l.add("bar");
    MultiKeyMap<String, List<String>> m = new MultiKeyMap<String, List<String>>();

    m.put("1", l);
    m.put("2", l);

    for(Entry<String, List<String>> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    m.get("1").add("foobar");
    m.put("3", l);

    System.out.println("----");
    for(Entry<String, List<String>> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    l = new ArrayList<String>();
    l.add("bla");

    m.put("4", l);

    System.out.println("----");
    for(Entry<String, List<String>> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    m.put("3", l);

    System.out.println("----");
    for(Entry<String, List<String>> e : m.entrySet()) {
        System.out.println("K=" + e.getKey() + ", V=" + e.getValue().toString());
    }

    System.out.println("----");
    System.out.println("values=" + m.values());
}

The test above will output something like this:

K=1, V=[foo, bar]
K=2, V=[foo, bar]
----
K=1, V=[foo, bar, foobar]
K=2, V=[foo, bar, foobar]
K=3, V=[foo, bar, foobar]
----
K=1, V=[foo, bar, foobar]
K=2, V=[foo, bar, foobar]
K=3, V=[foo, bar, foobar]
K=4, V=[bla]
----
K=1, V=[foo, bar, foobar]
K=2, V=[foo, bar, foobar]
K=3, V=[bla]
K=4, V=[bla]
----
values=[[foo, bar, foobar], [bla]]

As you see the value mapped by 1 and 2 has not been updated, after only the key 3 is turned to map another value. The reason is that the hashCode resultng from [foo, bar] is different from the one of [foo, bar, foobar] which causes Map#get to not return the correct result. To get over this you need to get set of keys by comparing to the actual value.

public class MultiKeyMap<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;

    private Map<V, Set<K>> keySetMap = new HashMap<V, Set<K>>();

    @Override
    public V put(K key, V value) {
        V v = null;

        Set<K> keySet = keySetMap.get(value);
        if (keySet == null) {
            keySet = new LinkedHashSet<K>();
            keySetMap.put(value, keySet);
        }

        keySet.add(key);
        v = super.put(key, value);

        // update the old keys to reference the new value
        for (K k : getKeySetByValue(v)) {
            super.put(k, value);
        }

        return v;
    }

    @Override
    public Collection<V> values() {
        // distinct values
        return new LinkedHashSet<V>(super.values());
    }

    private Set<K> getKeySetByValue(V v) {
        Set<K> set = null;
        if (v != null) {
            for (Map.Entry<V, Set<K>> e : keySetMap.entrySet()) {
                if (v.equals(e.getKey())) {
                    set = e.getValue();
                    break;
                }
            }
        }
        return set == null ? Collections.<K> emptySet() : set;
    }
}

Now running both test again gives the following output:

For simple (immutable) Objects

K=1, V=A
K=2, V=B
----
K=1, V=A
K=2, V=B
K=3, V=A
----
K=1, V=A
K=2, V=B
K=3, V=A
K=4, V=C
----
K=1, V=D
K=2, V=B
K=3, V=D
K=4, V=C
----
values=[D, B, C]

For object that can change

K=1, V=[foo, bar]
K=2, V=[foo, bar]
----
K=1, V=[foo, bar, foobar]
K=2, V=[foo, bar, foobar]
K=3, V=[foo, bar, foobar]
----
K=1, V=[foo, bar, foobar]
K=2, V=[foo, bar, foobar]
K=3, V=[foo, bar, foobar]
K=4, V=[bla]
----
K=1, V=[bla]
K=2, V=[bla]
K=3, V=[bla]
K=4, V=[bla]
----
values=[[bla]]

I hope this helps you find a way to implement your Map. You could instead of extending an existing implementation implement the Map interface so that you can provide an implentation for all it's methods with respect to their contracts and have the implementation of your choice as a member to handle the actual mapping.

Please Use the excellent helper classes EqualsBuilder and HashCodeBuilder from the Apache Commons Lang library. An example:

public class Person {
    private String name;
    private int age;
    // ...

    public int hashCode() {
        return new HashCodeBuilder(17, 31). // two randomly chosen prime numbers
            // if deriving: appendSuper(super.hashCode()).
            append(name).
            append(age).
            toHashCode();
    }

    public boolean equals(Object obj) {
        if (obj == null)
            return false;
        if (obj == this)
            return true;
        if (!(obj instanceof Person))
            return false;

        Person rhs = (Person) obj;
        return new EqualsBuilder().
            // if deriving: appendSuper(super.equals(obj)).
            append(name, rhs.name).
            append(age, rhs.age).
            isEquals();
    }
}

Source

Create another Map that holds the relationship key->intermediateKey. The intermediate key may be a GUID or something else that is automatically generated and guaranteed to be unique.

  Map<String, GUID> first = new HashMap<String, GUID>();
  first.put(key1, guid1);
  first.put(key2, guid1);

  Map<GUID, ValueType> second = new HashMap<GUID, ValueType>();
  second.put(guid1, value1);

Alternatively (although I find it far more complicated, and less flexible), you could play with the keys. If key1.equals(key2) (and, consequently, key2.equals(key1) && (key1.hashCode() == key2.hashCode) thenMap.get(key1)will return the same value thanMap.get(key2)`.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top