Карта с несколькими ключами

Question

Я пытаюсь реализовать карту как

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

Карта должна содержать 2 ключа и соответствующее значение будет список. Я хочу добавить записи в один и тот же список, если значение одного ключа равно, например. Рассмотрим следующие записи

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.

все должны быть вставлены в один и тот же список, как

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

Я не могу использовать таблицу Гуавы или общие MulitKeyMap (не хочу включать целую библиотеку только для этого) .

Я попытался реализовать класс (который я могу использовать в качестве ключа), который будет иметь оба key1 а также key2 как атрибут, но реализация эффективного хеш-кода, который не учитывает key1 и key2, кажется немного (или может быть много) хитрым

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

}

Это будет работать, если я использую один и тот же хэш-код для всех, но это повлияет на производительность, так как у меня есть тысячи записей.

---

РЕДАКТИРОВАТЬ:
Я не могу использовать вложенные Карты, такие как

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

Поскольку некоторые записи могут иметь только один ключ.

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

Здесь R3 не имеет ключа1 и, следовательно, не может быть вставлен в то же место, что и R1 и R2

---

РЕДАКТИРОВАТЬ 2:

Я также хочу поддерживать порядок перерыва.

Answer 1

Вместо этого используйте TreeMap, таким образом вы можете использовать собственный компаратор для своего класса CustomKey вместо хэш-кода.

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

eta: вместо создания класса компаратора вы можете заставить класс CustomKey реализовать Comparable

Answer 2

Карты по определению имеют 1 ключ на значение.

У вас может быть карта карт, или ваш ключ может быть объектом с 2 полями, но это как можно ближе.

Карта карт:

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

Пользовательский объект

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

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

Map myyMap <MapKey, value>

Answer 3

Если требуется поведение, подобное HashMap, я бы создал две карты и использовал магию для обработки коллекций (также я бы порекомендовал использовать наборы для этого...):

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

Answer 4

Попробуй это....

Создайте класс для ключа к карте

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

В приведенном выше классе вы можете изменить DataTypes key1 и key2 по мере необходимости. Вот основной класс, который будет выполнять необходимую логику

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

Код довольно прост и понятен. Дайте мне знать, если это удовлетворяет вашим требованиям.

Answer 5

Я думаю, что решение ниже будет работать для вас - я использовал объект MyKey.java в качестве ключа HashMap. Он содержит оба ключа и хэш-код. Хеш-код будет использоваться для идентификации списка значений для различного набора комбинаций клавиш, которые вы перечислили в вопросе. Этот хэш-код генерируется при первой регистрации обоих ключей. Он сохраняется для каждого ключа, так что даже если любой из ключей имеет значение null, вы получите тот же хеш-код.

MultiKeyMap.java => Расширяет HashMap и переопределяет методы put и get. populateHashKey() - Этот метод будет генерировать / возвращать один и тот же хеш-код для различных комбинаций клавиш, которые вы хотите.

ПРИМЕЧАНИЕ. Порядок вставки поддерживается Arraylist. Также все значения для каждой комбинации клавиш будут сохранены в одном и том же списке на карте.

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

Тестовый класс -

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

}

Выход -

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

Answer 6

По сути, идея этого заключается в том, чтобы сопоставить ключи по значению.

Таким образом, у вас может быть внутренняя карта, которая делает это (здесь у меня есть набор ключей вместо 2).

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

Так что ваши Map Реализация может выглядеть примерно так:

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

Это прекрасно работает для простых (неизменяемых) объектов:

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

с тестом выше, результат будет выглядеть

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]

Как вы видите в последнем выводе, ключ 1 теперь отображает значение D потому что значение, ранее сопоставленное 3 был такой же, как тот, который нанес на карту 1 на шаге раньше.

Но это становится сложно, когда вы хотите поместить список (или любой изменяемый объект) в вашу карту, потому что если вы измените список (добавьте / удалите элемент), то список будет иметь другой hashCode как тот, который использовался для сопоставления предыдущих ключей:

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

Тест выше выведет что-то вроде этого:

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

Как вы видите значение отображается 1 а также 2 не обновлялся, только ключ 3 поворачивается, чтобы отобразить другое значение. Причина в том, что hashCode результат из [foo, bar] отличается от одного из [foo, bar, foobar] что приводит к Map#get не вернуть правильный результат. Чтобы преодолеть это, вам нужно получить набор ключей, сравнивая их с фактическим значением.

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

Теперь запуск обоих тестов снова дает следующий результат:

Для простых (неизменяемых) объектов

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]

Для объекта, который может измениться

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

Я надеюсь, что это поможет вам найти способ реализовать свою карту. Вы могли бы вместо расширения существующей реализации реализовать Map интерфейс, так что вы можете обеспечить внедрение для всех его методов в отношении их контрактов и иметь реализацию по вашему выбору в качестве члена для обработки фактического отображения.

Answer 7

Проверяйте только хеш-код ключа key1, если он совпадает, то мы все равно тестируем методом equals.

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

Answer 8

Пожалуйста, используйте отличные вспомогательные классы EqualsBuilder и HashCodeBuilder из библиотеки Apache Commons Lang. Пример:

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

Источник

Answer 9

Создать другой Map который содержит ключ отношения-> промежуточный ключ. Промежуточный ключ может быть GUID или чем-то еще, что автоматически генерируется и гарантированно будет уникальным.

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

В качестве альтернативы (хотя я нахожу это гораздо более сложным и менее гибким), вы можете играть с клавишами. Если key1.equals(key2) (и следовательно, key2.equals(key1) && (key1.hashCode () == key2.hashCode) thenMap.get (ключ1)will return the same value thanMap.get (ключ2)`.