Wie behandelt eine Java HashMap verschiedene Objekte mit demselben Hashcode?

Ihre dritte Behauptung ist falsch.

Es ist absolut legal, dass zwei ungleiche Objekte denselben Hash-Code haben. Es wird von HashMap als "First Pass Filter" verwendet, damit die Karte mit dem angegebenen Schlüssel schnell nach möglich Einträgen suchen kann. Die Schlüssel mit demselben Hash-Code werden dann mit dem angegebenen Schlüssel auf Gleichheit getestet.

Sie möchten nicht, dass zwei ungleiche Objekte nicht denselben Hash-Code haben können, da Sie sonst auf 2 beschränkt wären³² mögliche Objekte. (Dies würde auch bedeuten, dass verschiedene Typen nicht einmal die Felder eines Objekts verwenden könnten, um Hashcodes zu generieren, da andere Klassen denselben Hash generieren könnten.)

HashMap ist ein Array von Entry-Objekten.

Betrachten Sie HashMap nur als ein Array von Objekten.

Schauen Sie sich an, was dies Object ist:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;
… 
}

Jedes Entry-Objekt repräsentiert ein Schlüsselwertpaar. Das Feld next verweist auf ein anderes Entry-Objekt, wenn ein Bucket mehrere Entry-Objekte enthält.

Es kann vorkommen, dass Hash-Codes für zwei verschiedene Objekte gleich sind. In diesem Fall werden zwei Objekte in einem Bucket gespeichert und als verknüpfte Liste angezeigt. Der Einstiegspunkt ist das neu hinzugefügte Objekt. Dieses Objekt verweist auf ein anderes Objekt mit dem Feld next und so weiter. Der letzte Eintrag bezieht sich auf null.

Beim Erstellen eines HashMap mit dem Standardkonstruktor

HashMap hashMap = new HashMap();

Das Array wird mit einer Größe von 16 und einem Standard-Lastausgleich von 0,75 erstellt.

Hinzufügen eines neuen Schlüsselwertpaares

1. Berechnen Sie den Hashcode für den Schlüssel
2. Position hash % (arrayLength-1) berechnen, an der das Element platziert werden soll (Eimernummer)
3. Wenn Sie versuchen, einen Wert mit einem Schlüssel hinzuzufügen, der bereits in HashMap gespeichert wurde, wird der Wert überschrieben.
4. Andernfalls wird das Element zum Bucket hinzugefügt.

Wenn der Bucket bereits über mindestens ein Element verfügt, wird ein neues Element hinzugefügt und an der ersten Position des Bucket platziert. Ihr next-Feld verweist auf das alte Element.

Streichung

1. Hashcode für den angegebenen Schlüssel berechnen
2. Berechnung der Bucket-Nummer hash % (arrayLength-1)
3. Holen Sie sich einen Verweis auf das erste Entry-Objekt im Bucket und iterieren Sie mit der equals-Methode alle Einträge im angegebenen Bucket. Eventuell finden wir das richtige Entry. Wenn ein gewünschtes Element nicht gefunden wird, geben Sie null zurück. 

Sie finden ausgezeichnete Informationen unter http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-Java.html

Zusammenfassen: 

HashMap arbeitet nach dem Hashing-Prinzip

put (key, value): HashMap speichert sowohl key als auch value als Map.Entry. Hashmap wendet Hashcode (Schlüssel) an, um den Bucket abzurufen. Wenn es eine Kollision gibt, verwendet HashMap LinkedList zum Speichern des Objekts. 

get (key): HashMap verwendet den Hashcode von Key Object, um die Position des Buckets zu ermitteln, und ruft dann die keys.equals () -Methode auf, um den korrekten Knoten in LinkedList zu identifizieren und ein zugehöriges Wertobjekt für diesen Schlüssel in Java HashMap zurückzugeben.

Hier ist eine grobe Beschreibung des Mechanismus von HashMap für die Version Java 8 (möglicherweise etwas anders als Java 6) ) .

Datenstrukturen

