Kartenimplementierung mit doppelten Schlüsseln

115

Ich möchte eine Karte mit doppelten Schlüsseln haben.

Ich weiß, dass es viele Kartenimplementierungen gibt (Eclipse zeigt mir ungefähr 50), also wette ich, dass es eine geben muss, die dies zulässt. Ich weiß, dass es einfach ist, eine eigene Karte zu schreiben, die dies tut, aber ich würde lieber eine vorhandene Lösung verwenden.

Vielleicht etwas in Commons-Sammlungen oder Google-Sammlungen?

IAdapter
quelle
4
Wie soll das funktionieren? Wenn Sie nach einem Wert fragen, der einem Schlüssel zugeordnet ist und dieser Schlüssel mehrmals in der Karte vorhanden ist, welcher Wert sollte zurückgegeben werden?
Mnementh
get könnte eine Ausnahme auslösen, ich brauche diese Map nur für die Iteration.
IAdapter
6
Wenn Sie es nur für die Iteration benötigen, warum benötigen Sie überhaupt eine Karte? Verwenden Sie eine Liste von Paaren oder etwas ...
Tal Pressman
2
Da mein gesamtes Programm bereits mit Map funktioniert und ich jetzt festgestellt habe, dass Daten möglicherweise doppelte Schlüssel haben. Wenn die Verwendung von Map auf andere Weise so falsch wäre, hätten wir nur 5 Implementierungen von Map und nicht 50+.
Kapitel

Antworten:

90

Sie suchen nach einer Multimap, und tatsächlich haben sowohl Commons-Sammlungen als auch Guava mehrere Implementierungen dafür. Multimaps ermöglichen mehrere Schlüssel, indem eine Sammlung von Werten pro Schlüssel verwaltet wird. Sie können also ein einzelnes Objekt in die Karte einfügen, aber eine Sammlung abrufen.

Wenn Sie Java 5 verwenden können, würde ich Guavas bevorzugen, Multimapda es generika-fähig ist.

nd.
quelle
3
Außerdem gibt diese Multimap nicht vor, eine Karte zu sein, wie es der Apache tut.
Kevin Bourrillion
7
Beachten Sie, dass Google Collections von Guava abgelöst wurde. Hier ist der Link zur Guava-Version von MultiMap: code.google.com/p/guava-libraries/wiki/…
Josh Glover
Multimap ist jedoch nicht vollständig serialisierbar, es hat vorübergehende Mitglieder, die eine deserialisierte Instanz unbrauchbar machen
dschulten
@dschulten Nun, Multimap ist eine Schnittstelle und Sie geben nicht an, welche Implementierung Sie meinen. com.google.common.collect.HashMultimaphat readObject/ writeObjectMethoden, ebenso wie ArrayListMultimap und Immutable {List, Set} Multimap. Ich würde eine nutzlose deserialisierte Instanz als einen Fehler betrachten, der es wert ist, gemeldet zu werden.
nd.
1
Apache Collections 4.0 unterstützt generics commons.apache.org/proper/commons-collections/javadocs/…
kervin
35

Wir müssen uns nicht auf die externe Bibliothek von Google Collections verlassen. Sie können einfach die folgende Map implementieren:

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

Bitte stellen Sie sicher, dass Sie den Code fein einstellen.

user668943
quelle
14
Sie müssen sich natürlich nicht auf Guavas Multimap verlassen. Es erleichtert nur Ihr Leben, da Sie sie nicht erneut implementieren, testen usw. müssen
PhiLho
Dies ermöglicht keine nahtlose Iteration über alle Paare. Es gibt sicherlich mehr Mängel. Ich wollte gerade meine Lösung vorschlagen, die auch eine zusätzliche Klasse erfordert, und sah dann, dass @ Mnemenths Antwort genau das ist.
Mark Jeronimus
2
Das Schreiben von Basiscode ist nicht immer so klug. Google ist eher bessere Tests
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));

Ausgabe ist:

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

Hinweis: Wir müssen Bibliotheksdateien importieren.

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

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

oder 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
quelle
2
Guter Vorschlag, da ich Spring in meinem Projekt verwende, habe ich letztendlich die Spring-Variante von MultiValueMap verwendet, wie in den Dokumenten http://docs.spring.io/spring-framework/docs/current/javadoc-api/org/ erwähnt. springframework / util / MultiValueMap.html
ajup
18

Sie könnten einfach ein Array von Werten für den Wert in einer regulären HashMap übergeben und so doppelte Schlüssel simulieren. Es liegt an Ihnen, zu entscheiden, welche Daten verwendet werden sollen.

Sie können auch einfach eine MultiMap verwenden , obwohl mir die Idee, Schlüssel selbst zu duplizieren, nicht gefällt.

AlbertoPL
quelle
Danke dir! Verwenden Sie TreeMap<String, ArrayList<MyClass>>gelöst meine doppelten Schlüsselanforderungen.
Joe
10

Wenn Sie eine Liste von Schlüssel-Wert-Paaren durchlaufen möchten (wie Sie im Kommentar geschrieben haben), sollte eine Liste oder ein Array besser sein. Kombinieren Sie zuerst Ihre Schlüssel und Werte:

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

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

}

Ersetzen Sie Klasse1 und Klasse2 durch die Typen, die Sie für Schlüssel und Werte verwenden möchten.

Jetzt können Sie sie in ein Array oder eine Liste einfügen und sie durchlaufen:

Pair[] pairs = new Pair[10];
...
for (Pair pair : pairs)
{
   ...
}
Mnementh
quelle
Wie würde ich add () oder put () implementieren? Ich möchte nicht die Anzahl der Dimensionen hardcore.
Amit Kumar Gupta
2
Verwenden Sie in diesem Fall eine Liste. Das zweite Beispiel ändert sich zu List <Pair> pair = new List <Pair> (); Die for-Schleife bleibt gleich. Mit diesem Befehl können Sie ein Paar hinzufügen: pairs.add (pair);
Mnementh
Dies ist wahrscheinlich die beste Antwort, um ehrlich zu sein.
PaulBGD
6

Dieses Problem kann mit einer Liste von Karteneinträgen gelöst werden List<Map.Entry<K,V>>. Wir müssen weder externe Bibliotheken noch eine neue Implementierung von Map verwenden. Ein Karteneintrag kann folgendermaßen erstellt werden: Map.Entry<String, Integer> entry = new AbstractMap.SimpleEntry<String, Integer>("key", 1);

Thach Van
quelle
3

Lerne aus meinen Fehlern ... bitte implementiere dies nicht alleine. Guave Multimap ist der richtige Weg.

Eine häufige Verbesserung, die in Multimaps erforderlich ist, besteht darin, doppelte Schlüssel-Wert-Paare nicht zuzulassen.

Das Implementieren / Ändern dieser in Ihrer Implementierung kann ärgerlich sein.

In Guave ist es so einfach wie:

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

ArrayListMultimap<String, Integer> allow_dupe_key_plus_val = ArrayListMultimap.create();
Erfrierung
quelle
2

Ich hatte eine etwas andere Variante dieses Problems: Es war erforderlich, zwei verschiedene Werte mit demselben Schlüssel zu verknüpfen. Wenn ich es hier poste, falls es anderen hilft, habe ich eine HashMap als Wert eingeführt:

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

Im obigen Code wird die Schlüssel-FrameID aus der ersten Zeichenfolge einer Eingabedatei in jeder Zeile gelesen. Der Wert für frameTypeHash wird durch Aufteilen der verbleibenden Zeile erstellt und ursprünglich als Zeichenfolgenobjekt gespeichert. Über einen Zeitraum hinweg begann die Datei mit mehreren Zeilen ( mit unterschiedlichen Werten), die demselben frameID-Schlüssel zugeordnet sind, sodass frameTypeHash mit der letzten Zeile als Wert überschrieben wurde. Ich habe das String-Objekt durch ein anderes HashMap-Objekt als Wertefeld ersetzt. Dies hat dazu beigetragen, einen einzelnen Schlüssel für eine andere Wertzuordnung beizubehalten.

Suresh Vadali
quelle
2

Keine ausgefallenen Bibliotheken erforderlich. Karten werden durch einen eindeutigen Schlüssel definiert. Biegen Sie sie also nicht, sondern verwenden Sie eine Liste. Streams sind mächtig.

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

Und das ist es. Anwendungsbeispiele:

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
quelle
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
quelle
Danke @daspilker. Ich sehe deine Bearbeitung jetzt nur. Gud zu sehen, dass jemand mein Snippet findet, ist es wert, wenn es bearbeitet wird.
Gabrial David
1
 1, Map<String, List<String>> map = new HashMap<>();

Diese ausführliche Lösung hat mehrere Nachteile und ist fehleranfällig. Dies bedeutet, dass wir eine Sammlung für jeden Wert instanziieren, vor dem Hinzufügen oder Entfernen eines Werts auf dessen Vorhandensein prüfen und manuell löschen müssen, wenn keine Werte mehr vorhanden sind usw.

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

Java-Map-Duplicate-Keys

Daria Yu
quelle
1

Was ist mit einem solchen MultiMap-Gerät?

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

}
George
quelle
0

Können Sie auch den Kontext erläutern, für den Sie versuchen, eine Karte mit doppelten Schlüsseln zu implementieren? Ich bin sicher, es könnte eine bessere Lösung geben. Karten sollen aus gutem Grund eindeutige Schlüssel behalten. Aber wenn du es wirklich tun wolltest; Sie können die Klasse jederzeit erweitern und eine einfache benutzerdefinierte Kartenklasse schreiben, die über eine Kollisionsminderungsfunktion verfügt und es Ihnen ermöglicht, mehrere Einträge mit denselben Schlüsseln zu behalten.

Hinweis: Sie müssen die Kollisionsminderungsfunktion so implementieren, dass kollidierende Schlüssel "immer" in einen eindeutigen Satz konvertiert werden. Etwas Einfaches wie das Anhängen eines Schlüssels mit dem Objekt-Hashcode oder so?

Priyank
quelle
1
Der Kontext ist, dass ich dachte, dass Schlüssel einzigartig sein werden, aber es stellt sich heraus, dass das möglicherweise nicht der Fall ist. Ich möchte nicht alles umgestalten, da es nicht oft verwendet wird.
IAdapter
Ich möchte eine kleine XML-Datei in einen Hashmap-ähnlichen Datentyp konvertieren. Nur das Problem ist, dass die Struktur der XML-Datei nicht behoben ist
Amit Kumar Gupta
0

Um vollständig zu sein, verfügt Apache Commons Collections auch über eine MultiMap . Der Nachteil ist natürlich, dass Apache Commons keine Generika verwendet.

newacct
quelle
1
Beachten Sie, dass ihre MultiMap Map implementiert, aber die Verträge der Map-Methoden bricht. Das nervt mich.
Kevin Bourrillion
0

Mit ein bisschen Hack können Sie HashSet mit doppelten Schlüsseln verwenden. WARNUNG: Dies hängt stark von der Implementierung von HashSet ab.

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
quelle
0

Wenn doppelte Schlüssel vorhanden sind, kann ein Schlüssel mehr als einem Wert entsprechen. Die naheliegende Lösung besteht darin, den Schlüssel einer Liste dieser Werte zuzuordnen.

Zum Beispiel in 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
quelle
0

Ich habe das benutzt:

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

Alex Arvanitidis
quelle