TreeMap i HashMap - różnica

0

Czym różnią się te 2 kolekcje w Javie? Czytałem dokumentację, ale nie rozumiem:(

Czy jeśli w zadaniu zamiast HashMap zastosuję TreeMap będzie to działało tak samo?

0

Obie mają ten sam zestaw metod udostępniany przez interjfejs Map. Różnią się tylko tym w jaki sposób przechowują dane i w konsekwencji jakie są czasy wykonywania operacji.
Z punktu widzenia kodu których z tych kolekcji używa nie ma problemu z podmienieniem jednej mapy na inną (o ile wszędzie deklarujesz ją jako Map a nie jako konkretną klasę)
HashMap przechowuje dane w tablicy hashującej. Wyciąganie danych z takiej tablicy powinno odbywać się w średnim czasie O(1) (ale pesymistycznie może to być O(n))
TreeMap przechowuje dane w zrównoważonym drzewie binarnym. Wyciąganie danych z takiego drzewa odbywa się w czasie nie większym niż O(logn).

0

Przede wszystkim TreeMap jest posortowana i wypisywanie foreachem z niej będzie w kolejności rosnącej - oczywiście rosnącej względem podanej funkcji porównującej.
Poza tym złożoności jak kolega napisał powyżej. W HashMapie dostęp do konkretnej komórki ma czas oczekiwany stały. Dodanie elementu też, ale jeżeli dodamy element do pełnej hashmapy to hashmapa musi zrobić drugą, większa tablicę, przenieść do niej elementy i usunąć starą. A więc o ile nie ustawisz dobrze (albo nie będziesz miał możliwości przewidzieć) z góry wielkości hashmapy to niektóre dodania mogą mieć złożoność Theta(n).
Po szczegóły odsyłam do wikipedii. HashMap to tablica haszująca, a TreeMap to drzewo zrównoważone, w Javie to pewnie czerwono-czarne.

0

Fragment dokumentacji klasy TreeMap

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0