• Hash-Tabelle
  Der Hash-Wert wird über hash() on key berechnet und entscheidet, welcher Bucket der Hash-Tabelle für einen bestimmten Schlüssel verwendet werden soll.
• Verknüpfte Liste (einzeln)
  Wenn die Anzahl der Elemente in einem Bucket gering ist, wird eine einfach verknüpfte Liste verwendet.
• Rot-Schwarzer Baum
  Wenn die Anzahl der Elemente in einem Bucket groß ist, wird ein rot-schwarzer Baum verwendet.

Klassen (intern)

• Map.Entry
  Stellen Sie eine einzelne Entität in der Karte dar, die Schlüssel/Wert-Entität.

• HashMap.Node
  Verknüpfte Listenversion des Knotens.

  Es könnte darstellen:

  • Ein Hash-Eimer.
    Weil es eine Hash-Eigenschaft hat.
  • Ein Knoten in einer einfach verknüpften Liste (also auch Kopf der verknüpften Liste) .
• HashMap.TreeNode
  Baumversion des Knotens.

Felder (intern)

• Node[] table
  Die Bucket-Tabelle (Kopf der verknüpften Listen).
  Wenn ein Bucket keine Elemente enthält, ist er null und nimmt daher nur Platz von einer Referenz ein.
• Set<Map.Entry> entrySet Gruppe von Entitäten.
• int size
  Anzahl der Einheiten.
• float loadFactor
  Geben Sie an, wie voll die Hash-Tabelle sein darf, bevor Sie die Größe ändern.
• int threshold
  Die nächste Größe, deren Größe geändert werden soll.
  Formel: threshold = capacity * loadFactor

Methoden (intern)

• int hash(key)
  Berechnen Sie den Hash anhand des Schlüssels.

• Wie ordne ich Hash zu Eimer?
  Verwenden Sie folgende Logik:

  static int hashToBucket(int tableSize, int hash) {
      return (tableSize - 1) & hash;
  }
  

Über die Kapazität

In der Hash-Tabelle bedeutet Kapazität die Anzahl der Bucket, die von table.length Stammen könnte.
Kann auch über threshold und loadFactor berechnet werden, muss also nicht als Klassenfeld definiert werden.

Konnte die effektive Kapazität erhalten über: capacity()

Operationen

• Entität nach Schlüssel suchen.
  Finden Sie zuerst den Bucket anhand des Hash-Werts, schleifen Sie dann die verknüpfte Liste oder suchen Sie den sortierten Baum.
• Entität mit Schlüssel hinzufügen.
  Finden Sie zuerst den Eimer gemäß dem Hash-Wert des Schlüssels.
  Dann versuchen Sie den Wert zu finden:
  • Wenn gefunden, ersetzen Sie den Wert.
  • Fügen Sie andernfalls einen neuen Knoten am Anfang der verknüpften Liste hinzu oder fügen Sie ihn in den sortierten Baum ein.
• Größe ändern
  Wenn threshold erreicht ist, wird die Kapazität der Hash-Tabelle verdoppelt (table.length) Und anschließend ein erneutes Hash für alle Elemente ausgeführt, um die Tabelle neu zu erstellen.
  Dies könnte eine teure Operation sein.

Performance

• bekommen & setzen
  Zeitkomplexität ist O(1), weil:
  • Auf den Bucket wird über den Array-Index zugegriffen, also O(1).
  • Die verknüpfte Liste in jedem Bucket ist klein und kann daher als O(1) angezeigt werden.
  • Die Baumgröße ist ebenfalls begrenzt, da die Kapazität erweitert und der Hash-Vorgang erneut ausgeführt wird, wenn die Anzahl der Elemente zunimmt. Daher kann dies als O(1) und nicht als O(log N) angezeigt werden.

Der Hashcode legt fest, welchen Bereich die Hashmap überprüfen soll. Wenn sich im Bucket mehrere Objekte befinden, wird linear gesucht, um herauszufinden, welches Element im Bucket dem gewünschten Element (mit der equals()) -Methode entspricht.

Mit anderen Worten, wenn Sie einen perfekten Hashcode haben und der Hashmap-Zugriff konstant ist, müssen Sie nie durch einen Bucket iterieren (technisch gesehen müssten Sie auch MAX_INT-Buckets haben, die Java-Implementierung kann einige Hashcodes im selben Bucket mit gemeinsam nutzen weniger Platzbedarf). Wenn Sie den schlechtesten Hashcode haben (gibt immer dieselbe Nummer zurück), wird der Zugriff auf die Hashmap linear, da Sie alle Elemente in der Map durchsuchen müssen (sie befinden sich alle im selben Bucket), um das zu erhalten, was Sie möchten.

Meistens ist ein gut geschriebener Hashcode nicht perfekt, aber er ist einzigartig genug, um Ihnen mehr oder weniger konstanten Zugriff zu gewähren.

Sie liegen falsch in Punkt drei. Zwei Einträge können denselben Hash-Code haben, dürfen aber nicht gleich sein. Schauen Sie sich die Implementierung von HashMap.get aus dem OpenJdk an. Sie können sehen, dass es überprüft, ob die Hashes gleich sind und die Schlüssel gleich sind. Wäre Punkt drei wahr, dann wäre es nicht notwendig, die Schlüssel auf Gleichheit zu prüfen. Der Hashcode wird vor dem Schlüssel verglichen, da der erstgenannte Vergleich effizienter ist. 

Wenn Sie mehr darüber erfahren möchten, werfen Sie einen Blick auf den Wikipedia-Artikel zu Open Collision Resolution , das meiner Meinung nach der Mechanismus ist, den die OpenJdk-Implementierung verwendet. Dieser Mechanismus unterscheidet sich auf subtile Weise von dem "Bucket" -Ansatz einer der anderen Antworten. 

import Java.util.HashMap;

public class Students  {
    String name;
    int age;

    Students(String name, int age ){
        this.name = name;
        this.age=age;
    }

    @Override
    public int hashCode() {
        System.out.println("__hash__");
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        System.out.println("__eq__");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Students other = (Students) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }

    public static void main(String[] args) {

        Students S1 = new Students("taj",22);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Output:

__ hash __

116232

__ hash __

116201

__ hash __

__ hash __

2

Wenn wir also sehen, dass beide Objekte S1 und S2 unterschiedlichen Inhalt haben, sind wir ziemlich sicher, dass unsere überschriebene Hashcode-Methode für beide Objekte unterschiedlichen Hashcode (116232,11601) generiert. JETZT, da es verschiedene Hash-Codes gibt, wird es nicht einmal die Mühe machen, die EQUALS-Methode aufzurufen. Ein anderer Hashcode GARANTIERT VERSCHIEDENEN Inhalt in einem Objekt.

    public static void main(String[] args) {

        Students S1 = new Students("taj",21);
        Students S2 = new Students("taj",21);

        System.out.println(S1.hashCode());
        System.out.println(S2.hashCode());

        HashMap<Students,String > HM = new HashMap<Students,String > (); 
        HM.put(S1, "tajinder");
        HM.put(S2, "tajinder");
        System.out.println(HM.size());
    }
}

Now lets change out main method a little bit. Output after this change is 

__ hash __

116201

__ hash __

116201

__ hash __

__ hash __

__ eq __

1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally  calls Equal method to verify this. 


Conclusion 
If hashcode is different , equal method will not get called. 
if hashcode is same, equal method will get called.

Thanks , hope it helps. 

Jedes Entry-Objekt repräsentiert ein Schlüssel-Wert-Paar. Das nächste Feld bezieht sich auf ein anderes Eintragsobjekt, wenn ein Bereich mehr als einen Eintrag enthält.

Es kann vorkommen, dass Hash-Codes für 2 verschiedene Objekte gleich sind. In diesem Fall werden 2 Objekte in einem Bucket gespeichert und als LinkedList angezeigt. Der Einstiegspunkt ist ein kürzlich hinzugefügtes Objekt. Dieses Objekt verweist auf ein anderes Objekt mit dem nächsten Feld und somit auf eins. Der letzte Eintrag bezieht sich auf null. Wenn Sie HashMap mit Standardkonstruktor erstellen

Das Array wird mit der Größe 16 und einem Standard-Lastausgleich von 0,75 erstellt.

(Quelle)

Hash-Map arbeitet nach dem Hashing-Prinzip 

Die HashMap-Methode get (Key k) ruft die hashCode-Methode für das Schlüsselobjekt auf und wendet zurückgegebenes hashValue auf ihre eigene statische Hash-Funktion an, um eine Bucket-Position (Backing-Array) zu finden, an der Schlüssel und Werte in Form einer verschachtelten Klasse namens Entry (Map) gespeichert werden. Eintrag). Sie haben also aus der vorherigen Zeile geschlossen, dass sowohl Schlüssel als auch Wert als eine Art Eintragobjekt im Bucket gespeichert sind. Daher ist das Denken, dass nur der Wert im Eimer gespeichert ist, nicht richtig und wird auf den Interviewer keinen guten Eindruck machen.

