Implementacja mapy ze zduplikowanymi kluczami

116

Chcę mieć mapę ze zduplikowanymi kluczami.

Wiem, że istnieje wiele implementacji map (Eclipse pokazuje mi około 50), więc założę się, że musi istnieć taka, która na to pozwala. Wiem, że łatwo jest napisać własną mapę, która to robi, ale wolałbym użyć istniejącego rozwiązania.

Może coś w kolekcjach-wspólnych lub kolekcjach-google?

IAdapter
źródło
4
Jak to powinno działać? Jeśli poprosisz o wartość skojarzoną z kluczem, a ten klucz istnieje wiele razy na mapie, która wartość powinna zostać zwrócona?
Mnementh
get może zgłosić wyjątek, potrzebuję tej mapy tylko do iteracji.
IAdapter
6
Jeśli potrzebujesz go tylko do iteracji, dlaczego potrzebujesz mapy w pierwszej kolejności? Użyj listy par czy czegoś ...
Tal Pressman,
2
Ponieważ mój cały program już działa z Mapem, a teraz odkryłem, że dane mogą mieć zduplikowane klucze. Gdyby użycie Map w inny sposób byłoby tak złe, mielibyśmy tylko 5 implementacji Map, a nie 50+.
IAdapter

Odpowiedzi:

90

Szukasz multimapy i rzeczywiście, zarówno wspólne kolekcje, jak i guawa, mają do tego kilka implementacji. Multimapy pozwalają na użycie wielu kluczy, utrzymując zbiór wartości na klucz, tj. Możesz umieścić pojedynczy obiekt na mapie, ale pobierasz kolekcję.

Jeśli możesz używać Java 5, wolałbym Guava, Multimapponieważ jest świadoma generycznych.

nd.
źródło
3
Poza tym ta Multimapa nie udaje mapy tak, jak robi to apache.
Kevin Bourrillion
7
Pamiętaj, że Kolekcje Google zostały zastąpione przez Guava, więc oto link do wersji MultiMap w wersji Guava: code.google.com/p/guava-libraries/wiki/…
Josh Glover
Jednak Multimap nie jest w pełni serializowalny, ma przejściowe elementy członkowskie, co sprawia, że
zdeserializowana
@dschulten Cóż, Multimap to interfejs i nie określasz, którą implementację masz na myśli. com.google.common.collect.HashMultimapma readObject/ writeObjectMethods, podobnie jak ArrayListMultimap i Immutable {List, Set} Multimap. Uznałbym bezużyteczną deserializowaną instancję za błąd, który warto zgłosić.
nd.
1
Apache Collections 4.0 obsługuje generics commons.apache.org/proper/commons-collections/javadocs/ ...
kervin
35

Nie musimy polegać na zewnętrznej bibliotece Google Collections. Możesz po prostu zaimplementować następującą mapę:

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

Upewnij się, że dostroiłeś kod.

user668943
źródło
14
Oczywiście nie musisz polegać na Multimapie Guavy. To po prostu ułatwia życie, ponieważ nie musisz ich ponownie wdrażać, testować itp.
PhiLho
Nie pozwala to na płynną iterację dla wszystkich par. Niedociągnięć na pewno jest więcej. Już miałem zasugerować moje rozwiązanie, które również wymaga jednej dodatkowej klasy, a potem zobaczyłem, że odpowiedź @ Mnementh jest taka.
Mark Jeronimus
2
pisanie podstawowego kodu nie zawsze jest sprytne. Google ma większe szanse na lepsze testy
senseiwu
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));

Wynik to:

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

Uwaga: musimy zaimportować pliki biblioteczne.

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

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

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

import org.apache.commons.collections.MultiMap;
import org.apache.commons.collections.map.MultiValueMap;
Issac Balaji
źródło
2
Dobra sugestia, ponieważ używam Spring w moim projekcie, skończyło się na użyciu Springa MultiValueMap, jak wspomniano w dokumentach http://docs.spring.io/spring-framework/docs/current/javadoc-api/org/ springframework / util / MultiValueMap.html
ajup
18

Możesz po prostu przekazać tablicę wartości dla wartości w zwykłym HashMap, symulując w ten sposób zduplikowane klucze, i to od Ciebie zależy, jakich danych użyjesz.

Możesz też po prostu użyć MultiMapy , chociaż sam nie podoba mi się pomysł duplikowania kluczy.

AlbertoPL
źródło
Dziękuję Ci! Korzystanie z TreeMap<String, ArrayList<MyClass>>rozwiązało moje zduplikowane kluczowe potrzeby.
Joe
10

Jeśli chcesz iterować po liście par klucz-wartość (jak napisałeś w komentarzu), to lista lub tablica powinny być lepsze. Najpierw połącz swoje klucze i wartości:

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

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

}

Zastąp Class1 i Class2 typami, których chcesz użyć dla kluczy i wartości.

Teraz możesz umieścić je w tablicy lub liście i iterować po nich:

Pair[] pairs = new Pair[10];
...
for (Pair pair : pairs)
{
   ...
}
Mnementh
źródło
Jak wdrożyć add () lub put (). Nie chcę ostrej liczby wymiarów.
Amit Kumar Gupta,
2
W takim przypadku użyj listy. Drugi przykład zmienia się na List <Pair> pairs = new List <Pair> (); Pętla for pozostaje taka sama. Możesz dodać parę za pomocą tego polecenia: pairs.add (pair);
Mnementh
Szczerze mówiąc, to chyba najlepsza odpowiedź.
PaulBGD,
6

Ten problem można rozwiązać za pomocą listy wpisów na mapie List<Map.Entry<K,V>>. Nie musimy używać ani zewnętrznych bibliotek, ani nowej implementacji Map. Wpis mapy można utworzyć w następujący sposób: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

Thach Van
źródło
3

Ucz się na moich błędach ... proszę, nie wdrażaj tego samodzielnie. Multimap Guava to droga do zrobienia.

Typowym ulepszeniem wymaganym w multimapach jest uniemożliwienie zduplikowanych par klucz-wartość.

Wdrażanie / zmienianie tego w implementacji może być denerwujące.

W guawie jest to tak proste, jak:

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

ArrayListMultimap<String, Integer> allow_dupe_key_plus_val = ArrayListMultimap.create();
odmrożenie
źródło
2

Miałem nieco inny wariant tego problemu: wymagane było skojarzenie dwóch różnych wartości z tym samym kluczem. Po prostu zamieszczając go tutaj, na wypadek, gdyby pomogło innym, jako wartość wprowadziłem 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 );
        }
}

W powyższym kodzie klucz frameID jest odczytywany z pierwszego ciągu pliku wejściowego w każdym wierszu, wartość frameTypeHash jest konstruowana przez podzielenie pozostałej linii i pierwotnie była przechowywana jako obiekt String, przez pewien czas plik zaczął mieć wiele wierszy ( z różnymi wartościami) skojarzony z tym samym kluczem frameID, więc frameTypeHash został nadpisany ostatnią linią jako wartością. Zastąpiłem obiekt String innym obiektem HashMap jako polem wartości, co pomogło w utrzymaniu pojedynczego klucza do różnych mapowań wartości.

Suresh Vadali
źródło
2

Nie są wymagane żadne wymyślne biblioteki. Mapy są definiowane przez unikalny klucz, więc nie zginaj ich, używaj listy. Strumienie są potężne.

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

I to wszystko. Przykłady użycia:

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
źródło
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;
        }
    }
Gabrial David
źródło
Dziękuję @daspilker. Widzę teraz tylko twoją zmianę. Gud, aby zobaczyć, jak ktoś znajdzie mój fragment, jeśli jest edytowany.
Gabrial David
1
 1, Map<String, List<String>> map = new HashMap<>();

to rozwlekłe rozwiązanie ma wiele wad i jest podatne na błędy. Oznacza to, że musimy utworzyć instancję Collection dla każdej wartości, sprawdzić jej obecność przed dodaniem lub usunięciem wartości, usunąć ją ręcznie, gdy nie ma żadnych wartości itp.

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

java-map-duplicate-keys

Daria Yu
źródło
1

a co z takim implem 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() .....

}
Jerzy
źródło
0

Czy mógłbyś również wyjaśnić kontekst, dla którego próbujesz zaimplementować mapę ze zduplikowanymi kluczami? Jestem pewien, że mogłoby być lepsze rozwiązanie. Mapy mają na celu przechowywanie unikalnych kluczy nie bez powodu. Chociaż jeśli naprawdę chcesz to zrobić; zawsze możesz rozszerzyć klasę i napisać prostą niestandardową klasę mapy, która ma funkcję ograniczania kolizji i umożliwiłaby przechowywanie wielu wpisów z tymi samymi kluczami.

Uwaga: Należy zaimplementować funkcję ograniczania kolizji, tak aby kolidujące klucze były konwertowane na unikalny zestaw „zawsze”. Coś prostego, jak dodanie klucza z hashcode obiektu czy coś takiego?

Priyank
źródło
1
Kontekst jest taki, że myślałem, że klucze będą unikalne, ale okazuje się, że może nie być. Nie chcę zmieniać wszystkiego, ponieważ nie będzie często używany.
IAdapter
Chcę przekonwertować mały plik XML na hashmap jak typ danych. Jedynym problemem jest to, że struktura pliku XML nie została naprawiona
Amit Kumar Gupta
0

aby być kompletnym, Apache Commons Collections ma również MultiMap . Wadą jest oczywiście to, że Apache Commons nie używa Generics.

newacct
źródło
1
Zauważ, że ich MultiMap implementuje Map, ale przerywa kontrakty metod Map. To mnie wkurza.
Kevin Bourrillion
0

Przy odrobinie hackowania możesz użyć HashSet ze zduplikowanymi kluczami. OSTRZEŻENIE: jest to silnie zależne od implementacji 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
źródło
0

Jeśli istnieją zduplikowane klucze, klucz może odpowiadać więcej niż jednej wartości. Oczywistym rozwiązaniem jest mapowanie klucza do listy tych wartości.

Na przykład w Pythonie:

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
źródło
0

Użyłem tego:

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

Alex Arvanitidis
źródło