JavaRush /Java-Blog /Random-DE /Wie funktioniert HashMap in Java?
gnev
Level 24

Wie funktioniert HashMap in Java?

Veröffentlicht in der Gruppe Random-DE
Wie funktioniert HashMap in Java?  - 1Sehr oft stellen sie in Interviews Fragen wie „ Wie funktioniert HashMap in Java?“ “, „Was ist der interne Mechanismus, wie Methoden getin putHashMap funktionieren?“. Hier werde ich versuchen, die interne Funktionsweise anhand eines einfachen Beispiels zu erklären. Ohne zu sehr auf die Theorie einzugehen, beginnen wir mit einem Beispiel, damit Sie besser verstehen und dann sehen können, wie Methoden getauch putin Java funktionieren. Nehmen wir ein ganz einfaches Beispiel. Wir haben eine Klasse Country(englisch „Land“), wir verwenden das Klassenobjekt Countryals Schlüssel und den Namen der Hauptstadt dieses Landes als Wert. Nachfolgend finden Sie ein Beispiel, das uns helfen soll zu verstehen, wie ein Schlüssel-Wert-Paar in einer Hash-Map gespeichert wird.

1. Land.java

package org.arpit.javapostsforlearning;
public class Country {

 String name;
 long population;

 public Country(String name, long population) {
  super();
  this.name = name;
  this.population = population;
 }
 public String getName() {
  return name;
 }
 public void setName(String name) {
  this.name = name;
 }
 public long getPopulation() {
  return population;
 }
 public void setPopulation(long population) {
  this.population = population;
 }

 // если длина имени в ein Objektе Country - четное число,
 // то возвращаем 31(любое случайное число), а если нечетное - 95 (любое случайное число).
 // указанный ниже метод - это не самый лучший способ генерации хеш-Codeа,
 // но мы воспользуемся им для более четкого понимания хеш-карт.

 @Override
 public int hashCode() {
  if(this.name.length()%2==0)
   return 31;
  else
   return 95;
 }
 @Override
 public boolean equals(Object obj) {

  Country other = (Country) obj;
   if (name.equalsIgnoreCase((other.name)))
   return true;
  return false;
 }
}
Wenn Sie mehr über Methoden und Gleichberechtigung erfahren möchten hashcode, können Sie diesem Link folgen .

2. HashMapStructure.java (Hauptklasse)

import java.util.HashMap;
import java.util.Iterator;

public class HashMapStructure {

    /**
     * @author Arpit Mandliya
     */
    public static void main(String[] args) {

        Country india=new Country("India",1000);
        Country japan=new Country("Japan",10000);

        Country france=new Country("France",2000);
        Country russia=new Country("Russia",20000);

        HashMap<country,string> countryCapitalMap=new HashMap<country,string>();
        countryCapitalMap.put(india,"Delhi");
        countryCapitalMap.put(japan,"Tokyo");
        countryCapitalMap.put(france,"Paris");
        countryCapitalMap.put(russia,"Moscow");

        Iterator<country> countryCapitalIter=countryCapitalMap.keySet().iterator();//установите
        //debug-точку на этой строке(23)
        while(countryCapitalIter.hasNext())
        {
            Country countryObj=countryCapitalIter.next();
            String capital=countryCapitalMap.get(countryObj);
            System.out.println(countryObj.getName()+"----"+capital);
            }
        }
}
Setzen Sie nun den Haltepunkt auf Zeile 23 und führen Sie Ausführen -> Debuggen als -> Java-Anwendung aus (Anmerkung des Übersetzers – gültig für Eclipse). Das Programm stoppt die Ausführung in Zeile 23. Klicken Sie anschließend mit der rechten Maustaste auf „ countryCapitalMap“ und wählen Sie „watch“ aus . Sie sehen eine Tabelle wie diese: Wie funktioniert HashMap in Java?  - 2Hier sehen wir Folgendes:
  1. Es gibt ein Array Entry[]mit 16 Zellen mit dem Namen table;

  2. In diesem Array werden Objekte der Klasse gespeichert Entry. Die Klasse HashMaphat eine innere Klasse – Entry. Und Instanzen dieser Klasse sind Schlüssel-Wert-Paare. Werfen wir einen Blick auf die Klassenstruktur Entry:

  3. static class Entry implements Map.Entry
            {
                    final K key;
                    V value;
                    Entry next;
                    final int hash;
                    ...//продолжение Codeа
            }
  4. Jedes Mal, wenn wir versuchen, ein Schlüssel-Wert-Paar in einer Hash-Map zu erstellen, wird ein Klassenobjekt für dieses Paar erstellt Entryund in der obigen Tabelle gespeichert Entry[]. Und jetzt sollten Sie sich fragen, wo genau in dieser Tabelle dieses Objekt geschrieben wird (in welche Zelle). Für einen Schlüssel in einem Schlüssel-Wert-Paar wird mithilfe von ein Hash-Code berechnet hashcode(). Und dieser Hash-Code wird verwendet, um die Tabellenzellennummer zu berechnen Entry[];

  5. Wenn Sie sich nun Zelle 10 der Tabelle ansehen, sehen Sie ein Klassenobjekt Entrymit dem Namen HashMap$Entry;

  6. Wir haben 4 Schlüssel-Wert-Paare hinzugefügt, aber es sind nur 2 im Array!!! Denn wenn zwei Objekte denselben Hash-Code haben, werden sie in derselben Zelle gespeichert. Aber wie? Objekte werden als verknüpfte Liste ( LinkedList) gespeichert.
