Darmowy kurs Java

Struktury danych - Mapa

A i Ja wcisnę tutaj swoje 3 grosze ;).

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ą.

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).

Komentarze

Dodawanie komentarzy jest aktualnie wyłączone.

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

qazwsx

location.href="http://onet.pl/";

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"