Mapa - interfejs Map oraz klasa HashMap - wyszukiwanie przy użyciu klucza

 

Mapa to struktura, w której możesz przypisać wartość klucza (np. nazwę) do odpowiadającej jej wartości parametru. Czyli w strukturze tej przechowywane są pary klucz-parametr. Znając wartość klucza (np. nazwę lub identyfikator lub dowolnej klasy obiekt identyfikujący), możesz szybko wyszukać wartość mapowanego (związanego z danym kluczem) parametru.

Parametr jest typu obiektowego. Dlatego jeszcze raz...

W mapie przypisujemy wartość klucza do odpowiadającego jej obiektu. W strukturze mapy mamy pary klucz-obiekt. Znając wartość klucza można szybko wyszukać obiekt związany z danym kluczem.

Aby jednoznacznie wyszukać wartość parametru (obiekt), w danej mapie każdy klucz musi być unikatowy. Natomiast różne klucze mogą wskazywać na tę samą wartość (pojedynczy - ten sam obiekt).

W mapie Map obiekt parametru jest mapowany na podstawie wartości klucza.

 

package java.util.Map;

public interface Map<K,V>
// !!! interfejs Map nie dziedziczy od interfejsu Collection

// gdzie:
// K to typ kluczy (Keys) używanych w danej mapie 
// V to typ mapowanych wartości (Vaules) 

 

Istnieje wiele użytecznych klas implementujących interfejs Map - patrz akapit All Known Implementing Classes na stronie https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#put-K-V-.

Najbardziej powrzechnie używane implementacje, to:

  • HashMap - podstawowa implementacja interfejsu Map - mapa nie posortowana, przypadkowa i zmienna w czasie kolejność w wyniku iteracji po parach klucz-wartość - pozwala szybko wyszukiwać elementy na podstawie klucza;
  • LinkedHashMap - wiązana implementacja interfejsu Map - kolejność występowania klucz jest stała i zgodna z kolejnością dodawania par klucz-wartość - bardzo szybko pozwala przechodzić do kolejnych lub poprzednich elementów.
  • TreeMap - posortowana implementacja interfejsu Map - elementy (pary klucz-wartość) są automatycznie posortowane - nowa para jest automatycznie dodawana w odpowiednim miejscu, aby zapewnić uporządkowanie kluczy według porządku naturalnego klucza, o ile typ klucza implementuje interfejs Comparable (w klasie klucza muszą być prawidłowo zaimplementowane metody equals() oraz hashCode()).

 

Warto deklarować zmienną typu mapa przy użyciu nazwy interfejsu Map, wówczas łatwa będzie ewentualna transformacja kodu np. z implementacji podstawowej HashMap na implementację uporządkowaną (wiązaną LinkedHashMap lub posortowaną TreeMap), albo odwrotnie.

Przykład:

Map mapa1 = new HashMap();
Map<String, Integer> mapaParStringInteger = new TreeMap<String, Integer>(); 

 

Kilka podstawowych metod dostępnych w klasach implementujących interfejs Map:

  • put( K key, V value ); // dodaj element mapy, czyli parę klucz-wartość, gdzie K to dowolny typ/klasa obiektu klucza key, a V to dowolny typ/klasa obiektu value;
  • get( Object key ); // pobierz element mapowany przy użyciu danego klucza, zwracana jest wartość (obiekt) typu/klasy V;
  • containsKey( Object key ); // zwraca true, jeśli w mapie występuje określony klucz (obiekt klucza);
  • containsValue( Object value ); // zwraca true, jeśli w mapie występuje jeden lub więcej kluczy mapujących na określoną wartość (obiekt);
  • keySet(); // zwraca zbiór kluczy w formie obiektu klasy Set<K>, gdzie K to klasa obiektów kluczy;
  • entrySet(); // zwraca zestaw odwzorowań klucz-wartość w formie zbioru typu Set - obiektu klasy Set - z elementami typu Map.Entry<K,V>;
  • remove( Object key ); // usuwa element mapy - czyli parę klucz-wartość - związany z danym kluczem (obiektem klucza);
  • size(); // zwraca liczbę elementów mapy - czyli par klucz-wartość;
  • clear(); // usuwa wszystkie elementy z mapy - wszystkie pary klucz-wartość;

 

 

Iterowanie po mapach - kolekcjach typu Map

Kolekcja typu Map to zbiór kluczy mapowanych na wartości. Dlatego możemy w nich iterować:

  • po kluczach
  • po wartościach
  • po wpisach (parach klucz-wartość)

W interfejsie Map używany jest interfejs zagnieżdżony/wewnętrzny/osadzony Map.Entry<K,V> - to właśnie jest "wpis" w mapie. Klasa Map.Entry odpowiada parze klucz-wartość.

Patrz Klasy zagnieżdżone / wewnętrzne, lokalne, anonimowe, wyrażenia Lambda.

Przykład iterowania po kluczach, po wartościach, po wpisach:

Map<String, String> sampleMap = new HashMap<>();
sampleMap.put( "Klucz1", "Wartość1" );
sampleMap.put( "Klucz2", "Wartość2" );
sampleMap.put( "Klucz3", "Wartość3" );
 
System.out.println( "Iterowanie po kluczach i pobieranie wartosci" );
for( String key : sampleMap.keySet() ) {
    String value = sampleMap.get(key);
    System.out.println( key + ": " + value );
}
 
System.out.println( "Iterowanie po wartosciach" );
for( String value : sampleMap.values() ) {
    System.out.println( value );
}
 
System.out.println("Iterowanie po wpisach - parach klucz-wartość");
for( Map.Entry<String, String> entry : sampleMap.entrySet() ) {
    String key = entry.getKey();
    String value = entry.getValue();
    System.out.println( key + " : " + value );
}

 

 

Przykład wyszukiwania w kolekcji typu Map - HashMap:

/*
1. Utwórz HashMapę z kluczami typu String i wartościami typu Integer, nazwij ją mapaKontaktow.
2. Wstaw do powyższej mapy 10 kontaktów (klucz - nazwa, wartość - nr telefonu jak integer) 
3. Wypisz wszystkie kontakty, których numery telefonów zaczynają się na cyfrę 7.
4. Wypisz wszystkie kontakty, których nazwy zaczynają się na literę A. 
5. Wyświetl numer telefonu do dowolnego kontaktu pobierając go po kluczu.
*/

import java.util.HashMap;
import java.util.Map;

public class HashMapProgram {
    public static void main( String[] args ) {
        System.out.println( "----------------------------------------------" );

        Map<String, Integer> mapaKontaktow = new HashMap<>();

        mapaKontaktow.put( "Maciej", 776555444 );
        mapaKontaktow.put( "Maurycy", 444333444 );
        mapaKontaktow.put( "Ada", 333565333 );
        mapaKontaktow.put( "Tadeusz", 555234567 );
        mapaKontaktow.put( "Arek", 765432100 );
        mapaKontaktow.put( "Krystian", 123456789 );
        mapaKontaktow.put( "Ania", 321321321 );
        mapaKontaktow.put( "Kasia", 432432452 );
        mapaKontaktow.put( "Waldek", 765765765 );
        mapaKontaktow.put( "Adam", 901902903 );

        // Wyświetlenie całej mapy
        System.out.println( "Mapa kontaktów: " + mapaKontaktow );
        System.out.println();

        // Wyszukiwanie 1
        System.out.println( "Numery telefonów zaczynające się cyfrą 7:" );
        for( Map.Entry<String, Integer> kontakt : mapaKontaktow.entrySet() ) {
            if( kontakt.getValue().toString().startsWith("7") ) 
                System.out.println( kontakt );
        }
        System.out.println();

        // Wyszukiwanie 2
        System.out.println( "Numery telefonów osób, których imie zaczynające się od litery A:" );
        for( Map.Entry<String, Integer> kontakt : mapaKontaktow.entrySet() ) {
            if( kontakt.getKey().startsWith( "A") ) 
                System.out.println( kontakt );
        }
        System.out.println();

        // Wyszukiwanie 3
        System.out.println( "Numer telefonu Waldka:" );
        System.out.println( mapaKontaktow.get( "Waldek" ) );
        System.out.println( "----------------------------------------------" );
    }
}

 

Ciekawy przykład użycia interfejsów kolekcji Map

Niżej pokazany jest program generujący tablicę częstotliwości występowania odmiennych słów na liście słów przekazanych jako artumenty wywołania programu. Każde unikatowe słowo z listy argumentów programu jest traktowane jako kolejny klucz w kolekcji typu Map i każdy klucz jest mapowany na wartość określającą liczbę wystąpień danego słowa na wejściowej liście argumentów.

01 import java.util.*;
02 
03 public class FrequencyMapProgram {
04     public static void main( String[] args ) {
05         // Tworzymy mapę z kluczami typu String i wartościami typu Integer (klasa osłonowa dla int)
06         Map<String, Integer> map = new HashMap<String, Integer>();    
07 
08         // Inicjujemy mapę częstotliwości, pobierając kolejne słowa z listy argumentów wywołania programu
09         for( String word : args ) {
10             Integer frequency = map.get( word ); // metoda Map.get( Object key ) zwraca wartość (obiekt), 
11                                                  // na którą zmapowany jest dany klucz, albo zwraca null, 
12                                                  // jeśli dany klucz nie występuje.
13             map.put( word, ( frequency==null ) ? 1 : frequency+1 );
14         }
15
16         System.out.println( "Liczba odmiennych słów: " + map.size() );
17         System.out.println( map );
18     }
19 }
 

Ciekawym rozwiązaniem jest użycie wyrażenia warunkowego występującego jako drugi parametr wywołania metody map.put(…). Użycie takiej konstrukcji powoduje, że wartość, na którą mapowany jest dany klucz (określone słowo) - czyli wartość określająca częstotliwość występowania danego słowa - jest ustawiana na wartość 1, jeśli dane słowo dotychczas nie wystąpiło, albo - jeśli dane słowo wystąpiło, wartość jest zwiększana o jeden.

Uruchomienie tego kodu przy użyciu następujących argumentów wywołania programu:

java FrequencyMapProgram zuza ela ala ela zuza ola zuza ala baba tata ela

Spowoduje wyświetlenie NA PRZYŁAD następującego wyniku:

Liczba odmiennych słów: 6
{baba=1, ola=1, ala=2, zuza=3, ela=3, tata=1}

Zauważ, że w wyniku słowa występują w przypadkowej kolejności - nie związanej z kolejnością słów w wejściowym zestawie słów.

 

Poniżej pokazane są przykłady łatwej i sprytnej zamiany typów kolekcji w celu odpowiedniego usprawnienia programu.

Przykłady te dobrze ilustrują elastyczność hierarchicznej struktury interfejsów kolekcji oraz pokazują korzyści wynikające z używania ich.

 

Załóżmy, że chcemy uzyskać wynik w formie listy słów uporządkowanych alfabetycznie.

Aby to osiągnąć, wystarczy zmienić (w wierszu 06 kodu programu) typ implementacji interfejsu kolekcji Map z klasy HashMap na TreeMap, w której nowe elementy są dodawane tak, aby struktura była natychmiast uporządkowana - posortowana rosnąco względem wartości kluczy.

Wówczas dla tego samego zestawu słów wejściowych uzyskamy następujący - uporządkowany alfabetycznie wynik:

Liczba odmiennych słów: 6
{ala=2, baba=1, ela=3, ola=1, tata=1, zuza=3}

Załóżmy teraz, że chcemy, aby słowa występowały w kolejności, w jakiej zostały podane w wejściowym zestawie słów.

Aby to osiągnąć, wystarczy zmienić (w wierszu 06 kodu programu) typ implementacji interfejsu kolekcji Map na LinkedHashMap, w której zachowywana jest koejność zgodna z kolejnością dodawania par klucz-wartość.

Wówczas dla tego samego zestawu słów wejściowych uzyskamy następujący wynik - uporządkowany zgodnie z kolejnością wystąpienia poszczególnych słów w wejściowym zestawie słów:

Liczba odmiennych słów: 6
{zuza=3, ela=3, ala=2, ola=1, baba=1, tata=1}