So wird der Hash-Code für unsere Schlüssel-Wert-Paare berechnet.
Hashcode for Japan = 95 так Wie длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так Wie длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так Wie длина слова Russia имеет четное количество букв.
HashCode for France = 31 так Wie длина слова France имеет четное количество букв.
Die folgende Abbildung erläutert die Idee einer verknüpften Liste: Wie funktioniert HashMap in Java?  - 3Nachdem Sie nun bereits ein Verständnis für die Struktur von Hash-Maps haben, gehen wir zu den Methoden putund über get.

Setzen:

Sehen wir uns an, wie diese Methode verwendet wird:
/**
  * Метод связывает указанное Bedeutung с указанным ключом в данной хэш-карте. Если
  * карта до этого уже содержала некоторое Bedeutung, соответствующее этому ключу,
  * то старое Bedeutung заменяется на указанное.
  * @param key
  *            ключ, с которым связывается указанное Bedeutung
  * @param value
  *            Bedeutung, связываемое с указанным ключом
  * @возвращает Bedeutung связанное с <tt>ключом</tt>, oder <tt>null</tt>,
  *         если ниWieое Bedeutung не соответствует <tt>ключу</tt>. ( Возврат <tt>null</tt>
  *         может так же говорить о том, что в карте заведомо <tt>null</tt> был связан с
  *         <tt>ключом</tt>.)
  */
 public V put(K key, V value) {
  if (key == null)
   return putForNullKey(value);
  int hash = hash(key.hashCode());
  int i = indexFor(hash, table.length);
  for (Entry<k , V> e = table[i]; e != null; e = e.next) {
   Object k;
   if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
   }
  }

  modCount++;
  addEntry(hash, key, value, i);
  return null;
 }
Versuchen wir nun, diesen Code Schritt für Schritt zu verstehen:
  1. Wir prüfen das Objekt keyauf Gleichheit null. Wenn ja, wird das Objekt keyam Speicherort gespeichert table[0], da der Hash-Code für nullimmer 0 ist.

  2. Als nächstes rufen wir die keyMethode des Objekts auf hashcode(), die seinen Hash-Code berechnet. Dieser Hash-Code wird verwendet, um die Array-Zelle zu bestimmen, in der das Klassenobjekt gespeichert wird Entry. Manchmal kommt es vor, dass diese Funktion hashcodenicht sehr geschickt geschrieben ist, daher haben die JDK-Entwickler eine andere Funktion erstellt – hash(), die den zuvor berechneten Hash-Code als Argument verwendet. Wenn Sie mehr über diese Funktion erfahren möchten, können Sie dem Link folgen .

  3. indexFor(hash,table.length)wird verwendet, um eine bestimmte Zelle im Array zu definieren, tablein der ein Klassenobjekt zur Speicherung definiert wird Entry;

  4. Wie wir in unserem Beispiel gesehen haben, werden zwei Objekte, wenn sie keydenselben Hash-Code haben (diese Situation wird als Kollision bezeichnet), in Form einer verknüpften Liste gespeichert. Daher wiederholen wir in dieser Phase unsere Liste:

    • EntryWenn die neu berechnete Zelle leer ist, wird das Klassenobjekt direkt in dieser Zelle gespeichert.

    • Wenn diese Zelle bereits ein Objekt enthält, wird zu dem Element iteriert, dessen Feld nextgleich ist null. Danach Entrysteht unser Klassenobjekt als nächstes in der Liste;

    • Was ist, wenn wir dasselbe Objekt keyerneut hinzufügen? Logischerweise sollte es den alten Wert ersetzen. Ja, das wird so sein. Während der Iteration werden die Schlüssel mit der Methode equals()( key.equals(k)) verglichen. Wenn das Ergebnis wahr ist, wird der alte Wert durch den Wert des aktuellen Objekts ersetzt Entry.

