Kolekcje mieszające w Javie, część 1

(ang. Hashing collections in Java, part 1)

Często na rozmowach kwalifikacyjnych zadaję pytanie „Jak działają kolekcje mieszające (ang. hashing) w Javie?”. Niestety bardzo rzadko zdarza się, że kandydat lub kandydatka potrafi udzielić poprawnej odpowiedzi na ten temat. Dlaczego zadaję takie pytanie? Czy ta wiedza jest potrzebna do programowania? Czasem ktoś stwierdza, że programuje od wielu lat i ta wiedza nie jest do niczego potrzebna.

Według mnie znajomość takich zagadnień świadczy o podejściu osoby do programowania. Pomaga odróżnić programistę od tzw. kodera, czyli osoby, która poznał trochę API i „pisze kod”. Jednak kod, który się kompiluje i nawet realizuje założone wymagania może być daleki od dobrze napisanego kodu.

Do brzegu

W dzisiejszym wpisie omówię kolekcje haszujące. Będzie to znacznie obszerniejsze wyjaśnienie od tego, czego oczekiwałbym w odpowiedzi od kandydata. Niemniej jednak myślę, że warto zapoznać z tematem dogłębnie. Być może zachęci to was do zapoznania się również z innymi zagadnieniami języka Java w bardziej dociekliwy sposób.

Po co nam kolekcje mieszające?

Zanim dowiemy się jak działają kolekcje mieszające warto zastanowić się jakie zalety posiadają? Innymi słowy dlaczego warto ich używać? Chodzi oczywiście o optymalizację, ale optymalizację czego? Wszystkiego? Prawie. Dobrze zaimplementowana funkcja mieszająca (o tym później) pozwala na szybkie znajdowanie elementów w kolekcji. Większość operacji na kolekcjach (a w szczególności na zbiorach) opiera się na znajdowaniu elementów: dodawanie, modyfikowanie, usuwanie, itp. Także w dużym stopni optymalizuje to większość operacji na kolekcjach.

Kubełki... czyli jak to działa w prostych słowach?

Za każdym razem na rozmowie kwalifikacyjnej słyszę, że elementy trafiają do odpowiednich „kubełków”? Na początek wyobraźmy sobie kolekcję, która nie korzysta z funkcji mieszającej. W jaki sposób możemy znaleźć dany obiekt w takiej kolekcji? Zastanów się przez chwilę…

Wyobraź sobie teraz duży budynek, w którym przebywa np. jedenaście różnych osób. Chcesz znaleźć osobę o imieniu Marek. Nie wiesz jak Marek wygląda, ani w którym miejscu się znajduje (wewnątrz budynku). Wchodzisz więc do środka i pytasz każdą osobę po kolei czy ma na imię Marek?

Tak samo działa kolekcja. Sprawdza każdy element za pomocą metody equals() czy jest tym elementem, którego szuka. Czyli innymi słowy porównuje obiekt wzorcowy (poszukiwany) z każdym obiektem kolekcji po kolei.

Nie jest to najlepsza metoda. Co można zrobić, aby łatwiej i szybciej znaleźć Marka? Możemy podzielić przestrzeń w budynku na pokoje, w których będę przebywać poszczególne osoby. Każdy pokój będzie miał też przypisany kolejny numer. W takim przypadku wiedząc, w którym pokoju przebywa Marek możesz udać się od razu we właściwe miejsce – do konkretnego pokoju. Nie musisz wchodzić do każdego pokoju i pytać się czy jest tutaj Marek? :). Numer pokoju to właśnie wartość zwracana przez funkcję mieszającą.

Numer pokoju to właśnie nasz kod mieszający (hashCode). Jest on wyliczany przez metodę hashCode() dla każdego obiektu na podstawie jego właściwości. Poprawna implementacja metody hashCode() powinna zwracać unikalne wartości dla unikalnych obiektów. Tak, aby nie dochodziło to kolizji.

Kolizje

W idealnej sytuacji w pokoju nr 10 (a w zasadzie w każdym) znajduje się (co najwyżej) tylko jedna osoba. Wiadomo wtedy od razu, że jest to Marek. Jeśli jednak w pokoju nr 10 będzie przebywać kilka różnych osób, wtedy mamy do czynienia z tzw. kolizją. Czyli funkcja haszująca zwróciła tę samą wartość dla kilku różnych obiektów. Wtedy wchodząc do pokoju nr 10 musisz zapytać każdą osobę czy ma na imię Marek? Jest to i tak lepsza sytuacja niż pytanie o imię wszystkich osób w całym budynku :).

W kupie raźniej? Oczywiście, że nie 🙂

Najgorszym z możliwych przypadków jest zaimplementowanie funkcji mieszającej zwracającą stałą wartość, np. 10. Wtedy wszystkie osoby będę siedziały w jednym i tym samym pokoju. Nie jest to implementacja błędna (kod dalej będzie działał i się kompilował). Jednak jest dalece niepoprawna, delikatnie mówiąc ;). Efekt będzie taki, jak w przypadku kolekcji nie korzystającej z funkcji mieszającej. Czyli będziemy musieli zapytać wszystkich (w najgorszym przypadku) czy mają na imię Marek? W tym takim przypadku nasza kolekcja będzie działać podobnie jak kolekcja bez funkcji mieszającej.

W następnej części napiszemy trochę kodu obrazującego opisane do tej pory mechanizmy. Zapraszam do kolejnej części: Kolekcje mieszające w Javie, część 2

Kolekcje mieszające w Javie, część 1​
Tagi:            

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *