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?


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.


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.


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;

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.


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)
{
   ...
}

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



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

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.


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

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

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


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

}

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?


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.


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

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

0

Użyłem tego:

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.