Warum Hash-Maps in Java 8 binäre Baum statt verknüpfte Liste verwenden? [geschlossen]

Dies ist hauptsächlich sicherheitsrelevante Änderung. In normalen Situationen ist es selten möglich, viele Kollisionen zu haben, wenn Hash-Schlüssel von nicht vertrauenswürdigen Quellen kommen (zB HTTP-Header-Namen vom Client), dann ist es möglich und nicht sehr schwierig, die Eingabe speziell zu erstellen gleicher Hashcode. Wenn Sie nun viele Suchvorgänge durchführen, kann es zu einem Denial-of-Service kommen. Es scheint, dass es ziemlich viel Code in der Wildnis gibt, der für diese Art von Angriffen anfällig ist, daher wurde beschlossen, dies auf der Java-Seite zu beheben.

Weitere Informationen finden Sie unter JEP-180 .

Ihre Frage enthält falsche Voraussetzungen.

1. Eine Bucket-Kollision ist nicht unbedingt eine Hash-Kollision. Sie müssen nicht den gleichen Hashcode für zwei Objekte haben, um im selben Bucket zu landen. Der Bucket ist ein Element eines Arrays und der Hash-Code muss einem bestimmten Index zugeordnet werden. Da die Array-Größe in Bezug auf die Größe Map angemessen sein sollte, können Sie die Array-Größe nicht beliebig erhöhen, um Bucket-Kollisionen zu vermeiden. Es gibt sogar die theoretische Einschränkung, dass eine Array-Größe bei maximal 2³¹ liegen kann, während es 2²² mögliche Hash-Codes gibt.
2. Eine Hash-Kollision ist kein Zeichen für eine schlechte Programmierung. Für alle Objekte mit einem Wertebereich größer als 2³² ist die Möglichkeit von verschiedenen Objekten mit dem gleichen Hash-Code unvermeidlich. String s sind ein offensichtliches Beispiel, aber sogar ein Point mit zwei int -Werten oder ein einfacher Long -Schlüssel haben unvermeidbare Hash-Kollisionen. Sie können also häufiger vorkommen als Sie denken und hängt stark vom Anwendungsfall ab.
3. Die Implementierung wechselt nur dann zu einem Binärbaum, wenn die Anzahl der Kollisionen in einem Bucket einen bestimmten Schwellenwert überschreitet, sodass die höheren Speicherkosten nur dann zur Anwendung kommen, wenn sie sich auszahlen. Es scheint ein häufiges Missverständnis darüber zu geben, wie sie funktionieren. Da die Bucket-Kollision nicht notwendigerweise Hash-Kollisionen sind, sucht die Binärsuche zuerst die Hash-Codes. Nur wenn die Hash-Codes identisch sind und der Schlüssel Comparable entsprechend implementiert, wird seine natürliche Reihenfolge verwendet. Die Beispiele, die Sie im Internet gefunden haben, verwenden bewusst den gleichen Hash-Code für Objekte, um die Verwendung der Comparable -Implementierung zu demonstrieren, die andernfalls nicht angezeigt würde. Was sie auslösen, ist nur der letzte Ausweg der Implementierung.
Tagir wies darauf hin , dieses Problem könnte die Sicherheit einer Software beeinträchtigen, da ein langsames Fallback die Möglichkeit eröffnen könnte DoS-Angriffe. In früheren JRE-Versionen gab es mehrere Versuche, dieses Problem anzugehen, das mehr Nachteile als der Speicherverbrauch eines Binärbaums hatte. Zum Beispiel wurde versucht, die Zuordnung von Hash-Codes zu Array-Einträgen in Java 7 zu randomisieren, was zu einem Initialisierungsaufwand führte, wie in Dieser Fehlerbericht . Dies ist bei dieser neuen Implementierung nicht der Fall.