Kollisionen und Hash-Funktionen

Die Wahl der richtigen Hash-Funktion ist wichtig für die Performance. Denn eine »dumme« Hash-Funktion, die beispielsweise alle Schlüssel nur auf einen konstanten Wert abbildet, erreicht keine Verteilung, sondern lediglich eine lange Liste von Schlüssel-Werte-Paaren; diese Anhäufung an einer Stelle nennt sich Clustering. Doch auch bei der besten Verteilung über N Buckets ist nach dem Einfügen des Elements N + 1 irgendwo eine Liste mit mindestens zwei Elementen aufgebaut, daher vergrößert die Bibliothek standardmäßig das Feld. Ist aber die Hash-Funktion aber so schlecht, dass alles auf das gleiche Bucket abgebildet wird, hilft dieses Re-Hashing auch nicht.

Je länger die Datenstruktur der miteinander kollidierenden Einträge wird, desto langsamer wird der Zugriff der auf Hashing basierenden Datenstruktur insgesamt. Java basiert beim Hashing einzig auf der hashCode()-Methode, und es liegt in unserer Hand sie gut zu implementieren. Die Klasse String hat eine relativ einfache (dafür schnelle) Implementierung von hashCode(), die in der Vergangenheit zu Denial of Service Attacken führte gerade weil es zu Kollisionen kam.[1]


[1] In Java 7 wurde dafür in String eine zusätzliche Hash-Methode realisiert, doch in Java 8 diese Implementierung wieder entfernt und die Implementierung für das Hashing insgesamt verändert, zumindest für die aktuellen Klassen, das ältere java.util.Hashtable blieb unverändert.

Ähnliche Beiträge

Veröffentlicht in Insel

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert