Heim  >  Artikel  >  Java  >  Ausführliche Erklärung und einfache Beispiele der Java-Hash-Speicherung

Ausführliche Erklärung und einfache Beispiele der Java-Hash-Speicherung

高洛峰
高洛峰Original
2017-02-03 13:12:372008Durchsuche

Java Hash Storage

Die Datenstrukturen des Hash-Speichers in Java beziehen sich hauptsächlich auf HashSet, HashMap, LinkedHashSet, LinkedHashMap und HashTable usw. Um den Hash-Speichermechanismus in Java zu verstehen, müssen wir zunächst zwei Methoden verstehen: equal() und hashCode(). Wir haben die Methode equal() und ihren Unterschied zum Vergleichsoperator „==“ in einem anderen Artikel erklärt. Bei hashCode() handelt es sich um eine in der Object-Klasse definierte Methode:

public native int hashCode();

Dies ist eine lokale Methode, die einen int-Wert zurückgibt und nicht in der Object-Klasse implementiert ist. Diese Methode wird hauptsächlich in Datenstrukturen verwendet, die Hashing verwenden, und funktioniert normalerweise mit Hash-basierten Sammlungen. Wenn Sie beispielsweise ein Objekt in einen Container einfügen (wir gehen davon aus, dass es sich um eine HashMap handelt), können Sie feststellen, ob das Objekt bereits im Container vorhanden ist Container? Wo ist das Ziel? Da der Container möglicherweise Tausende von Elementen enthält, ist es sehr ineffizient, sie mit der Methode equal() nacheinander zu vergleichen. Der Wert des Hashings liegt in der Geschwindigkeit. Der Schlüssel wird irgendwo gespeichert, sodass er schnell gefunden werden kann. Die schnellste Datenstruktur zum Speichern einer Reihe von Elementen ist ein Array. Verwenden Sie es also zum Speichern von Schlüsselinformationen (beachten Sie, dass es sich um die Schlüsselinformationen handelt, nicht um den Schlüssel selbst). Da das Array seine Kapazität jedoch nicht anpassen kann, gibt es ein Problem: Wir möchten eine unbestimmte Anzahl von Werten in der Karte speichern. Was sollen wir jedoch tun, wenn die Anzahl der Schlüssel durch die Kapazität des Arrays begrenzt ist?

Die Antwort lautet: Das Array speichert nicht den Schlüssel selbst, sondern generiert eine Zahl über das Schlüsselobjekt und verwendet sie als Index des Arrays. Diese Zahl ist der Hashcode (Hashcode). Dies ist in Object definiert und kann von der Methode hashCode() generiert werden, die von Ihrer Klasse überschrieben wird. Um das Problem der festen Array-Kapazität zu lösen, können verschiedene Schlüssel denselben Index erzeugen, ein Phänomen, das als Konflikt bezeichnet wird. Daher besteht der Prozess zum Abfragen eines Werts im Container darin, zuerst den Hash-Code des einzufügenden Objekts über hashCode () zu berechnen und dann den Hash-Code zum Abfragen des Arrays zu verwenden. Konflikte werden häufig über externe Links behandelt, das heißt, das Array speichert nicht direkt den Wert, sondern eine Liste von Werten, und dann wird eine lineare Abfrage für die Werte in der Liste durchgeführt Langsamer. Wenn die Hash-Funktion jedoch gut genug ist, gibt es an jeder Position im Array weniger Werte. Daher kann der Hash-Mechanismus schnell zu einer bestimmten Position im Array springen und dabei nur wenige Elemente vergleichen. Deshalb ist HashMap so schnell. Wir können es mit der HashMap.put()-Methode erleben:

public V put(K key, V value) {
  if (table == EMPTY_TABLE) {
   inflateTable(threshold);
  }
  if (key == null)
   return putForNullKey(value);
  int hash = hash(key);
  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;
 }

Die Hauptidee ist: im Schlüssel Wenn es nicht leer ist, wird der Hash-Code-Hash gemäß dem Schlüsselobjekt abgerufen, und dann wird der Index i des Arrays über den Hash-Code abgerufen. Durchlaufen Sie die durch Tabelle [i] dargestellte Liste und ermitteln Sie mithilfe von equal(), ob der Schlüssel vorhanden ist. Wenn er vorhanden ist, aktualisieren Sie den alten Wert mit dem neuen Wert und geben Sie den alten Wert zurück. Andernfalls fügen Sie das neue Schlüssel-Wert-Paar zu HashMap hinzu . Daraus ist ersichtlich, dass die Methode hashCode dazu dient, die Anzahl der Aufrufe der Methode equal zu reduzieren und dadurch die Programmeffizienz zu verbessern.

Hier müssen wir beachten: hashCode() muss nicht immer in der Lage sein, einen eindeutigen Identifikationscode zurückzugeben, aber die Methode equal() muss streng bestimmen, ob zwei Objekte gleich sind.

Vielen Dank fürs Lesen, ich hoffe, es kann Ihnen helfen, vielen Dank für Ihre Unterstützung dieser Website!

Ausführlichere Erklärungen und einfache Beispiele für die Java-Hash-Speicherung finden Sie auf der chinesischen PHP-Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn