2014-07-10 33 views
10

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?

Odpowiedz

5

Jak już zauważyłeś: w Java 8 występuje znaczna poprawa wydajności, jak opisano w JEP-180. Zasadniczo, jeśli łańcuch mieszający przejdzie przez pewien rozmiar, HashMap (jeśli to możliwe) zastąpi go zbalansowanym drzewem binarnym. To sprawia, że ​​zachowanie "najgorszego przypadku" dla różnych operacji to O(log N) zamiast O(N).

Nie wyjaśnia to bezpośrednio zmiany w hash. Jednakże, musiałbym postawić hipotezę:, że optymalizacja w JEP-180 oznacza, że ​​wydajność osiągnięta z powodu źle rozproszonej funkcji hashowania jest mniej istotna, i że zmienia się analiza kosztów i korzyści dla metody hash; tj. bardziej złożona wersja jest mniej korzystna średnio. (Pamiętajcie, że gdy metoda typu klucza hashcode generuje kody wysokiej jakości, wówczas gimnastyka w złożonej wersji metody hash to strata czasu.)

Ale to tylko teoria. Prawdziwe uzasadnienie zmiany hash jest najprawdopodobniej poufne.

+0

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

+0

@ 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 ... –

+0

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

2

Kiedy wpadłem hash diffences wdrożeniowe widzę różnicę czasową w nano sekund jak poniżej (nie super, ale może mieć pewien wpływ, gdy rozmiar jest ogromny ~ 1 mln +) -

7473 ns - Java 7

3981 NS java 8

Jeśli mówimy o dobrze uformowane klawisze i HashMap duży rozmiar (~ mln), to może mieć jakiś wpływ, a to ze względu na uproszczoną logiką.

0

Dokumentacja Java mówi, że chodzi o to, aby obsłużyć sytuację, w której stara implementacja listy Linked wykonywała O (n) zamiast O (1). Dzieje się tak, gdy wygenerowany jest ten sam kod skrótu dla dużego zestawu danych wstawianych do HashMap.

To jednak nie jest normalny scenariusz. Aby poradzić sobie z sytuacją, w której po przekroczeniu pewnej wartości próg liczby elementów w haszdzie, ta zmienna zmieni listę połączonych pozycji na drzewo binarne. W przypadku kolizji o wysokiej mieszance poprawi to wydajność wyszukiwania od O (n) do O (log n), co jest znacznie lepsze i rozwiązuje problem wydajności.