Przechodzimy do ostatniego typu kolekcji, który będzie omawiać czyli interfejs Map. Mapy to obiekty, które przechowują dane w postaci dwójki klucz-wartość. To najważniejsza zmiana w stosunku do poprzednio przedstawionych kolekcji. Klucz jest swego rodzaju identyfikatorem i to na jego podstawie zwracana jest wartość. Artykuł jest częścią wpisów o kolekcjach w Javie.

Interfejs Map

Zarówno klucz jak i wartość mogą być dowolnymi typami obiektowymi. np. <String,Zywnosc> – odpowiednio klucz, wartość. Klucze muszą być wartościami unikatowymi tzn. jeden klucz nie może wskazywać na kilka wartości. Jeżeli nastąpi próba przypisania do tego samego klucza innej wartości, to zastąpi ona tę, na którą wskazywał dotychczas klucz. Aby uzyskać żądaną wartość należy podać klucz, który jednoznacznie na nią wskazuje.

Najważniejsze klasy, które implementują mapy w Javie to.

• HashMap – mapa, która wyszukuje klucz, który najpierw przetwarza przy pomocy funkcji skrótu (metody hashCode()). Elementy kolekcji nie są posortowane.
• TreeMap – przechowuje elementy w strukturze drzew czerwono-czarnych.
• AbstractMap – zawiera definicje metod interfejsu Map – przydatne w przypadku własnej implementacji interfejsu Map, gdyż zwalnia z programisty obowiązek definiowania wszystkich metod.

AbstractMap

Jest to klasa, która implementuje podstawowe metody takie jak dodawanie, usuwanie, wyszukiwanie elementów w mapie. Jest wygodna w przypadku, gdy programista potrzebuje własnej implementacji interfejsu Map w szczególności konkretnej metody. Wtedy wystarczy opracować jej kod, a reszta jest dostarczona przez tę klasę.

Konstruktor

AbstractMap() – pusta mapa.

HashMap

Klasa wykorzystująca do swojego działania tzw. tablicę mieszającą (ang. hash table). Każdy klucz przy pomocy metody hashCode() jest przetwarzany na wartość zwaną kodem mieszającym (ang. hash code). Czas wykonywania podstawowych operacji jest stały (dodawanie, usuwanie, dostęp).

Początkowa pojemność

Iteracja po całej kolekcji jest zależna od jej pojemności (nie tylko od liczby par klucz-wartość). Dlatego przy ustawianiu początkowej wartości należy zachować umiar i dostosować ją do potrzeb. Ze względów wydajnościowych warto ustawić wartość jak najbliżej odpowiadającej zapotrzebowaniu.

Z drugiej strony, jeżeli tablica zostanie przepełniona, to potrzebne będzie utworzenie nowej – większej tablicy (potęgi liczby 2) i przeniesieniu w nowe miejsce wszystkich elementów ze starej tablicy, a jest to kosztowna operacja

Współczynnik zapełnienia

Parametrem, który odpowiada za automatyczne powiększanie tablicy jest współczynnik zapełnienia tablicy (ang. load factor) – wartość zmiennoprzecinkowa typu float. To ona decyduje jaka część tablicy musi zostać zapełniona, aby potrzebna była jej reorganizacja. Standardowa jej wartość wynosi 0.75, jednakże tę wartość możemy ustalać sami.

Konstruktory

HashMap() – pusta mapa.

HashMap(int initialCapacity) – mapa o podanej w parametrze pojemności i współczynniku załadowania równym 0.75.

HashMap(int initialCapacity, float loadFactor) – pusta mapa o podanej w parametrze pojemności i współczynniku załadowania zdefiniowanym przez programistę.

HashMap(Map<? extends K,? extends V> map) – tworzy kolekcję oraz wstawia do niej elementy map.

Metody

int size() – zwraca liczbę par klucz-wartość.

boolean isEmpty() – sprawdza czy istnieje jakakolwiek para klucz-wartość. Jeśli tak zwraca true.

V get(Object key) – zwraca wartość przypisaną do klucza (możliwa wartość null).

V get(Object key) – zwraca wartość przypisaną do danego klucza (możliwa wartość null).

V put(K key, V value) – wstawia parę klucz-wartość do mapy. Jeżeli klucz posiadał wcześniej przypisaną wartość, to jest ona aktualizowana.

V remove(Object key) – usuwa wartość przypisaną do klucza.

Collection<V> values() – zwraca wszystkie wartości z mapy bez kluczy.

void clear() – usuwa wszystkie pary z mapy.

Set<K> keySet() – zwraca wszystkie klucze z mapy bez wartości.

Set<Map.Entry<K,V>> entrySet() – zwraca wszystkie pary klucz-wartość.

Przykład użycia

Wynik wykonania powyższego kodu jest następujący.

Przykład pokazuje, że jeden klucz zawsze wskazuje na konkretną wartość. W przypadku wykonamy metodę put(klucz,wartość) i podamy ponownie ten sam klucz, to nowa wartość zastąpi poprzednią. Wartość null może być kluczem tylko raz, natomiast jako wartość można ją przypisać wiele razy.

TreeMap

W kolekcji TreeMap dwójki <klucz, wartość> są uporządkowane przez porównywanie kluczy. Sortowanie może być naturalne (ang. natural ordering) lub na podstawie własnego komparatora.

Wysoką wydajność wyszukiwania zapewniają zaimplementowane drzewa czerwono-czarne, których złożoność można oszacować jako przybliżone O(log(n)).

W przypadku tej kolekcji nie można podawać wartości null jako klucza pary <klucz,wartość>.

Konstruktory

TreeMap() – tworzy pustą mapę opartą na drzewach czerwono-czarnych. Porządkowanie odbywa się w sposób naturalny.

TreeMap(Comparator<? super K> comparator) – tworzy pustą mapę opartą na drzewach czerwono-czarnych. Porządkowanie zapewnia komparator dostarczony jako parametr.

TreeMap(SortedMap<K,? extends V> map) – tworzy mapę i uzupełnia ją elementami z mapy podanej w parametrze.

Metody

Kolekcja TreeMap oferuje te same metody, co HashMap. W związku z tym opiszemy tylko te, które są dostępne jedynie w strukturze drzewiastej.

Map.Entry<K,V> firstEntry() – zwraca parę klucz-wartość, której klucz jest „najmniejszym” elementem mapy.

K firstKey() – zwraca klucz, który jest najmniejszy w mapie.

Map.Entry<K,V> lastEntry() – zwraca parę klucz-wartość, której klucz jest „największym” elementem mapy.

K lastKey() – zawraca klucz, który jest największy w mapie.

Przykład użycia

Wynik wykonania powyższego kodu jest następujący

Jak widać program działa identycznie do momentu próby dodania pary o kluczu null. Ze względu na sposób sortowania elementów w drzewie nie jest możliwe dodanie takiego węzła.

HashMap vs TreeMap

Kolekcja HashMap jest szybsza przy dodawaniu,ale można jej użyć tylko gdy nie jest potrzebne żadne sortowanie elementów. Drzewa czerwono-czarne ze względu na algorytmy optymalizujące liczbę poziomów obu poddrzew mogą spowolnić dodawanie elementów.

Jednakże TreeMap może korzystnie wpłynąć na czas odnajdywania elementów.