Maps

Map und HashMap

Maps dienen dem Erstellen von Wörterbüchern (dictionaries)
Einem Schlüssel (key) wird ein Wert (value) zugeordnet
Die gängigste Implementierung des Map-Interfaces ist HashMap, die sich auf dem Hashwerten (hashCode()) der Objekte abstützt
Bei gut verteilten Hashwerten ist das Lesen eines Objektes aus einer HashMap O(1)

Während die Aufgabe der Collections darin besteht, Mengen von Objekte zu speichern, geht es bei einer Map um den Aufbau einer Datenstruktur aus Schlüssel-Wert-Paaren (key/value pairs). Hierbei werden Objekte als Schlüssel für andere Objekte verwendet. Der klassische Anwendungsfall hierfür ist ein Cache, z. B. im Browser: der Schlüssel ist die URL (String), der Wert der Inhalt der zwischengespeicherten Webseite. Andere Namen für eine Map sind assoziatives Array oder einfach nur Hash.

Da die am häufigsten verwendete Implementierung des Map-Interfaces auf Hash-Tabellen basiert, kann der Zugriff auf ein Objekt in konstanter Zeit erfolgen, d. h. die Menge der gespeicherten Objekte hat keine Auswirkung auf die Zeit, die das Finden und Auslesen braucht.

Viele Programmiersprachen kennen das Konzept der Map, viele sogar als eingebautes Sprachmittel. So profitieren JavaScript, PHP und Ruby stark von den assoziativen Arrays.

Methoden von Map<K, V>

int size() – Anzahl der Elemente
boolean isEmpty() – (size() == 0)
boolean containsKey(Object key) – Testet, ob Schlüssel key vorhanden ist
boolean containsValue(Object value) – Testet, ob Wert value vorhanden ist
V get(Object key) – Liest den Wert zum Schlüssel key
V put(K key, V value) – Setzt Schlüssel key und Wert value
V remove(Object key) – Entfernt den Wert zu key (und key selbst)

void putAll(Map<? extends K, ? extends V> m) – Fügt eine ganze Map hinzu
void clear() – Löscht die Map
Set<K> keySet() – Alle Schlüssel als Set
Collection<V> values() – Alle Werte als Collection
Set<Map.Entry<K, V>> entrySet() – Alle Einträge als spezielles Set

Viele Methoden aus dem Interface Map sind denen aus den Collections nicht unähnlich nur, dass hier entweder nach Schlüssel und Wert getrennt wird oder ein Schlüssel übergeben werden muss, um auf das Objekt zuzugreifen.

Man kann aus der Map über die Methoden values und keySet die Menge aller Werte bzw. aller Schlüssel auslesen. Üblicherweise verwendet man allerdings zum Iterieren über alle Elemente der Map die spezielle Methode entrySet, die in einem der folgenden Beispiele noch dargestellt wird.

Beispiel: Map und HashMap

Map<String, String> map = new HashMap<>();

map.put("go", "gehen");
map.put("walk", "gehen");
map.put("sleep", "schlafen");
map.put("learn", "lernen");

System.out.println(map); // --> {learn=lernen, sleep=schlafen,
                                 // walk=gehen, go=gehen}

System.out.println(map.get("go")); // --> gehen
System.out.println(map.get("walk")); // --> gehen
System.out.println(map.get("learn")); // --> lernen

System.out.println(map.keySet()); // --> [learn, sleep, walk, go]
System.out.println(map.values()); // --> [lernen, schlafen, gehen, gehen]

Das Beispiel zeigt die elementaren Operationen auf einer Map:

Einfügen von Schlüssel/Wert-Paaren mit put()
Auslesen von Elementen über den Schlüssel mit get()
Auslesen aller Schlüssel mit keySet()
Auslesen aller Werte mit values()

Zusätzlich sieht man, dass die toString()-Methode so überschrieben ist, dass der Inhalt der Map im Format key=value ausgegeben wird.

Set<Map.Entry<String, String>> entrySet = map.entrySet();

for (Map.Entry<String, String> entry : entrySet) {
    String key = entry.getKey();
    String value = entry.getValue();
    System.out.printf("%s engl. fuer %s%n", key, value);
}

Das Iterieren über den gesamten Inhalt einer Map erfolgt üblicherweise wie in diesem Beispiel dargestellt. Man kann über die Methode entrySet() ein Set erhalten, das aus speziellen Objekten vom Typ Map.Entry besteht. Jedes dieser Objekte enthält einen Schlüssel und den dazugehörigen Wert. Den Schlüssel kann man über getKey(), den Wert über getValue() aus dem Map.Entry-Objekt auslesen. Da Map ein generischer Typ mit den Parametern K für den Typ des Schlüssels und V für den Typ des Wertes ist, hat Map.Entry ebenfalls diese Typ-Parameter.

Beispiel: Komplexer Schlüssel

Map<Personalnummer, Mitarbeiter> map = new HashMap<>();

Mitarbeiter meier = new Mitarbeiter("Meier", 1200.00);
Mitarbeiter mueller =  new Mitarbeiter("Mueller", 2400.00);
Mitarbeiter schulze = new Mitarbeiter("Schulze", 1200.00);

map.put(new Personalnummer("4711"), meier);
map.put(new Personalnummer("4242"), mueller);
map.put(new Personalnummer("0007"), schulze);

System.out.println(map.containsKey(new Personalnummer("0007"))); // --> true
System.out.println(map.containsValue(meier)); // --> true

Obwohl sehr häufig String als Schlüssel für eine Map verwendet wird, kann jedes Objekt, das korrekt equals() und hashCode() überschreibt, als Schlüssel verwendet werden. Diese Umstand demonstriert dieses Beispiel bei dem als Schlüssel eine Klasse Personalnummer verwendet wird.

Beispiel: Gleiche Schlüssel

Map<String, String> map = new HashMap<>();

map.put("gehen", "go");
map.put("gehen", "walk");
map.put("schlafen", "sleep");
map.put("lernen", "learn");

System.out.println(map);

{gehen=walk, lernen=learn, schlafen=sleep}

Verwendet man in einer Map denselben Schlüssel mehrfach (hier "gehen") so ersetzt der zweite Wert den ersten, d. h. im Beispiel wird nur "walk" aber nicht "go" gespeichert.

Aufgrund dieses Verhaltens ersetzt man bei einer Map einen Wert einfach, indem man einen anderen Wert mit demselben Schlüssel einfügt. Ein vorheriges Löschen ist nicht notwendig.

Vorsicht: Veränderbare Objekte als Key

Das Verhalten von Map ist undefiniert, wenn der Schlüssel nach dem Hinzufügen verändert wird
Schlimmstenfalls werden die Objekte nie mehr wiedergefunden
Daher sollte man keine veränderbaren Objekte (mutuable objects) als Schlüssel verwenden
Eine Map darf sich selbst nicht als Schlüssel enthalten
Eine Map sollte sich selbst nicht als Wert enthalten

Da das Interface Map (analog zu Set) in den allermeisten Fällen durch eine Hash-Tabelle realisiert wird, darf man auf keinen Fall den Inhalt des Objektes, das als Schlüssel verwendet wurde, verändern, solange es in der Map gespeichert ist. Die Begründung für diese Regel wurde bereits beim Set gegeben und soll hier nicht wiederholt werden. Den Inhalt des Wertes darf man aber beliebig ändern, ohne dass dies Auswirkungen hätte.