Zum Hauptinhalt springen

Schlüsseltransformationen (Hashing)

Schlüsseltransformation (Hashing) bezeichnet die Abbildung einer großen Datenmenge (Schlüssel) auf eine kleinere Datenmenge (Hashcode) mittels einer Hashfunktion. Der Hashcode darf dabei nur vom Zustand des Schlüssels abhängen.

Hashtabellen​

Hashtabellen sind Datenstrukturen für schnellen Zugriff. Der Index eines Eintrags wird über eine Hashfunktion berechnet, sodass Einträge gleichmäßig in der Tabelle gestreut sind. Daher werden Hashtabellen auch Streuwerttabellen genannt.

IndexSchlüsselHashcode
0Butter630
1
2Brot407
3Milch493
4Eier389

Hashfunktionen​

Eine Hashfunktion berechnet aus einem Schlüssel (Hashcode) einen Tabellenindex. Die beiden gebräuchlichsten Verfahren sind die Divisionsrestmethode und die multiplikative Methode.

Die Divisionsrestmethode ist eine einfache und schnelle Hashfunktion. Der Index wird nach der Formel ℎ(𝑘) = 𝑘 𝑚𝑜𝑑 𝑚 berechnet.

SchlüsselHashcodeIndex
Brot407407 𝑚𝑜𝑑 5 = 2
Butter630630 𝑚𝑜𝑑 5 = 0
Milch493493 𝑚𝑜𝑑 5 = 3
Eier389389 𝑚𝑜𝑑 5 = 4
info

ℎ(𝑘) = Index, 𝑘 = Hashcode, 𝑚𝑜𝑑 = Modulo-Operation, 𝑚 = Tabellengröße

Kollisionen​

Ergibt die Hashfunktion für zwei unterschiedliche Schlüssel denselben Index, spricht man von einer Kollision. Um Kollisionen zu minimieren, müssen Tabellengröße und Hashfunktion sorgfältig gewählt werden. Für unvermeidliche Kollisionen gibt es zwei grundlegende Auflösungsstrategien.

Beim geschlossenen Hashing wird bei einer Kollision eine freie Stelle in der Hashtabelle gesucht. Beim linearen Sondieren geschieht dies mit festen Intervallschritten, beim quadratischen Sondieren wächst der Schritt quadratisch, und beim doppelten Hashing wird der Schritt über eine zweite Hashfunktion berechnet.

IndexSchlüssel
0Eier
1Brot
2
3Butter
4Milch

Hashing in Java​

Java verwendet Hashing intern in den Klassen HashMap<K, V> und HashSet<E>. Der Schlüssel eines Eintrags bestimmt über seinen Hashcode den Bucket, in dem der Eintrag abgelegt wird. Bei einer Suche wird zunächst der Bucket über den Hashcode gefunden, anschließend wird innerhalb des Buckets mit equals() verglichen.

Damit diese Mechanismen korrekt funktionieren, müssen die Methoden hashCode() und equals() der Klasse Object konsistent überschrieben werden:

  • Zwei inhaltlich gleiche Objekte (equals() gibt true zurück) müssen denselben Hashcode liefern.
  • Zwei Objekte mit demselben Hashcode müssen nicht inhaltlich gleich sein (eine Kollision ist erlaubt, aber ineffizient).
Person.java (Auszug)
public class Person {

   private String name;
   private int age;

   @Override
   public boolean equals(Object object) {
      if (this == object) return true;
      if (object == null || getClass() != object.getClass()) return false;
      Person other = (Person) object;
      return age == other.age && Objects.equals(name, other.name);
   }

   @Override
   public int hashCode() {
      return Objects.hash(name, age);
   }

}
warnung

Wird equals() überschrieben, ohne hashCode() anzupassen, verhält sich die Klasse in HashMap und HashSet falsch: Zwei inhaltlich gleiche Objekte landen in unterschiedlichen Buckets und werden nicht als gleich erkannt.