Zum Hauptinhalt springen

Schlüsseltransformationen (Hashing)

Schlüsseltransformation (Hashing) bezeichnet die Abbildung eines Schlüssels auf einen Wert fester Länge, genannt 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üsselHashwert
0Butter630
1
2Brot407
3Milch493
4Eier389

Hashfunktionen​

Eine Hashfunktion berechnet aus einem Schlüssel einen Hashcode. Der Hashcode hat immer dieselbe feste Länge, unabhängig von der Größe des Schlüssels. Die beiden gebräuchlichsten Hashfunktionen für Zeichenketten sind die Zeichenweise Addition und der Polynomial Rolling Hash.

Bei der Zeichenweisen Addition werden die ASCII-Werte aller Zeichen eines Schlüssels summiert. Das Ergebnis ist der Hashcode.

SchlüsselBerechnungHashcode
Brot66+114+111+116407
Butter66+117+116+116+101+114630
Milch77+105+108+99+104493
Eier69+105+101+114389

Index-Mapping​

Eine Indexfunktion berechnet aus einem Hashcode einen Tabellenindex. Die beiden gebräuchlichsten Verfahren sind die Divisionsrestmethode und die multiplikative Methode.

Die Divisionsrestmethode ist eine einfache und schnelle Indexfunktion. 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.

Hashing von Passwörtern​

Passwörter werden niemals im Klartext gespeichert, sondern als Hashcode. Beim Login wird das eingegebene Passwort erneut gehasht und mit dem gespeicherten Hashcode verglichen. Da Hashfunktionen nicht umkehrbar sind, kann ein Angreifer aus einem gestohlenen Hashcode das ursprüngliche Passwort nicht direkt rekonstruieren.

warnung

Einfache Hashfunktionen wie MD5 oder SHA-1 sind für Passwörter ungeeignet, weil sie sehr schnell berechnet werden können. Angreifer können mit sogenannten Brute-Force- oder Rainbow-Table-Angriffen Millionen von Kandidaten pro Sekunde testen. Für Passwörter werden bewusst langsame Algorithmen wie bcrypt, scrypt oder Argon2 eingesetzt.

info

Um zu verhindern, dass zwei Nutzer mit demselben Passwort denselben Hashcode erhalten (was Rainbow-Table-Angriffe erleichtert), wird dem Passwort vor dem Hashen ein zufälliger Wert — das sogenannte Salt — vorangestellt.

Abgrenzung: Hashing, Encoding und Encryption​

Die Begriffe Hashing, Encoding und Encryption werden häufig verwechselt, haben aber grundlegend unterschiedliche Eigenschaften und Einsatzzwecke.

EigenschaftHashingEncodingEncryption
UmkehrbarNeinJaJa (mit Schlüssel)
Schlüssel nötigNeinNeinJa
AusgabelängeFestVariabelVariabel
ZweckIntegrität, SucheDarstellungVertraulichkeit
BeispieleSHA-256, bcryptBase64, UTF-8AES, RSA

Hashing ist eine Einwegfunktion: Der ursprüngliche Wert lässt sich aus dem Hashcode nicht wiederherstellen. Es wird eingesetzt, um Integrität zu prüfen (z. B. Prüfsummen) oder Daten effizient zu suchen (Hashtabellen).

Encoding wandelt Daten in eine andere Darstellung um — ohne Geheimhaltung und vollständig umkehrbar. Base64 kodiert z. B. Binärdaten in druckbare ASCII-Zeichen, damit sie in E-Mails oder URLs übertragen werden können.

Encryption (Verschlüsselung) macht Daten für Dritte unlesbar und erfordert einen Schlüssel zur Entschlüsselung. Symmetrische Verfahren wie AES verwenden denselben Schlüssel zum Ver- und Entschlüsseln; asymmetrische Verfahren wie RSA nutzen ein Schlüsselpaar (öffentlich/privat).