Kurs Java Podstawy - rozszerzony

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

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 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, List 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(values);
}

Tomek

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