HashMap und HashSet

Kurz gesagt: Eine Map (Dictionary) speichert Paare aus Schlüssel und Wert mit eindeutigen Schlüsseln und findet einen Wert schnell über seinen Schlüssel, und ein Set speichert eindeutige Werte.

Problem

Wer ist dieser Benutzer?

Die Benutzer der Website stehen in einer Liste. Bei jeder Anmeldung suchst du die E-Mail zum Benutzernamen:

static String findEmail(List<User> users, String username) {
    for (User u : users) {
        if (u.username.equals(username)) {
            return u.email;
        }
    }
    return null;
}

Bei drei Benutzern geht das sofort. Bei 2 000 000 vergleicht jede Anmeldung bis zu 2 000 000 Namen, und es gibt Tausende Anmeldungen pro Minute. Ein Telefonbuch liest du auch nicht ab der ersten Seite. Du schlägst direkt beim Buchstaben auf.

Die Idee

Map: Schlüssel → Wert

Du willst fragen „Welche E-Mail hat weber?“ und sofort die Antwort bekommen. Die Collection dafür heißt Map (auch Wörterbuch oder Dictionary). Sie speichert Paare: einen Schlüssel und einen Wert. In Java ist die übliche Map HashMap:

Map<String, String> emails = new HashMap<>();
emails.put("mueller", "mueller@example.com");
emails.put("mschmidt", "mschmidt@example.com");
emails.put("weber", "weber@example.com");

System.out.println(emails.get("weber"));
System.out.println(emails.get("niemand"));
System.out.println("Benutzer: " + emails.size());

Ausgabe

weber@example.com
null
Benutzer: 3

• Es gibt zwei Typparameter: einen für den Schlüssel und einen für den Wert. Map<String, String> ist „von Text zu Text“.
• put(key, value) legt ein Paar hinein, und get(key) gibt den Wert zurück.
• Ein Schlüssel, den es nicht gibt, ergibt null.
• Map und HashMap sind in java.util. Wieder steht links das Interface und nach new die Klasse.

get durchläuft nicht alle Paare. Es findet den Platz des Schlüssels fast sofort, egal wie viele es sind. Wie das geht, zeigt die nächste Lektion.

Die Idee

Das Lager: ändern und prüfen

Der Bestand im Lager: Artikel → Anzahl.

Map<String, Integer> stock = new HashMap<>();
stock.put("Laptop", 4);
stock.put("Maus", 25);
stock.put("Laptop", 3);

System.out.println(stock.get("Laptop"));
System.out.println(stock.containsKey("Monitor"));
System.out.println(stock.getOrDefault("Monitor", 0));
stock.remove("Maus");
System.out.println(stock.size());

Ausgabe

3
false
0
1

• Schlüssel sind eindeutig. Das zweite put("Laptop", 3) fügt keine neue Zeile hinzu. Es ersetzt 4 durch 3.
• containsKey fragt, ob der Schlüssel in der Map ist.
• getOrDefault(key, 0) gibt den Wert zurück, oder 0, wenn es den Schlüssel nicht gibt. Das schützt dich vor null.
• remove(key) entfernt das Paar.

Genauer, für Neugierige

• Werte dürfen sich wiederholen: Laptop und Maus können beide 3 sein. Schlüssel nicht.
• Es gibt auch containsValue. Es durchläuft aber alle Werte, denn eine Map ist nur nach Schlüssel schnell.

Probier es aus

Wie viele stehen auf der Karte?

Was gibt das Programm aus?

Map<String, Integer> menu = new HashMap<>();
menu.put("Kaffee", 2);
menu.put("Tee", 2);
menu.put("Kaffee", 3);
System.out.println(menu.size() + " " + menu.get("Kaffee"));

Antwort

2 2

2 3

3 2

3 3

Prüfen

Die Idee

Durchlaufen und Reihenfolge

Die Lieferkosten nach Stadt. Eine Map durchläufst du paarweise mit entrySet():

Map<String, Double> delivery = new HashMap<>();
delivery.put("Berlin", 4.5);
delivery.put("Hamburg", 5.2);
delivery.put("Bremen", 6.0);
delivery.put("Dresden", 6.0);
delivery.put("Leipzig", 5.8);

for (Map.Entry<String, Double> e : delivery.entrySet()) {
    System.out.println(e.getKey() + ": " + e.getValue() + " €");
}

Ausgabe

Bremen: 6.0 €
Dresden: 6.0 €
Berlin: 4.5 €
Leipzig: 5.8 €
Hamburg: 5.2 €

Bremen kam als Erstes heraus, aber Berlin wurde als Erstes hinzugefügt. HashMap verspricht überhaupt keine Reihenfolge. Die Reihenfolge hängt von den Hashcodes der Schlüssel ab, um die es in der nächsten Lektion geht. Schreib keinen Code, der sich darauf verlässt.

Wenn die Reihenfolge wichtig ist, ändere nur die Klasse nach new:

• LinkedHashMap behält die Reihenfolge des Hinzufügens. Mit denselben put-Aufrufen und System.out.println(delivery):

Ausgabe

{Berlin=4.5, Hamburg=5.2, Bremen=6.0, Dresden=6.0, Leipzig=5.8}

• TreeMap sortiert die Schlüssel:

Map<String, Double> delivery = new TreeMap<>();
delivery.put("Berlin", 4.5);
delivery.put("Hamburg", 5.2);
delivery.put("Bremen", 6.0);
delivery.put("Dresden", 6.0);
delivery.put("Leipzig", 5.8);

System.out.println(delivery);

Ausgabe

{Berlin=4.5, Bremen=6.0, Dresden=6.0, Hamburg=5.2, Leipzig=5.8}

Map.Entry<String, Double> ist ein Paar: getKey() und getValue(). Im Namen steht ein Punkt, weil der Typ innerhalb von Map deklariert ist. Solche Typen siehst du in der Lektion „Klassen in Klassen“.

Genauer, für Neugierige

• Wenn du nur die Schlüssel brauchst, durchlaufe keySet(). Wenn du nur die Werte brauchst, durchlaufe values():

for (String city : delivery.keySet()) {
    System.out.print(city + " ");
}
System.out.println();

double sum = 0;
for (double price : delivery.values()) {
    sum += price;
}
System.out.println("Durchschnitt: " + sum / delivery.size() + " €");

Ausgabe

Bremen Dresden Berlin Leipzig Hamburg
Durchschnitt: 5.5 €

• TreeMap ist langsamer als HashMap, weil es die Schlüssel sortiert hält. Nimm es, wenn du die Reihenfolge brauchst.
• Mit denselben Schlüsseln gibt eine HashMap in einer Java-Version meist in derselben Reihenfolge aus. Das ist kein Versprechen: Die Reihenfolge kann sich mit einer anderen Version, mit mehr Elementen oder mit einer anderen Zahl von Buckets ändern.

Die Idee

Zählen

Wie oft wurde jeder Artikel bestellt? Der Schlüssel ist der Artikel, der Wert ist die Anzahl. Bei jeder Bestellung nimmst du die alte Anzahl (oder 0) und addierst 1:

String orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);

Ausgabe

{Cola=1, Kaffee=3, Tee=2}

Das ist die häufigste Verwendung einer Map: Wörter zählen, Stimmen, Fehler nach Art, Verkäufe nach Stadt. Hier ist es eine TreeMap, damit die Artikel sortiert herauskommen.

String orders = "Kaffee Tee Kaffee Cola Kaffee Tee";
Map<String, Integer> counts = new TreeMap<>();
for (String item : orders.split(" ")) {
    counts.put(item, counts.getOrDefault(item, 0) + 1);
}
System.out.println(counts);

Schritt für Schritt, in Worten

1. 6 Bestellungen und eine leere TreeMap.
2. „Kaffee“ ist noch nicht da: getOrDefault gibt 0, und put fügt den Schlüssel mit 1 hinzu.
3. „Tee“ ist noch nicht da: getOrDefault gibt 0, und put fügt den Schlüssel mit 1 hinzu.
4. „Kaffee“ ist schon da: getOrDefault gibt 1, und put ersetzt den Wert durch 2.
5. „Cola“ ist noch nicht da: getOrDefault gibt 0, und put fügt den Schlüssel mit 1 hinzu. TreeMap stellt ihn vor „Kaffee“: Die Schlüssel sind sortiert.
6. „Kaffee“ ist schon da: getOrDefault gibt 2, und put ersetzt den Wert durch 3.
7. „Tee“ ist schon da: getOrDefault gibt 1, und put ersetzt den Wert durch 2.
8. Jeder Artikel ist nur einmal ein Schlüssel, und der Wert sagt, wie oft er bestellt wurde.

Genauer, für Neugierige

• split(" ") aus der Lektion über Strings teilt die Zeile in Wörter.
• Im Modul „Modernes Java“ siehst du eine kürzere Schreibweise dafür, mit der Methode merge.

Probier es aus

Finde den Fehler

Das Programm soll die Bestellungen zählen. Stattdessen bricht es schon bei der ersten ab:

Fehler

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

In welcher Zeile ist der Fehler?

Wähle die Zeile mit dem Fehler.

1String[] orders = { "Kaffee", "Tee", "Kaffee" };2Map<String, Integer> counts = new TreeMap<>();3for (String item : orders) {4 counts.put(item, counts.get(item) + 1);5}6System.out.println(counts);

Prüfen

Die Idee

HashSet: jedes nur einmal

Wie viele verschiedene Leute haben sich heute auf der Website angemeldet? Wer sich fünfmal anmeldet, soll nur einmal zählen. Eine Collection, die jeden Wert nur einmal speichert, heißt Set (Menge):

String[] visits = { "anna@example.com", "jonas@example.com", "anna@example.com", "maria@example.com", "jonas@example.com" };
Set<String> visitors = new HashSet<>();
for (String email : visits) {
    visitors.add(email);
}
System.out.println("Besuche: " + visits.length);
System.out.println("Verschiedene Besucher: " + visitors.size());
System.out.println(visitors.contains("maria@example.com"));

Ausgabe

Besuche: 5
Verschiedene Besucher: 3
true

• add auf einen Wert, der schon darin ist, macht nichts und gibt false zurück. Ist er neu, gibt es true zurück.
• contains ist so schnell wie containsKey bei einer Map. Innen ist ein HashSet eine HashMap, in der du nur die Schlüssel speicherst.
• Es gibt keine Indizes. Ein Set beantwortet nur die Frage „Ist es hier drin?“.

Genauer, für Neugierige

• Auch hier ist die Reihenfolge nicht versprochen. LinkedHashSet behält die Reihenfolge des Hinzufügens, und TreeSet sortiert:

Set<String> tags = new TreeSet<>();
tags.add("java");
tags.add("sql");
tags.add("git");
tags.add("java");
System.out.println(tags);

Ausgabe

[git, java, sql]

• retainAll behält nur die Elemente, die zwei Sets gemeinsam haben, und addAll vereinigt sie. Du brauchst sie in der Übung.

Probier es aus

Eine doppelte Rechnung

Die Buchhalterin will die Rechnungsnummern sehen, die zweimal eingegeben wurden. Welche Methode prüft und fügt gleichzeitig hinzu?

String[] invoices = { "F-101", "F-102", "F-101", "F-103" };
Set<String> seen = new HashSet<>();
for (String number : invoices) {
    if (!seen.(number)) {
        System.out.println("Doppelte Rechnung: " + number);
    }
}

Prüfen

Übung

Maps im Einsatz

Löse die Aufgaben in deinem Editor.

1. Eine Benutzertabelle. Eine Klasse UserTable mit den Methoden add(String username, String email), get(String username) und size(). Innen ist sie eine HashMap. Füge mueller, mschmidt und weber mit E-Mails der Form mueller@example.com hinzu und suche mschmidt und niemand. In der nächsten Lektion baust du auch deine eigene Hashtabelle, ohne HashMap.

Ausgabe

mschmidt: mschmidt@example.com
niemand: unbekannter Benutzer
Benutzer: 3

2. Worthäufigkeit. Lies eine Zeile Text ein, schreib sie klein und zähle jedes Wort. Gib die Wörter in alphabetischer Reihenfolge aus.

Eingabe

Kaffee mit Milch und Kaffee ohne Zucker und Kaffee

Ausgabe

kaffee: 3
milch: 1
mit: 1
ohne: 1
und: 2
zucker: 1

3. Dokumente nach Stichwort. Eine Klasse DocumentIndex mit den Methoden addDocument(int id, String... keywords) und search(String keyword), die eine Liste mit den Nummern der Dokumente mit diesem Wort zurückgibt. Innen ist sie eine Map<String, List<Integer>>: für jedes Wort eine Liste von Dokumenten. Füge Dokument 1 mit „OOP“ und „Java“ hinzu, Dokument 2 mit „SQL“ und „Datenbanken“ und Dokument 3 mit „Java“ und „Collections“. Suche nach „Java“, „SQL“ und „Python“.

Ausgabe

Java: [1, 3]
SQL: [2]
Python: []

4. Ein Kontaktnetz. Eine Klasse Contact mit Name und E-Mail und eine Klasse ContactNetwork mit den Methoden addContact(String name, String email), addConnection(String a, String b) (die Verbindung gilt in beide Richtungen), friendsOf(String name), common(String a, String b) (gemeinsame Freunde) und emailOf(String name). Speichere die Kontakte in einer Map<String, Contact> und die Verbindungen in einer Map<String, Set<String>>. Nimm ein TreeSet, damit die Namen sortiert herauskommen. Verbinde Jonas mit Maria und Jonas mit Peter.

Ausgabe

Jonas: [Maria, Peter]
Maria: [Jonas]
Gemeinsame Freunde von Maria und Peter: [Jonas]
E-Mail von Peter: peter@example.com

Weitere Aufgaben

• Eine eindeutige ID. Eine Methode generateUserId(String email) gibt jeder neuen E-Mail eine Nummer, U001, U002 und so weiter, und für eine schon gesehene E-Mail gibt sie dieselbe Nummer zurück. Groß- und Kleinbuchstaben in der E-Mail gelten als gleich. Eine Variante mit einer Hashfunktion gibt es in der nächsten Lektion.
• Ein Buchkatalog. Der Schlüssel ist die ISBN, zum Beispiel 978-3-16-148410-0, und der Wert ist der Titel. Füge Bücher hinzu, suche eines und gib alle aus, sortiert nach ISBN.
• Ein Reiseplaner. Speichere für jedes Reiseziel eine Liste von Aktivitäten: „Paris“ → „der Eiffelturm“, „der Louvre“. Gib den Plan in der Reihenfolge aus, in der die Reiseziele hinzugefügt wurden. Welche Map wählst du?
• Ein Online-Wörterbuch. Wort → Erklärung. Lies Wörter ein, bis „ende“ kommt. Für ein unbekanntes Wort gib „Dieses Wort gibt es nicht.“ aus.
• Noten nach Fach. Lies Zeilen wie „Mathe 6“, „Physik 5“, „Mathe 4“ ein und gib die Durchschnittsnote für jedes Fach aus, sortiert nach Namen.

Test

Teste dich

1. Wann ist eine HashMap besser als eine Liste?

Wenn du nach Schlüssel suchst, zum Beispiel die E-Mail zum BenutzernamenWenn du die Elemente nach Nummer brauchstWenn die Reihenfolge des Hinzufügens am wichtigsten ist

2. In der Map gibt es schon den Schlüssel "Kaffee" mit dem Wert 2. Was macht put("Kaffee", 3)?

Es wirft eine ExceptionEs fügt einen zweiten Schlüssel "Kaffee" hinzuEs ersetzt den Wert durch 3; der Schlüssel bleibt einer

3. Was gibt get für einen Schlüssel zurück, den es nicht gibt?

0Es wirft eine Exceptionnull

4. Du gibst eine HashMap aus. In welcher Reihenfolge kommen die Schlüssel heraus?

In der Reihenfolge des HinzufügensIn einer Reihenfolge, die HashMap nicht versprichtAlphabetisch

5. Was gibt add auf einem HashSet zurück, wenn der Wert schon darin ist?

false, und es ändert das Set nichtEs wirft eine Exceptiontrue, und es fügt ihn ein zweites Mal hinzu

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Interfaces · Exceptions · Strings · Listen
• Geht weiter in: Hashcodes und Hashfunktionen · Klassen in Klassen · Lambdas · Streams
• Aufgaben zum Thema: Collections