Kolekcje Javy – Interfejs Map
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 (metodyhashCode()
). Elementy kolekcji nie są posortowane.TreeMap
– przechowuje elementy w strukturze drzew czerwono-czarnych.AbstractMap
– zawiera definicje metod interfejsuMap
– przydatne w przypadku własnej implementacji interfejsuMap
, 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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.util.HashMap; import java.util.Map; public class TestHashMap { public static void main(String[]args) { Map<Integer, String> solarSystem = new HashMap<>(); // Dodawanie elementów solarSystem.put(1, "Merkury"); solarSystem.put(2, "Wenus"); solarSystem.put(3, "Ziemia"); // Wyświetlenie kolekcji HashMap System.out.println(solarSystem); // Nadpisanie klucza System.out.println("Próba dodania ponownie tego samego elementu - "); solarSystem.put(3, "Księżyc"); System.out.println(solarSystem); //Usunięcie elementu o podanym kluczu solarSystem.remove(2); System.out.println(solarSystem); //Dodanie elementu null solarSystem.put(null, null); solarSystem.put(4, null); System.out.println(solarSystem); } } |
Wynik wykonania powyższego kodu jest następujący.
1 2 3 4 5 |
{1=Merkury, 2=Wenus, 3=Ziemia} Próba dodania ponownie tego samego elementu - {1=Merkury, 2=Wenus, 3=Księżyc} {1=Merkury, 3=Księżyc} {null=null, 1=Merkury, 3=Księżyc, 4=null} |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.util.Map; import java.util.TreeMap; public class TestTreeMap { public static void main(String[]args) { Map<Integer, String> solarSystem = new TreeMap<>(); // Dodawanie elementów solarSystem.put(1, "Merkury"); solarSystem.put(2, "Wenus"); solarSystem.put(3, "Ziemia"); // Wyświetlenie kolekcji TreeMap System.out.println(solarSystem); // Nadpisanie klucza System.out.println("Próba dodania ponownie tego samego elementu - "); solarSystem.put(3, "Księżyc"); System.out.println(solarSystem); //Usunięcie elementu o podanym kluczu solarSystem.remove(2); System.out.println(solarSystem); //Dodanie elementu null solarSystem.put(4, null); System.out.println(solarSystem); solarSystem.put(null, null); } } |
Wynik wykonania powyższego kodu jest następujący
1 2 3 4 5 6 7 8 |
{1=Merkury, 2=Wenus, 3=Ziemia} Próba dodania ponownie tego samego elementu - {1=Merkury, 2=Wenus, 3=Księżyc} {1=Merkury, 3=Księżyc} {1=Merkury, 3=Księżyc, 4=null} Exception in thread "main" java.lang.NullPointerException at java.base/java.util.TreeMap.put(TreeMap.java:561) at Test.main(Test.java:30) |
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.