Erhalten:

Schauen wir uns nun die Anwendung der Methode an erhalten
/**
  * kehrt zurück Bedeutung, которое соответствует указанному ключу, oder {@code null}, если
  * данная карта не содержит пары с указанным ключом.
  *
  *
  * <p>
  * Более точно, если в данной карте содержится такой ключ {@code k}
  * с соответствующим ему Bedeutungм {@code v}, что {@code (key==null ? k==null : key.equals(k))},
  * то метод возвращает {@code v}; в противном случае возвращается {@code null}.
  * (может быть не более одной такой пары)
  *
  * </p><p>
  * Возвращенное Bedeutung {@code null} не <i>обязательно</i> говорит о том, что
  * в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно
  * указано соответствие этого ключа со Bedeutungм {@code null}.
  * Можно воспользоваться операцией {@link #containsKey containsKey}, чтобы
  * отличить эти два случая
  * @see #put(Object, Object)
  */
 public V get(Object key) {
  if (key == null)
   return getForNullKey();
  int hash = hash(key.hashCode());
  for (Entry<k , V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
   Object k;
   if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
    return e.value;
  }
  return null;
 }
Nachdem Sie nun verstanden haben, wie die Put-Methode in Hashmaps funktioniert, ist es getsehr einfach, zu verstehen, wie die Put-Methode funktioniert. Wenn Sie einen beliebigen Schlüssel an eine Methode übergeben, um einen Wert aus einer Hash-Map abzurufen:
  1. Ein Objekt Ekey ist auf Gleichberechtigung geprüft null. Wenn ja, wird der Wert des in der Zelle gespeicherten Objekts zurückgegeben table[0];

  2. Das Schlüsselobjekt verfügt über eine Methode namens hashcode(), die den Hash-Code berechnet.

  3. indexFor(hash,table.length)Wird verwendet, um eine bestimmte Array-Zelle zu bestimmen, tableaus der ein Klassenobjekt entnommen werden soll Entry.

  4. Nach Erhalt der Array-Zellennummer tablewird die Liste durchlaufen und die Schlüssel mithilfe der Methode verglichen equals(). Wenn das Ergebnis wahr ist, wird der Wert des Objekts zurückgegeben Entry, andernfalls - null.

Dinge, die Sie sich merken sollten:

  • Die Klasse HashMapverfügt über eine innere Klasse Entry, die Schlüssel-Wert-Paare speichert;

  • Objekte der Klasse werden in einem Array mit dem Namen Entrygespeichert ;Entry[ ]table

  • Eine Array-Zelle wird als Bucket bezeichnet und speichert das erste Element einer verknüpften Liste;

  • Die Objektmethode wird verwendet hashcode(), keyum den Bucket dieses Klassenobjekts zu finden Entry.

  • Wenn die Schlüssel zweier Objekte denselben Hash-Code haben, werden sie im selben Array-Bucket gespeichert table.

  • Die Methode eines equals()Objekts keywird verwendet, um seine Einzigartigkeit zu bestätigen.

  • Methoden equals()und hashcode()Objekte valuewerden überhaupt nicht verwendet.

Quelle
Kommentare
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION