Was passiert, wenn ein doppelter Schlüssel in eine HashMap eingefügt wird?

275

Was passiert mit dem ursprünglichen Wert, wenn ich denselben Schlüssel mehrmals an HashMapdie putMethode übergebe? Und was ist, wenn sich sogar der Wert wiederholt? Ich habe keine Dokumentation dazu gefunden.

Fall 1: Überschriebene Werte für einen Schlüssel

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
System.out.println(mymap.get("1"));

Wir bekommen surely not one.

Fall 2: Doppelter Wert

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
// The following line was added:
mymap.put("1","one");
System.out.println(mymap.get("1"));

Wir bekommen one.

Aber was passiert mit den anderen Werten? Ich unterrichtete einen Schüler in Grundlagen und wurde danach gefragt. Ist das Mapwie ein Bucket, in dem auf den letzten Wert verwiesen wird (aber im Speicher)?

Boodieye
quelle
7
Übrigens ist dies eine hervorragende Gelegenheit, die Multi- Hashmap zu demonstrieren , die Teil der Sammlungsklassen in Jakarta ist ( commons.apache.org/collections ). Damit können Sie eine beliebige Anzahl von Werten mit demselben Schlüssel verknüpfen, wenn Sie dies benötigen.
John Munsch
Mögliches Duplikat von HashMap mit mehreren Werten unter demselben Schlüssel
Muhammed Refaat

Antworten:

302

Per Definition putersetzt der Befehl den vorherigen Wert, der dem angegebenen Schlüssel in der Zuordnung zugeordnet ist (konzeptionell wie eine Array-Indizierungsoperation für primitive Typen).

Die Karte lässt einfach ihren Verweis auf den Wert fallen. Wenn nichts anderes einen Verweis auf das Objekt enthält, kann dieses Objekt für die Speicherbereinigung verwendet werden. Darüber hinaus gibt Java alle vorherigen Werte zurück, die dem angegebenen Schlüssel zugeordnet sind (oder nullfalls keine vorhanden sind), sodass Sie feststellen können, was vorhanden war, und bei Bedarf eine Referenz pflegen können.

Weitere Informationen hier: HashMap Doc

jheddings
quelle
Danke dafür. Beim Lesen der Java-Dokumentation wird dies nicht klar erwähnt. Ich vermute, der Autor des Dokuments hat angenommen, dass dies eine stillschweigende Annahme aller Hash-Map-Implementierungen ist.
Andrew S
76

Sie finden Ihre Antwort möglicherweise im Javadoc von Map # put (K, V) (das tatsächlich etwas zurückgibt):

public V put(K key,
             V value)

Ordnet den angegebenen Wert dem angegebenen Schlüssel in dieser Zuordnung zu (optionale Operation). Wenn die Zuordnung zuvor eine Zuordnung für diesen Schlüssel enthielt, wird der alte Wert durch den angegebenen Wert ersetzt. (Eine Karte msoll kgenau dann eine Zuordnung für einen Schlüssel enthalten, wenn m.containsKey(k)sie zurückkehren würde true.)

Parameter:
key - Schlüssel, dem der angegebene Wert zugeordnet werden soll.
value- Wert, der dem angegebenen Schlüssel zugeordnet werden soll.

Rückgabe:
Vorheriger Wert, der dem angegebenen Schlüssel zugeordnet ist, oder nullwenn keine Zuordnung für vorhanden war key. (Eine nullRückgabe kann auch anzeigen, dass die Zuordnung zuvor nullder angegebenen zugeordnet war key, wenn die Implementierung nullWerte unterstützt .)

Wenn Sie den zurückgegebenen Wert beim Aufruf nicht zuweisen mymap.put("1", "a string"), wird er einfach nicht mehr referenziert und kann daher nicht mehr gespeichert werden.

Pascal Thivent
quelle
3
Der zurückgegebene Wert ist der vorherige Wert (oder null), wie oben im Javadoc dokumentiert. Ja, das meine ich. Kann es wirklich falsch interpretiert werden?
Pascal Thivent
das ist sehr hilfreich.
Roottraveller
18

Der vorherige Wert für den Schlüssel wird gelöscht und durch den neuen ersetzt.

Wenn Sie alle Werte eines Schlüssels beibehalten möchten, können Sie Folgendes implementieren:

import org.apache.commons.collections.MultiHashMap;
import java.util.Set;
import java.util.Map;
import java.util.Iterator;
import java.util.List;
public class MultiMapExample {

   public static void main(String[] args) {
      MultiHashMap mp=new MultiHashMap();
      mp.put("a", 10);
      mp.put("a", 11);
      mp.put("a", 12);
      mp.put("b", 13);
      mp.put("c", 14);
      mp.put("e", 15);
      List list = null;

      Set set = mp.entrySet();
      Iterator i = set.iterator();
      while(i.hasNext()) {
         Map.Entry me = (Map.Entry)i.next();
         list=(List)mp.get(me.getKey());

         for(int j=0;j<list.size();j++)
         {
          System.out.println(me.getKey()+": value :"+list.get(j));
         }
      }
   }
}
kamlesh0606
quelle
Diese Lösung ist entzogen. MultiHashMap ist Teil von apache.commons.collections und nicht von Java.
Wikimix
17

Es ist die Schlüssel- / Wertfunktion, und Sie könnten keinen doppelten Schlüssel für mehrere Werte haben, da Sie, wenn Sie den tatsächlichen Wert erhalten möchten, welcher der Werte zu dem
in Ihrem Beispiel eingegebenen Schlüssel gehört, wenn Sie den Wert "1" erhalten möchten, welcher Wert ist es ?!
Das ist ein Grund, für jeden Wert einen eindeutigen Schlüssel zu haben, aber Sie könnten einen Trick von Java Standard Lib haben:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class DuplicateMap<K, V> {

    private Map<K, ArrayList<V>> m = new HashMap<>();

    public void put(K k, V v) {
        if (m.containsKey(k)) {
            m.get(k).add(v);
        } else {
            ArrayList<V> arr = new ArrayList<>();
            arr.add(v);
            m.put(k, arr);
        }
    }

     public ArrayList<V> get(K k) {
        return m.get(k);
    }

    public V get(K k, int index) {
        return m.get(k).size()-1 < index ? null : m.get(k).get(index);
    }
}


und Sie könnten es auf diese Weise verwenden:

    public static void main(String[] args) {
    DuplicateMap<String,String> dm=new DuplicateMap<>();
    dm.put("1", "one");
    dm.put("1", "not one");
    dm.put("1", "surely not one");
    System.out.println(dm.get("1"));
    System.out.println(dm.get("1",1));
    System.out.println(dm.get("1", 5));
}

und Ergebnis der Drucke sind:

[one, not one, surely not one]
not one
null
Java Acm
quelle
Gute Antwort! Gut gemacht. Sie retten buchstäblich mein Programmierleben :).
Subin Babu
Danke auch von mir! Ich musste eine "Entfernen" -Methode hinzufügen, um die gleiche Funktionalität wie eine normale Karte auszuführen, aber es hat großartig funktioniert!
JGlass
1
@JGlass Ihr willkommener Typ, aber dies ist keine technische Lösung. Das können Sie mit Java Standard Lib tun. Bei technischen Problemen müssen Sie auf Ihr Problem achten. Wenn Sie dieses Verhalten benötigen, bin ich sicher, dass es keine Lösung ist, weil des Schlüssel / Wert-Konzepts, und muss über das Problem nachdenken und einen logischen Weg zur Lösung finden. Trotzdem machen meine Details nur Spaß mit Java und in der Produktion unterscheiden sich Probleme und Lösungswege stark von lustiger Arbeit! Sie können es jedoch verwenden, wenn das Schlüssel- / Wertverhalten nicht Ihr Problem ist und Sie eine solche Datenstruktur finden.
Java Acm
13

Ordnet den angegebenen Wert dem angegebenen Schlüssel in dieser Zuordnung zu. Wenn die Zuordnung zuvor eine Zuordnung für den Schlüssel enthielt, wird der alte Wert ersetzt.

Diego Alejandro
quelle
12

Es ersetzt den vorhandenen Wert in der Karte für den jeweiligen Schlüssel. Wenn kein Schlüssel mit demselben Namen vorhanden ist, wird ein Schlüssel mit dem angegebenen Wert erstellt. z.B:

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","two");

OUTPUT key = "1", value = "two"

Der vorherige Wert wird also überschrieben.

Bishal Jaiswal
quelle
4

Auf Ihre Frage, ob die Karte wie ein Eimer war: Nein.

Es ist wie eine Liste mit name=valuePaaren, namemuss aber kein String sein (kann es aber).

Um ein Element abzurufen, übergeben Sie Ihren Schlüssel an die Methode get () -, die Ihnen das zugewiesene Objekt zurückgibt.

Und eine Hash- Map bedeutet, dass beim Versuch, Ihr Objekt mit der get-Methode abzurufen, das reale Objekt nicht mit dem von Ihnen angegebenen verglichen wird, da es die Liste durchlaufen und den Schlüssel vergleichen müsste Sie haben das aktuelle Element angegeben.

Dies wäre ineffizient. Unabhängig davon, woraus Ihr Objekt besteht, berechnet es stattdessen einen sogenannten Hashcode aus beiden Objekten und vergleicht diese. Es ist einfacher, zwei ints anstelle von zwei ganzen (möglicherweise sehr komplexen) Objekten zu vergleichen. Sie können sich den Hashcode wie eine Zusammenfassung mit einer vordefinierten Länge (int) vorstellen, daher ist er nicht eindeutig und weist Kollisionen auf. Die Regeln für den Hashcode finden Sie in der Dokumentation, zu der ich den Link eingefügt habe.

Wenn Sie mehr darüber wissen möchten, sollten Sie sich Artikel über ansehen javapractices.com und technofundo.com ansehen

Grüße

Atmocreations
quelle
3

Ich habe immer benutzt:

HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();

wenn ich mehrere Dinge auf einen identifizierenden Schlüssel anwenden wollte.

public void MultiHash(){
    HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();
    String key = "Your key";

    ArrayList<String> yourarraylist = hashy.get(key);

    for(String valuessaved2key : yourarraylist){
        System.out.println(valuessaved2key);
    }

}

Sie könnten immer so etwas tun und sich ein Labyrinth schaffen!

public void LOOK_AT_ALL_THESE_HASHMAPS(){
    HashMap<String, HashMap<String, HashMap<String, HashMap<String, String>>>> theultimatehashmap = new HashMap <String, HashMap<String, HashMap<String, HashMap<String, String>>>>();
    String ballsdeep_into_the_hashmap = theultimatehashmap.get("firststring").get("secondstring").get("thirdstring").get("forthstring");
}
SchafiiHD
quelle
2

Karten aus JDK sind nicht zum Speichern von Daten unter doppelten Schlüsseln gedacht.

  • Bestenfalls überschreibt der neue Wert die vorherigen.

  • Das schlimmste Szenario ist eine Ausnahme (z. B. wenn Sie versuchen, es als Stream zu sammeln):

Keine Duplikate:

Stream.of("one").collect(Collectors.toMap(x -> x, x -> x))

OK. Sie erhalten: $ 2 ==> {one = one}

Duplizierter Stream:

Stream.of("one", "not one", "surely not one").collect(Collectors.toMap(x -> 1, x -> x))

Ausnahme java.lang.IllegalStateException: Schlüssel 1 duplizieren (versucht, die Werte eins und nicht eins zusammenzuführen) | at Collectors.duplicateKeyException (Collectors.java:133) | bei Collectors.lambda $ uniqKeysMapAccumulator $ 1 (Collectors.java:180) | bei ReduceOps $ 3ReducingSink.accept (ReduceOps.java:169) | bei Spliterators $ ArraySpliterator.forEachRemaining (Spliterators.java:948) | at AbstractPipeline.copyInto (AbstractPipeline.java:484) | at AbstractPipeline.wrapAndCopyInto (AbstractPipeline.java:474) | bei ReduceOps $ ReduceOp.evaluateSequential (ReduceOps.java:913) | at AbstractPipeline.evaluate (AbstractPipeline.java:234) | at ReferencePipeline.collect (ReferencePipeline.java:578) | um (# 4: 1)

Verwenden Sie zum Umgang mit doppelten Schlüsseln ein anderes Paket, z. B.: Https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Multimap.html

Es gibt viele andere Implementierungen, die sich mit doppelten Schlüsseln befassen. Diese werden für das Web benötigt (z. B. doppelte Cookie-Schlüssel, HTTP-Header können dieselben Felder haben, ...)

Viel Glück! :) :)

Witold Kaczurba
quelle
Ist die "Override" -Operation teuer?
Gaurav
Es kann nur mit JDK gelöst werden. Collectors.toMap()hat drittes Argument - Zusammenführungsfunktion. Wenn wir das letzte doppelte Element einfach überschreiben möchten : Stream.of("one", "two", "one").collect(Collectors.toMap(x -> x, x -> x, (key1, key2) -> key2)). Link
Stand Alone
Auch Ihr zweites Codebeispiel ist nicht korrekt. Diese Eingabe: "one", "not one", "surely not one"erzeugt keine doppelten Schlüsselfehler, da alle Zeichenfolgen unterschiedlich sind.
Stand Alone
Hi @stand alleine. Bitte lesen Sie die Mapping-Funktion (toMap) sorgfältig durch.
Witold Kaczurba
Hallo @WitoldKaczurba. Bitte kompilieren Sie Ihren Code vor dem Posten.
Stand Alone
1

Übrigens, wenn Sie eine Semantik wünschen, z. B. nur setzen, wenn dieser Schlüssel nicht vorhanden ist. Sie können concurrentHashMapmit verwendenputIfAbsent() Funktion verwenden. Überprüfen Sie dies heraus:

https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html#put(K,%20V)

concurrentHashMap ist threadsicher mit hoher Leistung, da es einen " Lock Striping " -Mechanismus verwendet, um den Durchsatz zu verbessern.

BufBills
quelle
1

Ja, dies bedeutet, dass alle 1 Schlüssel mit Wert mit dem letzten Mehrwert überschrieben werden. Hier fügen Sie "sicherlich nicht einen" hinzu, sodass nur "sicher nicht einer" angezeigt wird.

Selbst wenn Sie versuchen, mit einer Schleife anzuzeigen, werden nur ein Schlüssel und ein Wert angezeigt, die denselben Schlüssel haben.

Ajaynakrani
quelle
0
         HashMap<Emp, Emp> empHashMap = new HashMap<Emp, Emp>();

         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp());
         empHashMap.put(new Emp(1), new Emp());
         System.out.println(empHashMap.size());
    }
}

class Emp{
    public Emp(){   
    }
    public Emp(int id){
        this.id = id;
    }
    public int id;
    @Override
    public boolean equals(Object obj) {
        return this.id == ((Emp)obj).id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}


OUTPUT : is 1

Bedeutet, dass die Hash-Map keine Duplikate zulässt, wenn Sie die Methoden equals und hashCode () ordnungsgemäß überschrieben haben.

HashSet verwendet HashMap auch intern, siehe Quelldokument

public class HashSet{
public HashSet() {
        map = new HashMap<>();
    }
}
SatyaS
quelle