Site icon Java blog

Java #32: hashmap (mapa)

developeronthego
java hashmap

Mapa w przeciwieństwie do listy, umożliwia połączenie ze sobą dwóch obiektów: klucza i wartości. Dobrym przykładem używania mapy będzie próba zaimplementowania jakiegoś słownika. Słownik z definicji posiada szukaną nazwę zagadnienia (klucz) oraz jego definicję (wartość).

Przykładowa mapa:

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

Podobnie jak w przypadku tablicy dynamicznej, zamiast przy deklaracji zmiennej używać jej implementacji, powinno się wykorzystać jej interfejs (w tym przypadku Map). Map tak jak List, jest typem generycznym, czyli takim kontenerem na inny obiekt. W tym przypadku w znane Ci już ostre nawiasy wpisujesz klasę, której typem będzie Twój klucz oraz klasę reprezentującą wartość. W moim przypadku kluczem jest Integer a wartością String.

Algorytm hash mapy

Najczęściej spotykaną implementacją mapy jest HashMap. Jest to implementacja, która korzysta z algorytmu opartego o tablice mieszającą* (hashtable). W skrócie mapuje się tu klucz, którym jest liczba całkowita (tzw. hash), do którego przypisana jest konkretna wartość (często mówi się, że przechowywana jest ona w 'koszyku’, ang. bucket). Metoda haszująca generuje numer, który jest indeksem w tablicy. W teorii dobrze zaimplementowana taka metoda powinna przypisać jeden numer, jednej wartości. Jednak jeśli popełnisz błąd, to do jednego indeksu będzie przypisywana lista wartości z kolizją.

Przykład prostego wypełnienia mapy:

    Map<Integer, String> books = new HashMap<>();
    books.put(1, "Pan Tadeusz");
    books.put(2, "Potop");
    books.put(3, "Zbrodnia i kara");
    books.put(4, "Solaris");

Wyświetlanie danych za pomocą pętli foreach

for (Entry<Integer, String> item : books.entrySet()) {
	System.out.println(item.getKey());
	System.out.println(item.getValue());
}

Każda pętla foreach zawiera ten sam schemat: for (typ_po_jakim_iterujesz nazwa_zmiennej_reprezentującą_pojedyńczy element strukturę_którą_iterujesz). W tym przypadku wygląda to trochę przerażająco. Niestety w przypadku map nie możesz po prostu iterować po zmiennej books, lecz używając zbioru, który tworzy Ci metoda entrySet(). Czym jest zbiór (ang. set), opiszę w kolejnej lekcji. Z koleji interfejs Entry reprezentuje widok mapy (ang. collection-view of the map) . W praktyce powyższy zapis powinno rozumieć się tak jak: for (Map<Integer, String> item: books). Następnie w pętli, wyświetlam osobno klucz (metoda getKey()) oraz jego wartość (getValue()).

Pozostałe operacje na mapie

Aktualizacja rekordu wygląda tak:

books.replace(2, "Lalka");

Jeśli chcesz coś usunąć, wystarczy napisać:

books.remove("Lalka");

Jeśli nie pamiętasz, czy wypełniono wcześniej mapę taką samą wartością, spróbuj użyć:

System.out.println(books.putIfAbsent(3, "W pustyni i w puszczy"));

Jeśli klucz i wartość nie będą nigdzie użyte, metoda zwróci null, a wartość zostanie dodana. Metoda ta od razu zwróci Ci wartość poprzedniego rekordu, który chciałeś zastąpić, jeśli klucz jest zajęty.

Jeśli zależy Ci na sprawdzeniu tylko wartości kryjącym się pod konkretnym kluczem, możesz użyć:

int key = 1;
if (books.containsKey(key)) {
	System.out.println(books.get(key));
}

Pobranie wartości wykonuje się poprzez get(). W podobny sposób możesz też odnieść się też do wartości.

Na koniec sprawdzenie rozmiaru mapy i jej czyszczenie:

if (!books.isEmpty()) {
	System.out.println(books.size());
	books.clear();
}

Korzystanie własnego klucza w mapie

Teraz rozważmy bardziej skomplikowaną możliwość. Jak już mówiłem, kluczem mapy nie musi być tylko klasa Integer. Może być to jakakolwiek inna klasa. W jaki sposób w taki razie, wyliczyć hash, skoro inne klasy nie reprezentują liczb całkowitych. Jest na to sposób. 

public class MyHashKey {
	private String key;
	
	public MyHashKey(String key) {
		this.key = key;
	}
	@Override
	public int hashCode() {
		return (key == null) ? 0 : key.hashCode();
	}
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (!(obj instanceof MyHashKey))
			return false;
		MyHashKey other = (MyHashKey) obj;
		if (key == null) {
			if (other.key != null)
				return false;
		} else if (!key.equals(other.key))
			return false;
		return true;
	}
}

Klasa MyHashKey w wersji podstawowej zawiera jedynie pole i konstruktor. Jednak jeśli na jej podstawie ma być generowany hash obowiązkowo należy zaimplementować metody hashcode() i equals(). Są one dostępne w klasie Object, po której dziedziczą niejawnie wszystkie klasy w Javie.* Problem polega na tym, że jest to wersja podstawowa, która nie obejmie wszystkich zmian w Twoim kluczu. Np. w moim przypadku klucz zależy od wpisanego w niego tekstu. I w taki sposób należy zaimplementować obie metody.

Implementacja metody hashcode

Metoda hashode() zawsze zawraca liczbę całkowitą. W tym przypadku jest ona zależna od pola key, które jest typu String. Klasa String ma już poprawnie zaimplementowany hashCode(), więc pobierzemy sobie go z niej. Jednocześnie wcześniej sprawdzasz, czy pole nie jest nullem. Warunek (key == null) ? 0 : key.hashCode() oznacz, że jeśli key jest nullem to warunek zwróci liczbę 0, w przeciwnym przypadku będzie to key.hashCode(). Operator, który to umożliwia („? „) nazywa się operatorem trójargumentowym (ang. ternary operator) i jest równoważny ze zwykłym warunkiem if-else.

Implementacja metody equals

Dużo bardziej skomplikowana jest metoda equals(). Musi ona określić, czy zawartość sprawdzanego obiektu jest taka sama (czyli to co jest w polach dwóch instancji tej samej klasy powinno być sobie równe). Pamiętaj o sprawdzeniu za każdym razem czy dane pole nie jest nullem. Zanim jednak będziesz je porównywać są trzy ważne warunki, które warto pisać w takiej metodzie.

  1. Sprawdzenie czy przypadkiem nie porównujesz dwóch tych samych obiektów (słowo this wskazuje na tą samą referencje).
  2. Sprawdzenie czy cały obiekt nie jest nullem.
  3. Zweryfikowanie czy obie instancje są tej samej klasy.

Przy porównywaniu pól finalnie będziesz korzystać z metody equals() wywołanej na polach które są obiektami, jeśli pola są typami prostymi wystarczy porównać je poprzez znak '==’. Na koniec, jeśli wszystkie warunki zostały spełnione to zwracasz true.

Musisz być świadomy, że obie metody są tak samo ważne. Hashcode jedynie definiuje pod jakim indeksem w tablicy ma się znajdować koszyk, ale nie daje Ci 100% pewności, że nie wystąpi kolizja (wtedy pod jednym indeksem znajduje się kilka węzłów zamiast jednego). Tak sytuacja sprawia, że HashMapa zamiast być bardzo wydajną strukturą, staje się bardzo powolna, jednak właśnie dzięki metodzie equals wciąż będzie działać poprawnie.

Poniżej masz wywołanie kodu w sekcji main().

Map<MyHashKey, Integer> mapWithComplexKey = new HashMap<>();
mapWithComplexKey.put(new MyHashKey("something"), 10);
mapWithComplexKey.put(new MyHashKey("nothing"), 20);
mapWithComplexKey.put(new MyHashKey("other"), 30);
		
System.out.println("Value for key something: " + mapWithComplexKey.get(new MyHashKey("something"))); 
System.out.println("Value for key nothing: " + mapWithComplexKey.get(new MyHashKey("nothing"))); 
System.out.println("Value for key other: " + mapWithComplexKey.get(new MyHashKey("other")));

*Zobacz lekcję o klasie Object.

Ciekawe linki o hashmapie:

Link do kodu z lekcji: https://github.com/developeronthego/java-middle/tree/master/src/main/java/middle/lesson15

Exit mobile version