• Immer wenn wir die get (Key k) -Methode für das HashMap-Objekt aufrufen. Zuerst wird geprüft, ob der Schlüssel null ist oder nicht. Beachten Sie, dass es in HashMap nur einen Nullschlüssel geben kann. 

Wenn der Schlüssel null ist, werden die Null-Schlüssel immer dem Hash 0 zugeordnet, also 0.

Wenn key nicht null ist, wird hashfunction für das key-Objekt aufgerufen, siehe Zeile 4 in der obigen Methode, d. H. Key.hashCode (). Nachdem key.hashCode () hashValue zurückgibt, sieht Zeile 4 so aus

            int hash = hash(hashValue)

und jetzt wendet es zurückgegebenes hashValue in seiner eigenen Hashfunktion an.

Wir fragen uns vielleicht, warum wir den Hashwert erneut mit Hash (Hashwert) berechnen. Antwort ist Es verteidigt gegen schlechte Qualität Hash-Funktionen.

Jetzt wird der endgültige Hashwert verwendet, um die Bucket-Position zu finden, an der das Entry-Objekt gespeichert wird. Eintragsobjekt wird wie folgt im Bucket gespeichert (Hash, Schlüssel, Wert, Bucketindex) 

Ich werde nicht näher auf die Funktionsweise von HashMap eingehen, sondern ein Beispiel geben, damit wir uns daran erinnern können, wie HashMap funktioniert, indem wir es mit der Realität in Beziehung setzen.

Wir haben Key, Value, HashCode und Bucket.

Für einige Zeit werden wir jeden von ihnen mit den folgenden Angaben beziehen:

• Eimer -> Eine Gesellschaft
• HashCode -> Adresse der Gesellschaft (eindeutig immer)
• Wert -> Ein Haus in der Gesellschaft
• Schlüssel -> Hausadresse.

Verwenden von Map.get (Schlüssel):

Stevie möchte zum Haus seines Freundes (Josse), der in einer Villa in einer VIP -Gesellschaft lebt, die JavaLovers Society sein. Josse's Adresse ist seine SSN (was für jeden anders ist). Es gibt einen Index, in dem wir den Namen der Society basierend auf SSN herausfinden. Dieser Index kann als ein Algorithmus zum Herausfinden betrachtet werden der Hashcode.

• Der Name der SSN-Gesellschaft
• 92313 (Josse's) - JavaLovers
• 13214 - AngularJSLovers
• 98080 - JavaLovers
• 53808 - Biologieliebhaber

1. Dieser SSN (Schlüssel) gibt uns zunächst einen HashCode (aus der Indextabelle), der nichts anderes als der Name der Society ist.
2. Nun können sich mehrere Häuser in derselben Gesellschaft befinden, so dass der Hashcode allgemein sein kann.
3. Angenommen, die Gesellschaft ist für zwei Häuser üblich. Wie sollen wir herausfinden, in welchem ​​Haus wir uns befinden, ja, indem Sie den (SSN) -Schlüssel verwenden, der nur die Hausadresse ist

Map.put verwenden (Schlüssel, Wert)

Dies findet eine geeignete Gesellschaft für diesen Wert, indem der HashCode gefunden wird und der Wert dann gespeichert wird.

Ich hoffe das hilft und das ist offen für Modifikationen.

zwei Objekte sind gleich, impliziert, dass sie denselben Hashcode haben, nicht jedoch umgekehrt

Java 8 Update in HashMap-

sie machen diese Operation in Ihrem Code - 

myHashmap.put("old","key-value-pair");
myHashMap.put("very-old","old-key-value-pair");

nehmen Sie also an, Ihr Hashcode, der für die beiden Schlüssel "old" und "very-old" zurückgegeben wird, ist identisch. Was wird dann passieren?.

myHashMap ist eine HashMap und es wurde angenommen, dass Sie anfangs keine Kapazität angegeben haben. Die voreingestellte Kapazität laut Java ist also 16. Sobald Sie nun die Hashmap mit dem neuen Schlüsselwort initialisiert haben, wurden 16 Buckets erstellt. jetzt, wenn Sie die erste Anweisung ausgeführt haben

myHashmap.put("old","key-value-pair");

dann wird der Hashcode für "old" berechnet, und da der Hashcode auch eine sehr große Ganzzahl sein kann, hat Java dies intern getan - (Hash ist hier Hashcode und >>> ist Rechtsverschiebung)

hash XOR hash >>> 16

wenn Sie also ein größeres Bild angeben, wird ein Index zurückgegeben, der zwischen 0 und 15 liegen würde. Jetzt wird Ihr Schlüsselwertpaar "old" und "key-value-pair" in die Schlüssel- und Wertinstanzvariable des Eintragsobjekts konvertiert. Dann wird dieses Eintragsobjekt im Bucket gespeichert, oder Sie können sagen, dass an einem bestimmten Index dieses Eintragsobjekt gespeichert würde.

FYI- Entry ist eine Klasse in Map-Interface Map.Entry mit dieser Signatur/Definition

class Entry{
          final Key k;
          value v;
          final int hash;
          Entry next;
}

jetzt, wenn Sie die nächste Anweisung ausführen - 

myHashmap.put("very-old","old-key-value-pair");

und "very-old" gibt den gleichen Hashcode wie "old" aus, sodass dieses neue Schlüsselwertpaar erneut an denselben Index oder denselben Bucket gesendet wird. Da dieser Bucket jedoch nicht leer ist, wird die Variable next des Entry-Objekts zum Speichern dieses neuen Schlüsselwertpaares verwendet.

und diese wird als verknüpfte Liste für jedes Objekt gespeichert, das den gleichen Hashcode hat, aber TRIEFY_THRESHOLD wird mit dem Wert 6 angegeben. Nach diesem Erreichen wird die verknüpfte Liste in den ausgeglichenen Baum (rot-schwarzer Baum) mit dem ersten Element als konvertiert Wurzel.

Ein Bild sagt mehr als 1000 Wörter. Ich sage: etwas Code ist besser als 1000 Wörter. Hier ist der Quellcode von HashMap. Methode erhalten:

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

Es wird also klar, dass Hash zum Finden des "Buckets" verwendet wird und das erste Element immer in diesem Bucket überprüft wird. Wenn nicht, wird equals des Schlüssels verwendet, um das tatsächliche Element in der verknüpften Liste zu finden.

Sehen wir uns die put()-Methode an:

  /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

Es ist etwas komplizierter, aber es wird deutlich, dass das neue Element an der Position, die auf Basis von Hash berechnet wurde, in den Tab eingefügt wird:

i = (n - 1) & hash hier i ist der Index, in den das neue Element eingefügt wird (oder es ist der "Bucket"). n ist die Größe des tab-Arrays (Array von "Buckets").

Zuerst wird versucht, als erstes Element in diesem "Eimer" eingefügt zu werden. Wenn bereits ein Element vorhanden ist, hängen Sie einen neuen Knoten an die Liste an.