Kolekcje kubełkowane - hashowane

HashSet - zbiór hashowany (kubełkowany)

HashSet jest najczęściej wykorzystywaną implementacją zbioru. Na początek zadajmy pytanie w jakiej kolejności zostaną wypisane elementy dodane do HashSet?

W wynikach nie ma żadnego porządku:

Powyższy output jest wynikiem działania algorytmu w oparciu o który został zaimplementowany HashSet. Chodzi o algorytm kubełkujący. Gdy wstawiamy element do HashSet obliczany jest jego hashCode(), który jest potrzebny do obliczenia numeru kubełka według wzoru: numer = hashCode() % dlugoscTablicy. Tablica to zbiór obiektów typu Entry.

Efektem takiej konstrukcji jest możliowść sprawdzenia instnienia elementu w zbiorze w czasie stałym O( 1 ). To znaczy, że czas sprawdzenia (wyszukania) elementu nie zależy od rozmiaru danych, ani ich rodzaju. Czas działania metody contains() dla małej ilość elementów.

I zdecydowanie większej:

W drugiej linijce znadjuje się liczba milisekud! Jak widać kubełkowanie znacznie przyspiesza wyszukiwanie, kosztem całkowitej utraty kolejności elementów.

HashMap mapa hashowana

Teoretycznie jest to ważniejsza kolekcja w porównaniu z HashSet'em, ponieważ HashSet został zaimplementowany za pomocy HashMap. Tak naprawdę sam algorytm kubełkowania został zaimplementowany tylko w HashMap. W HashMap również zauważymy efekt braku kolejności w wyświetlancyh wynikach.

Znaczenie metod equals() i hashCode()

Wydajność działania HashMap i HashSet zależy wprost od sposobu zaimplementowania metody hashCode(). Zmierzymy teraz czas dodania 20 000 elementów do HashSet w zależności od implementacji metody hashCode().

A teraz przesłonimy metodę hashCode() tak aby zawsze zwracała ten sam numer.

Zwróć uwagę na to, jaka jest różnica. Dlatego o poprawną implementację hashCode() po prostu trzeba dbać. Służy ona nie tylko do obliczania kubełka w przypadku zbiorów i map, ale także do porównywania elementów. Tworząc klasy zawsze musi być spełniony warunek:

a.equals( b ) ==> a.hashCode() == b.hashCode().

Jednocześnie nie znaczy to, że: a.hashCode() == b.hashCode() ==> a.equals( b )

Ten artykuł jest elementem poniższych kursów: