Kolekcje, mapy…
…z pewnością podczas swojej przygody z programowaniem korzystałeś już z klasycznych kolekcji – podkreślam klasycznych – takich jak listy, zbiory, wektory lub kolejki. Teoretycznie do kolekcji zaliczami jeszcze mapy – czyli kontenery, które pozwalają przechowywać dane w parach klucz -> wartość.
Choć na podstawie dokumentacji mapy nie są kolekcjami – nie implementują interfejsu Collection – to i tak nazywamy je kolekcjami ze względu, że potrafią przechowywać dane. I to w całkiem inny sposób niż klasyczne kolekcje.
Czym są mapy
Powiedzmy sobie jeszcze więcej czym są mapy.
Tak jak już powiedziałem – mapy są kolekcjami, które przechowują dane na podstawie par klucz -> wartość, a nie tak jak było to w przypadku np. zwykłych list, do których po prostu wrzucaliśmy obiekty: np.
List<String> students = new LinkedList<String>();
students.add("Pablo");
I wszystko jest w porządku aż do momentu, gdy nie chcemy przeszukiwać kolekcji na podstawie pewnego pola, parametru.
W przypadku studentów może to być np. numer indeksu – i gdy chcemy znaleźć studenta o konkretnym numerze indeksu jesteśmy zmuszeni (oczywiście pomijając sytuację, gdy możemy wyciągnąć studenta przy użyciu zapytania SELECT w bazie danych) napisać prostą metodę lub skorzystać ze strumienii z Java 8 w celu przeszukania kolekcji.
I tutaj przychodzą nam z pomocą mapy, gdzie możemy przypisać wartości (studentów) do konkretnych kluczy (wartości), dzięki czemu przeszukiwanie kolekcji jest dużo szybsze i prostsze.
Jak działa mapa?
Mapa przechowuje wartości na podstawie podanego klucza, który jest hashowany przy użyciu funkcji hashującej (skrótu). Funkcja skrótu może mieć bardzo różne postacie, zazwyczaj w swojej implementacji używa operacji modulo oraz liczb pierwszych.
Po przehashowaniu (skróceniu) klucza na odpowiedni hash, wartość trafia do odpowiedniego wiaderka (bucket), który jest wybierany na podstawie utworzonego hashu.
Z powodu tego, że funkcja hashująca może zwrócić ten sam hash dla kilku kluczy mapa jest zaopatrzona również w dodatkowy mechanizm sprawdzania podczas wyszukiwania elementu. Działa on tak, że jeśli pod jednym hashem (w jednym wiaderku) znajduje się więcej obiektów niż jeden to znaczy, że trzeba dokonać sprawdzenia również klucza – jeśli napotka ten sam klucz w wiaderku to oznacza, że jest to ten sam obiekt.
Kluczami i wartościami mapy – tak jak innych kolekcji – mogą być tylko obiekty, dlatego klucz może być naszym własnym obiektem. Może to być jakiś wymyślny obiekt zawierający w sobie X pól albo zwykły Integer lub String. Wybór klucza zależy od sytuacji, czyli od tego po czym chcemy wyszukiwać wartości.
Co daje hashowanie?
Nie ma co się oszukiwać – hashowanie powoduje, że złożoność obliczeniowa wyszukiwania elementu jest równa O(1) – czyli najlepsza. 😉
Dzięki tworzeniu hashu, wiemy do którego wiaderka mamy zajrzeć – nie musimy przeszukiwać element po elemencie, a sprawdzanie elementów następuje dopiero wtedy, gdy w wiaderku jest więcej niż jeden obiekt.
Zastosowanie
Tak jak juz wspomniałem mapy pozwalają na szybszy dostęp do konkretnych obiektów na podstawie ustalonego klucza, możemy wyróżnić kilka sytuacji, gdzie mapa się sprawdzi:
- Wyszukiwanie studenta po jego numerze albumu,
- Wyszukiwanie kraju po jego skrócie,
- Wyszukiwanie książki po numerze ISBN,
- Wyszukiwanie usera po jego ID,
Warto stosować mapę, gdy nie mamy możliwości użycia zapytania SELECT – czasami zdarza się, że działamy na danych, które są tymczasowe i w ogóle nie są przechowywane w bazie danych. W takim wypadku bardzo dobrym sposobem jest wybranie mapy.
Interfejs Map
Map jest interfejsem map w Javie, zaś najpopularniejszymi implementacjami jest HashMap oraz TreeMap – my użyjemy HashMap. Znajdziemy w dokumentacji również więcej implementacji mapy np.:
- AbstractMap,
- EnumMap,
- ConcurrentSkipListMap,
- LinkedHashMap,
- ConcurrentHashMap,
- ConcurrentNavigableMap.
Każda implementacja została stworzona w innym celu – np. niektóre współpracują z wielowątkowością, a niektóre nie.
Przykład
Aby stworzyć mapę musimy zdefiniować typ klucza oraz typ wartości – tak jak w przypadku zwykłych kolekcji używamy typów generycznych.
Map<Integer, String> students = new HashMap<>();
Dodawanie elementów do mapy jest wykonywane poprzez metodę put, które jako argument przyjmuje klucz oraz wartość.
students.put(1, "Pablo Escabo"); students.put(2, "TUTU RURU"); students.put(3, "TYMTYM RYTMYM");
Do wyszukiwania elementu po kluczu w mapie służy metoda get, która przyjmuje klucz obiektu, który chcemy wyciągnąć:
System.out.println("Student o kluczu 1: " + students.get(1));
Ilość elementów w mapie można sprawdzić przy użyciu metody size.
System.out.println("Ilość elementów w mapie: " + students.size());
Iteracja po mapie wygląda całkowicie inaczej niż w przypadku zwykłych kolekcji, gdzie używamy w normalny sposób np. pętli foreach. Tutaj musimy znaleźć inny sposób ze względu, że mapa podzielona jest na wiaderka (bucket) to możemy wyciągnąć zbiór wszystkich entry – czyli par klucz -> wartość z tych wszystkich wiaderek. W tym celu użyjemy metody entrySet
for (Map.Entry<Integer, String> studentEntry : students.entrySet()) {
final Integer studentId = studentEntry.getKey();
final String student = studentEntry.getValue();
System.out.println("Key: " + studentId + ", Value: " + student);
}
Tak jak powiedziałem entry jest niczym innym jak parą dlatego z każdego entry możemy wyciągnąć klucz oraz wartość.
Usunąć obiekt z mapy możemy poprzez metodę remove, która jako argument przyjmuje klucz
students.remove(1);
Ważnym elementem mapy jest to – że klucze w mapie muszą być unikalne – oznacza to, że wywołując drugi raz metodę put na tym samym kluczu nadpiszemy poprzednią wartość.
students.put(2, "HELLO");
O ile wcześniej wyciągnęliśmy całe pary to możemy również wyciągnąć tylko zbiór wartości:
System.out.println("Students values: ");
Set<String> studentsValues = new HashSet<>(students.values());
for (String student : studentsValues) {
System.out.println(student);
}
Oraz zbiór kluczy:
System.out.println("Students keys: ");
Set<Integer> studentsKeys = students.keySet();
for (Integer studentKey : studentsKeys) {
System.out.println(studentKey);
}
Całą mapę można również wyczyścić metodę clear:
students.clear();
A sprawdzić czy jest pusta metodę isEmpty:
System.out.println("Czy mapa jest pusta? " + students.isEmpty());
Po uruchomieniu całego takiego kodu:
package pl.maniaq;
import java.util.*;
public class Main {
public static void main(String[] args) {
Map<Integer, String> students = new HashMap<>();
students.put(1, "Pablo Escabo");
students.put(2, "TUTU RURU");
students.put(3, "TYMTYM RYTMYM");
System.out.println("Student o kluczu 2: " + students.get(1));
System.out.println("Ilość elementów w mapie: " + students.size());
for (Map.Entry<Integer, String> studentEntry : students.entrySet()) {
final Integer studentId = studentEntry.getKey();
final String student = studentEntry.getValue();
System.out.println("Key: " + studentId + ", Value: " + student);
}
students.remove(1);
students.put(2, "HELLO");
System.out.println("Students values: ");
Set<String> studentsValues = new HashSet<>(students.values());
for (String student : studentsValues) {
System.out.println(student);
}
System.out.println("Students keys: ");
Set<Integer> studentsKeys = students.keySet();
for (Integer studentKey : studentsKeys) {
System.out.println(studentKey);
}
students.clear();
System.out.println("Czy mapa jest pusta? " + students.isEmpty());
}
}
Otrzymamy taki rezultat:
Student o kluczu 1: Pablo Escabo Ilość elementów w mapie: 3 Key: 1, Value: Pablo Escabo Key: 2, Value: TUTU RURU Key: 3, Value: TYMTYM RYTMYM Students values: HELLO TYMTYM RYTMYM Students keys: 2 3 Czy mapa jest pusta? true
Zauważ, że put(2, “HELLO”) nadpisało wartość TUTU RURU!
Metody
W przykładzie użyłem wszystkich popularnych metod z interfejsu map, przytoczę je jeszcze raz:
- get(klucz) – wyciągnij wartość po kluczu
- put(klucz, wartość) – wrzuć wartość pod konkretny klucz, jeśli istnieje to ją nadpisz
- isEmpty() – sprawdza czy mapa jest pusta
- size() – zwraca rozmiar mapy
- entrySet() – zwraca zbiór par klucz -> wartość
- entryValues() – zwraca zbiór wartości
- entryKeys() – zwraca zbiór kluczy
- clear() – czyści całą mapę
Własny obiekt jako klucz
O ile możemy używać własnych obiektów jako klucze to trzeba pamiętać o:
- Implementacji hashCode i equals
- Obiekt musi być immutable
Choć są to tylko dwie zasady to ich głębszym wytłumaczeniem zajmę się wkrótce w innym artykule.
Podsumowanie
Mapa jest specyficzną kolekcją, którą warto użyć, gdy nie możemy wyciągać danych bezpośrednio z bazy danych przy użyciu Selecta. Zdarza się, że musimy działać na danych, które w ogóle nie trafiają do bazy danych, a przeszukiwanie takich danych liniowo (czyli ze złożonością O(n)) jest marnowaniem czasu.
