Struktury danych - Mapa

Opowiem tutaj o mapie, czyli specjalnej kolekcji, która pozwala do danego parametru przypisać wartość klucza. Dzięki temu, znając wartość klucza, jesteśmy wstanie wyciągnąć z mapy interesujące nasz dane.

Mapy są bardzo często stosowane w komunikacji webowej między klientem a aplikacją webową.

Kurs Java

**Mapa -**obiekt mapujący wartości parametrów na podstawie klucza. W danej mapie może istnieć tylko jeden unikatowy klucz. Szeroko stosowany w komunikacji między aplikacjami, dzięki możliwości przypisanie wartości do stałych, ustalonych parametrów.

Mapę można sobie wyobrazić jako kolekcje przechowującą pary klucz-parameter. Na podstawie klucza wyciągamy wartość powiązaną z kluczem.

Przykład:

Map<String, Integer> Oceny = new HashMap<String, Integer>();
 Oceny.put("Matematyka", 5);
 Oceny.put("Polski", 2);

Właśnie zparametryzowaliśmy sobie oceny. Możemy teraz odwołać się do wartości z mapy za pomocą klucza, który stanowi w naszym przypadku String określający nazwę przedmiotu.

Mapę można zaimplementować implementując interfejs "Map" stosując 2 dowolne kolekcje. Mogą to być tablice, listy czy nawet inne mapy. Osobiście zalecam stosowanie tych już zaimplementowanych w bibliotekach Javy, jak np. HashMap.

Oto przykład mojej implementacji generycznej mapy opartej o 2 listy:

package pl.javastart.utils;
 
 import java.util.AbstractMap;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeSet;
 
 /**
  * @author Mikołajczuk Rafał
  * @date 2013-01-07
  */
 
 /**
  * Mapa przyjmująca 2 typy generyczne. K określa typ klucza,
  * natomiast V określa typ wartości przyjmowanej.
  * Przykładem może być MyMap<String, Integer> oceny.
  * 
  * Dwie listy przechowujące klucze oraz wartości będziemy 
  * traktować jaką całą mapę.
  */
 public class MyMap<K, V> implements Map<K, V> {
 
 	//Klucze mapy powiązane z wartościami
 	private ArrayList<K> keys;
 	
 	//Wartości mapy powiązane z kluczami
 	private ArrayList<V> values;
 	
 	//Czyść mapę
 	public void clear() {
 		keys.clear();
 		values.clear();
 	}
 
 	//Sprawdź, czy klucz 'key' istnieje w mapie
 	public boolean containsKey(Object key) {
 		return keys.contains(key);
 	}
 
 	//Sprawdź, czy wartość 'value" istnieje w mapie
 	public boolean containsValue(Object value) {
 		return values.contains(values);
 	}
 
 	/**
 	 * Trochę cięższej magii
 	 * 
 	 * Przerób mapę na 'Set' - Set jest kolekcją przechowującą indiwidualne, nie
 	 * powtarzające się elementy.
 	 */
 	@SuppressWarnings({ "rawtypes", "unchecked" })
 	@Override
 	public Set<java.util.Map.Entry<K, V>> entrySet() {
 		//sprawdź, czy ilość kluczy zgadza się z ilością wartości
 		if (keys.size() != values.size())
 			//jeśli nie, wyrzuć wyjątek
 			throw new IllegalStateException("InternalError: nie można zsynchronizować " +
 					"kluczy z wartośćiami");
 		/**
 		 * w przeciwnym wypadku..
 		 * 
 		 * Stwórz nowy Set, w moim wypadku obiekt klasy TreeSet
 		 * 
 		 * Widzimy tutaj, że nasz TreeSet przechowuje obiekty typu
 		 * Map.Entry<K, V>.
 		 * Map.Entry - jest to obiekt przechowujący parę klucz-wartość, czyli to co
 		 * przechowują mapy. <K, V> oznacza, że dana para jest typem K klucz + V wartość
 		 */
 		Set set = new TreeSet<Map.Entry<K, V>>();	
 		/**
 		 * Wrzuć wszystkie elementy mapy do TreeSetu.
 		 * Dzięki temu zabiegowi, elementy mapy nie będę się powtarzać
 		 * i otrzymamy kolecje indiwidualnych par klucz-wartość.
 		 */
 		for (int i=0; i<size(); i++) {
 			/**
 			 * Nie zrażać się słowem Abstract. AbstractMap jest zwykłą klasą,
 			 * która potrafi trochę więcej. SimpleEntry obiektem reprezentujący parę, 
 			 * którą można dodać do Setu.  
 			 */
 			set.add((new AbstractMap.SimpleEntry<K, V>(keys.get(i), values.get(i))));
 		}
 		//zwróć set
 		return set;
 	}
 
 	//Pobierz wartość z mapy na podstawie klucza 'key'
 	public V get(Object key) {
 		int i = keys.indexOf(key);
 		if (i == -1)
 			return null;
 		return values.get(i);
 	}
 
 	//sprawdź, czy mapa jest pusta
 	public boolean isEmpty() {
 		return keys.isEmpty();
 	}
 
 	//Zwróc kolekcje indiwidualnych kluczy mapy
 	public Set<K> keySet() {
 		return new TreeSet<K>(keys);
 	}
 
 	//Dodaj parę key-value do mapy
 	@SuppressWarnings("unchecked")
 	@Override
 	public V put(K key, V value) {
 		/**
 		 * Pętla, w której sprawdzamy, czy dany klucz
 		 * już nie wystąpił
 		 */
 		for (int i=0; i<keys.size(); i++) {
 			//przechowaj starą wartość klucza, jeśli istnieje
 			V oldValue = values.get(i);
 			
 			//jeśli klucz istnieje w mapie to
 			if(((Comparable<K>) key).compareTo(keys.get(i)) == 0) {
 				//przypisz kluczowi nową wartość zachowując kolejność
 				values.set(i, value);
 				//i zwróć starą
 				return oldValue;
 			}
 		}
 		//w przeciwnym wypadku dodaj na koniec mapy parę
 		keys.add(key);
 		values.add(value);
 		return null;
 	}
 	/**
 	 * Dodaj mapę 'm' do aktualnej mapy.
 	 * 
 	 * Ciekawostka, tutaj stosuje wzorzec Iterator. Iterator
 	 * jest bytem, który przechodzi przez elementy kolekcji.
 	 * Standardowy Itereator przechodzi po wszystkich elementach
 	 * kolekcji. Ale to tak na marginesie.
 	 */
 	public void putAll(Map<? extends K, ? extends V> m) {
 		
 		/**
 		 * Stwórz na podstawie kluczy mapy 'm' iterator.
 		 */
 		
 		Iterator<? extends K> keyIterator = m.keySet().iterator();
 		//wykonuj, dopóki iterator ma następną wartość
 		while(keyIterator.hasNext()) {
 			K key = keyIterator.next();
 			V value = m.get(key);
 			put(key, value);
 		}
 	}
 	/**
 	 * Usuń wartość klucza 'key' i zwróć
 	 * ją, jeśli istnieje. W przeciwnym wypadku
 	 * zwróć null'a.
 	 */
 	public V remove(Object key) {
 		int i = keys.indexOf(key);
 		if ( i == -1 )
 			return null;
 		V value = values.get(i);
 		keys.remove(i);
 		values.remove(i);
 		return value;
 	}
 
 	//Zwróć wielkość mapy
 	public int size() {
 		return keys.size();
 	}
 
 	//Zwróc kolekcje wartości
 	public Collection<V> values() {
 		return values;
 	}
 
 }
 
 }

Mapy stosowane są przy przekazywaniu parametrów za pomocą metod HTTP GET oraz POST, oraz bardzo popularnym formacie JSON (JavaScript Object Notation).


Dyskusja i komentarze

Masz pytania do tego wpisu? Może chcesz się podzielić spostrzeżeniami? Zapraszamy dyskusji na naszej grupie na Facebooku.

Poniżej znajdziesz archiwalne wpisy z czasów, gdy strona była jeszcze hobbystycznym blogiem.

jacobs

putAll(Map m) Czy mógłbym prosić o wyjaśnienie argumentów tej funkcji? Domyślam się, że przekazywana jest mapa i typy Ki V muszę być zgodne z typami przechowywanymi przez obiekt mapy. Ale o co chodzi z "? extends" ??

Rafał Mikołajczuk

? extends K oznacza, że "?" może być jakąkolwiek klasą, która dziedziczy po K. Ale żeby Ci uzmysłowić to, to opisze to na przykładzie. Mamy klasy kluczProsty i kluczZłożony które dziedziczą po klasie Klucz. Oraz mamy listę List<Klucz> która przechowuje różne rodzaje kluczy. I teraz, jeśli mamy metodę dodajListę(List<? extends Klucz> klucze) to jako parametr może przyjąć obiek klasy List<kluczProsty>, List<kluczZłożony> lub jakąkolwiek listę przechowującą klucze dziedziczące po klasie Klucz. Tutaj już w chodzi typy generyczne i zostanie to opisane w osobnym kursie.

jacobs

Dzięki, myślę że rozumiem o co chodzi. Swoją drogą kolekcje to dosyć ciekawy temat w javie i fajnie byłoby przeczytać jeszcze kilka fajnych artów na ten temat na Waszej stronie. Pozdrawiam

Rafał Mikołajczuk

wszystko w swoim czasie ;) ale na pewno opiszemy tutaj więcej kolekcji, a później nawet wzorce projektowe ;)

jacobs

czekam z niecierpliwością :D

bab

public boolean containsValue(Object value) { return values.contains(value<b>s</b>); }

Tomek

Metoda entrySet() nie działa - Eclipse wyrzuca błąd: "java.lang.ClassCastException: java.util.AbstractMap$SimpleEntry cannot be cast to java.lang.Comparable"