Was ist der Unterschied in der Hash-Map von Java 7 und Java 8, wenn beide mit einem Algorithmus mit konstanter Komplexität arbeiten? Nach meinem Verständnis sucht Hash-Karte in konstanter Zeit durch Erzeugen eines Hash-Schlüssels für ein Objekt durch Hash-Funktion.Unterschied in der Hash-Map in Java 7 und 8
In Java 7 nach der Berechnung Hash von Hash-Funktion, wenn mehr als ein Element den gleichen Hash hat als sie durch lineare Suche gesucht werden, so ist es Komplexität ist (n). In Java 8 wird diese Suche durch binäre Suche durchgeführt, so dass die Komplexität log (n) wird. Dieses Konzept ist falsch, dass die Hash-Karte ein Objekt in konstanter Komplexität durchsucht, weil dies nicht immer der Fall ist.
Tatsächlich gibt es einen Schwellenwert, es wird in JEP180 beschrieben, wenn ein einzelner Bucket/Bin hat mehr als TREEIFY_THRESHOLD = 8 Einträge wird in einen Baum umgewandelt. In Java 7, wo Kollisionen linear durchsucht wurden, gab es einen DOS-Schutz: ein zufälliges Seed Xord mit den Hashes, um sie weniger vorhersagbar zu machen. Diese Funktion wurde in Java 8 entfernt. – eckes
Wenn wir in die Implementierung gehen, ist es genau das, was Sie @eckes erklärt haben – MDaniyal
Sie könnten die neuesten Ausgaben des Java Specialist newsletter sehr hilfreich finden. Es vertieft sich im Laufe der Jahre in Java über Hashing; Zum Beispiel weisen Sie darauf hin, dass Sie besser sicherstellen sollten, dass Ihre Map-Schlüssel Comparable implementieren (wenn Sie Java8 verwenden).
@MDaniyal antwortete richtig, ohne die Phrase zu verwenden, die die Situation von zwei oder mehr Elementen mit dem gleichen Hash beschreibt: "Hash-Kollision." Wenn Sie generell Hash-Kollisionen genauer betrachten wollen, empfehle ich hier zu beginnen: https://en.wikipedia.org/wiki/Hash_table#Collision_resolution – Jeutnarg