Реализация карты с повторяющимися ключами

116

Я хочу иметь карту с повторяющимися ключами.

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

Может быть, что-то в общих коллекциях или гугл-коллекциях?

IAdapter
источник
4
Как это должно работать? Если вы запрашиваете значение, связанное с ключом, а этот ключ существует на карте несколько раз, какое значение следует вернуть?
Mnementh
get может вызвать исключение, мне нужна эта карта только для итерации.
IAdapter
6
Если он нужен только для итерации, зачем вообще нужна карта? Используйте список пар или что-то в этом роде ...
Tal Pressman
2
Потому что вся моя программа уже работает с Map, и теперь я обнаружил, что данные могут иметь повторяющиеся ключи. Если бы использовать Map другим способом было бы неправильно, у нас было бы только 5 реализаций Map, а не 50+.
IAdapter

Ответы:

90

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

Если вы можете использовать Java 5, я бы предпочел Guava, так Multimapкак он поддерживает дженерики.

без обозначения даты
источник
3
Кроме того, эта Multimap не претендует на роль карты, как это делает apache.
Кевин Бурриллион
7
Обратите внимание, что Коллекции Google были заменены Guava, поэтому вот ссылка на версию MultiMap для Guava: code.google.com/p/guava-libraries/wiki/…
Джош Гловер,
Однако Multimap не может быть полностью сериализован, у него есть временные элементы, которые делают десериализованный экземпляр бесполезным
dschulten
@dschulten Ну, Multimap - это интерфейс, и вы не указываете, какую реализацию вы имеете в виду. com.google.common.collect.HashMultimapимеет readObject/ writeObjectметоды, как и ArrayListMultimap и Immutable {List, Set} Multimap. Я считаю бесполезный десериализованный экземпляр ошибкой, о которой стоит сообщить.
.
1
Apache Collections 4.0 поддерживает общие
Кервин 07
35

Нам не нужно зависеть от внешней библиотеки Google Collections. Вы можете просто реализовать следующую карту:

Map<String, ArrayList<String>> hashMap = new HashMap<String, ArrayList>();

public static void main(String... arg) {
   // Add data with duplicate keys
   addValues("A", "a1");
   addValues("A", "a2");
   addValues("B", "b");
   // View data.
   Iterator it = hashMap.keySet().iterator();
   ArrayList tempList = null;

   while (it.hasNext()) {
      String key = it.next().toString();             
      tempList = hashMap.get(key);
      if (tempList != null) {
         for (String value: tempList) {
            System.out.println("Key : "+key+ " , Value : "+value);
         }
      }
   }
}

private void addValues(String key, String value) {
   ArrayList tempList = null;
   if (hashMap.containsKey(key)) {
      tempList = hashMap.get(key);
      if(tempList == null)
         tempList = new ArrayList();
      tempList.add(value);  
   } else {
      tempList = new ArrayList();
      tempList.add(value);               
   }
   hashMap.put(key,tempList);
}

Обязательно настройте код.

user668943
источник
14
Конечно, вам не нужно полагаться на Multimap Guava. Это просто облегчает вашу жизнь, так как вам не нужно заново внедрять их, тестировать и т. Д.
PhiLho
Это не позволяет выполнять бесшовную итерацию по всем парам. Недостатков наверняка больше. Я собирался предложить свое решение, для которого также требуется один дополнительный класс, но затем увидел, что ответ @Mnementh - это просто.
Марк Иеронимус
2
писать базовый код не всегда так умно. Скорее всего, у Google будут лучшие тесты,
сэнсэйу,
26
Multimap<Integer, String> multimap = ArrayListMultimap.create();

multimap.put(1, "A");
multimap.put(1, "B");
multimap.put(1, "C");
multimap.put(1, "A");

multimap.put(2, "A");
multimap.put(2, "B");
multimap.put(2, "C");

multimap.put(3, "A");

System.out.println(multimap.get(1));
System.out.println(multimap.get(2));       
System.out.println(multimap.get(3));

Выход:

[A,B,C,A]
[A,B,C]
[A]

Примечание: нам нужно импортировать файлы библиотеки.

http://www.java2s.com/Code/Jar/g/Downloadgooglecollectionsjar.htm

import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Multimap;

или https://commons.apache.org/proper/commons-collections/download_collections.cgi

import org.apache.commons.collections.MultiMap;
import org.apache.commons.collections.map.MultiValueMap;
Иссак Баладжи
источник
2
Хорошее предложение, поскольку я использую Spring в своем проекте, я в конечном итоге использовал версию Spring для MultiValueMap, как указано в документах http://docs.spring.io/spring-framework/docs/current/javadoc-api/org/ springframework / util / MultiValueMap.html
ajup
18

Вы можете просто передать массив значений для значения в обычном HashMap, таким образом имитируя повторяющиеся ключи, и вам решать, какие данные использовать.

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

AlbertoPL
источник
Спасибо! Использование TreeMap<String, ArrayList<MyClass>>решило мои потребности в дублировании ключей.
Джо
10

Если вы хотите перебрать список пар ключ-значение (как вы написали в комментарии), то лучше использовать список или массив. Сначала объедините свои ключи и значения:

public class Pair
{
   public Class1 key;
   public Class2 value;

   public Pair(Class1 key, Class2 value)
   {
      this.key = key;
      this.value = value;
   }

}

Замените Class1 и Class2 типами, которые вы хотите использовать для ключей и значений.

Теперь вы можете поместить их в массив или список и перебрать их:

Pair[] pairs = new Pair[10];
...
for (Pair pair : pairs)
{
   ...
}
Mnementh
источник
Как мне реализовать add () или put (). Я не хочу хардкорного количества измерений.
Амит Кумар Гупта,
2
В этом случае используйте список. Второй пример меняется на List <Pair> pair = new List <Pair> (); Цикл for остается прежним. Вы можете добавить пару с помощью этой команды: pair.add (pair);
Mnementh
Если честно, это, наверное, лучший ответ.
PaulBGD
6

Эту проблему можно решить с помощью списка записей на карте List<Map.Entry<K,V>>. Нам не нужно использовать ни внешние библиотеки, ни новую реализацию Map. Запись на карте может быть создана следующим образом: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

Thach Van
источник
3

Учитесь на моих ошибках ... пожалуйста, не выполняйте это самостоятельно. Guava multimap - это то, что вам нужно.

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

Реализация / изменение этого в вашей реализации может раздражать.

В Гуаве это так просто, как:

HashMultimap<String, Integer> no_dupe_key_plus_val = HashMultimap.create();

ArrayListMultimap<String, Integer> allow_dupe_key_plus_val = ArrayListMultimap.create();
отмороженное место
источник
2

У меня был немного другой вариант этой проблемы: требовалось связать два разных значения с одним и тем же ключом. Просто разместив его здесь на случай, если он поможет другим, я ввел HashMap в качестве значения:

/* @param frameTypeHash: Key -> Integer (frameID), Value -> HashMap (innerMap)
   @param innerMap: Key -> String (extIP), Value -> String
   If the key exists, retrieve the stored HashMap innerMap 
   and put the constructed key, value pair
*/
  if (frameTypeHash.containsKey(frameID)){
            //Key exists, add the key/value to innerHashMap
            HashMap innerMap = (HashMap)frameTypeHash.get(frameID);
            innerMap.put(extIP, connName+":"+frameType+":"+interfaceName);

        } else {
            HashMap<String, String> innerMap = new HashMap<String, String>();
            innerMap.put(extIP, connName+":"+frameType+":"+interfaceName);
            // This means the key doesn't exists, adding it for the first time
            frameTypeHash.put(frameID, innerMap );
        }
}

В приведенном выше коде ключевой frameID считывается из первой строки входного файла в каждой строке, значение для frameTypeHash создается путем разделения оставшейся строки и первоначально сохранялось как объект String, в течение некоторого периода времени, когда файл начинался с нескольких строк ( с разными значениями), связанный с тем же ключом frameID, поэтому frameTypeHash был перезаписан последней строкой в ​​качестве значения. Я заменил объект String другим объектом HashMap в качестве поля значения, это помогло сохранить один ключ для другого сопоставления значений.

Суреш Вадали
источник
2

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

import java.util.AbstractMap.SimpleImmutableEntry;

List<SimpleImmutableEntry<String, String>> nameToLocationMap = Arrays.asList(
    new SimpleImmutableEntry<>("A", "A1"),
    new SimpleImmutableEntry<>("A", "A2"),
    new SimpleImmutableEntry<>("B", "B1"),
    new SimpleImmutableEntry<>("B", "B1"),
);

И это все. Примеры использования:

List<String> allBsLocations = nameToLocationMap.stream()
        .filter(x -> x.getKey().equals("B"))
        .map(x -> x.getValue())
        .collect(Collectors.toList());

nameToLocationMap.stream().forEach(x -> 
do stuff with: x.getKey()...x.getValue()...
BiggDatta
источник
1
class  DuplicateMap<K, V> 
{
    enum MapType
    {
        Hash,LinkedHash
    }

    int HashCode = 0;
    Map<Key<K>,V> map = null;

    DuplicateMap()
    {
        map = new HashMap<Key<K>,V>();
    }

    DuplicateMap( MapType maptype )
    {
        if ( maptype == MapType.Hash ) {
            map = new HashMap<Key<K>,V>();
        }
        else if ( maptype == MapType.LinkedHash ) {
            map = new LinkedHashMap<Key<K>,V>();
        }
        else
            map = new HashMap<Key<K>,V>();
    }

    V put( K key, V value  )
    {

        return map.put( new Key<K>( key , HashCode++ ), value );
    }

    void putAll( Map<K, V> map1 )
    {
        Map<Key<K>,V> map2 = new LinkedHashMap<Key<K>,V>();

        for ( Entry<K, V> entry : map1.entrySet() ) {
            map2.put( new Key<K>( entry.getKey() , HashCode++ ), entry.getValue());
        }
        map.putAll(map2);
    }

    Set<Entry<K, V>> entrySet()
    {
        Set<Entry<K, V>> entry = new LinkedHashSet<Map.Entry<K,V>>();
        for ( final Entry<Key<K>, V> entry1 : map.entrySet() ) {
            entry.add( new Entry<K, V>(){
                private K Key = entry1.getKey().Key();
                private V Value = entry1.getValue();

                @Override
                public K getKey() {
                    return Key;
                }

                @Override
                public V getValue() {
                    return Value;
                }

                @Override
                public V setValue(V value) {
                    return null;
                }});
        }

        return entry;
    }

    @Override
    public String toString() {
        StringBuilder builder = new  StringBuilder();
        builder.append("{");
        boolean FirstIteration = true;
        for ( Entry<K, V> entry : entrySet() ) {
            builder.append( ( (FirstIteration)? "" : "," ) + ((entry.getKey()==null) ? null :entry.getKey().toString() ) + "=" + ((entry.getValue()==null) ? null :entry.getValue().toString() )  );
            FirstIteration = false;
        }
        builder.append("}");
        return builder.toString();
    }

    class Key<K1>
    {
        K1 Key;
        int HashCode;

        public Key(K1 key, int hashCode) {
            super();
            Key = key;
            HashCode = hashCode;
        }

        public K1 Key() {
            return Key;
        }

        @Override
        public String toString() {
            return  Key.toString() ;
        }

        @Override
        public int hashCode() {

            return HashCode;
        }
    }
Габриал Давид
источник
Спасибо @daspilker. Я вижу только вашу правку сейчас. Гуд увидеть, как кто-нибудь найдет мой фрагмент достойным, если его отредактируют.
Габриал Дэвид
1
 1, Map<String, List<String>> map = new HashMap<>();

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

2, org.apache.commons.collections4.MultiMap interface
3, com.google.common.collect.Multimap interface 

Java-карта-дублирующие клавиши

Дарья Ю
источник
1

как насчет такого имплта MultiMap?

public class MultiMap<K, V> extends HashMap<K, Set<V>> {
  private static final long serialVersionUID = 1L;
  private Map<K, Set<V>> innerMap = new HashMap<>();

  public Set<V> put(K key, V value) {
    Set<V> valuesOld = this.innerMap.get(key);
    HashSet<V> valuesNewTotal = new HashSet<>();
    if (valuesOld != null) {
      valuesNewTotal.addAll(valuesOld);
    }
    valuesNewTotal.add(value);
    this.innerMap.put(key, valuesNewTotal);
    return valuesOld;
  }

  public void putAll(K key, Set<V> values) {
    for (V value : values) {
      put(key, value);
    }
  }

  @Override
  public Set<V> put(K key, Set<V> value) {
    Set<V> valuesOld = this.innerMap.get(key);
    putAll(key, value);
    return valuesOld;
  }

  @Override
  public void putAll(Map<? extends K, ? extends Set<V>> mapOfValues) {
    for (Map.Entry<? extends K, ? extends Set<V>> valueEntry : mapOfValues.entrySet()) {
      K key = valueEntry.getKey();
      Set<V> value = valueEntry.getValue();
      putAll(key, value);
    }
  }

  @Override
  public Set<V> putIfAbsent(K key, Set<V> value) {
    Set<V> valueOld = this.innerMap.get(key);
    if (valueOld == null) {
      putAll(key, value);
    }
    return valueOld;
  }

  @Override
  public Set<V> get(Object key) {
    return this.innerMap.get(key);
  }

  @Override
  etc. etc. override all public methods size(), clear() .....

}
Джордж
источник
0

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

Примечание. Вы должны реализовать функцию смягчения конфликтов таким образом, чтобы конфликтующие ключи преобразовывались в уникальный набор «всегда». Что-то простое, например, добавить ключ с хэш-кодом объекта или что-то в этом роде?

Priyank
источник
1
Контекст таков, что я думал, что ключи будут уникальными, но оказалось, что это могло не быть. Я не хочу реорганизовывать все, потому что это редко используется.
IAdapter
Я хочу преобразовать небольшой XML-файл в хэш-карту, например тип данных. Проблема только в том, что структура XML-файла не исправлена
Амит Кумар Гупта
0

для полноты: Коллекции Apache Commons также имеют MultiMap . Обратной стороной, конечно же, является то, что Apache Commons не использует Generics.

newacct
источник
1
Обратите внимание, что их MultiMap реализует Map, но нарушает контракты методов Map. Это меня беспокоит.
Кевин Бурриллион,
0

Немного взломав, вы можете использовать HashSet с повторяющимися ключами. ВНИМАНИЕ: это сильно зависит от реализации HashSet.

class MultiKeyPair {
    Object key;
    Object value;

    public MultiKeyPair(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

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

class MultiKeyList extends MultiKeyPair {
    ArrayList<MultiKeyPair> list = new ArrayList<MultiKeyPair>();

    public MultiKeyList(Object key) {
        super(key, null);
    }

    @Override
    public boolean equals(Object obj) {
        list.add((MultiKeyPair) obj);
        return false;
    }
}

public static void main(String[] args) {
    HashSet<MultiKeyPair> set = new HashSet<MultiKeyPair>();
    set.add(new MultiKeyPair("A","a1"));
    set.add(new MultiKeyPair("A","a2"));
    set.add(new MultiKeyPair("B","b1"));
    set.add(new MultiKeyPair("A","a3"));

    MultiKeyList o = new MultiKeyList("A");
    set.contains(o);

    for (MultiKeyPair pair : o.list) {
        System.out.println(pair.value);
    }
}
Erdem
источник
0

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

Например, в Python:

map = dict()
map["driver"] = list()
map["driver"].append("john")
map["driver"].append("mike")
print map["driver"]          # It shows john and mike
print map["driver"][0]       # It shows john
print map["driver"][1]       # It shows mike
cyberthanasis
источник
0

Я использовал это:

java.util.List<java.util.Map.Entry<String,Integer>> pairList= new java.util.ArrayList<>();

Алекс Арванитидис
источник