w Java 8 java.util.HashMap zauważyłem zmianę from:Zmiana HashMap funkcji skrótu w Java 8
static int hash(int h) {
h ^= (h >>> 20)^(h >>> 12);
return h^(h >>> 7)^(h >>> 4);
to:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode())^(h >>> 16);
Wydaje się od kodu, że nowa funkcja jest prostszym XOR
niższych 16 bitów z górną 16 pozostawiając górne 16 bitów niezmienione, w przeciwieństwie do kilku różnych przesunięć w poprzedniej implementacji, oraz z komentarzy, że jest to mniej skuteczne w przydzielaniu wyników funkcji skrótu z ah igh liczba kolizji w niższych bitach do różnych wiader, ale oszczędza cykle procesora, wykonując mniej operacji.
Jedyną rzeczą, jaką zobaczyłem w release notes był change z połączonych listach do zrównoważonego drzewa do przechowywania kolizji klawiszy (co moim zdaniem może się zmieniło ilość czasu to miało sens, aby spędzić obliczania dobrą hash), byłem szczególnie zainteresowani widzeniem, czy na skutek zastosowania tej zmiany na dużych mapach skrótów wystąpił jakikolwiek oczekiwany wpływ na wydajność. Czy są jakieś informacje na temat tej zmiany, czy też każdy, kto ma lepszą wiedzę o funkcjach skrótu, ma pojęcie o tym, jakie mogą być skutki tej zmiany (jeśli w ogóle, być może właśnie źle zrozumiałem kod) i czy istnieje potrzeba generowania skrótu kody w inny sposób, aby zachować wydajność podczas przechodzenia do Java 8?
Gdy rozmiar "łańcucha mieszającego" przekracza limit, przesuwa się on do "zrównoważonego drzewa" z list powiązanych, aby był określony. W związku z tym najgorsze operacje przyjmują czas O (n) zamiast O (n). – darkdefender27
@ darkdefender27 - Twój komentarz nie ma sensu. 1) W jaki sposób O (n) jest lepszy niż O (n)? 2) To faktycznie idzie do O (logn)! 3) To właśnie powiedziałem w mojej odpowiedzi ... –
Och, przepraszam, miałem na myśli O (log n). Twoja odpowiedź ma całkowicie sens. Próbowałem tylko powiedzieć, że przełącza się na "zrównoważone" drzewo binarne. – darkdefender27