Hash Map

Eine HashMap ist neben der ArrayList eine der am häufigsten verwendeten vordefinierten Datenstrukturen in Java. Die Hash Map wird verwendet, wenn Daten als Schlüssel-Wert-Paare gespeichert werden, wobei Werte mithilfe von Schlüsseln hinzugefügt, abgerufen und gelöscht werden können.

Im folgenden Beispiel wurde ein HashMap-Objekt erstellt, um Städte anhand ihrer Postleitzahlen zu suchen, und es wurden vier Postleitzahl-Stadt-Paare zum HashMap-Objekt hinzugefügt. Am Ende wird die Postleitzahl "00710" aus der Hash Map abgerufen. Sowohl die Postleitzahl als auch die Stadt werden als Strings dargestellt.

HashMap<String, String> postalCodes = new HashMap<>();
postalCodes.put("00710", "Helsinki");
postalCodes.put("90014", "Oulu");
postalCodes.put("33720", "Tampere");
postalCodes.put("33014", "Tampere");

System.out.println(postalCodes.get("00710"));

Der interne Zustand der oben erstellten Hash Map sieht folgendermaßen aus. Jeder Schlüssel verweist auf einen Wert.

Wenn die Hash Map den verwendeten Schlüssel nicht enthält, gibt die get-Methode einen null-Verweis zurück.

HashMap<String, String> numbers = new HashMap<>();
numbers.put("One", "Uno");
numbers.put("Two", "Dos");

String translation = numbers.get("One");
System.out.println(translation);

System.out.println(numbers.get("Two"));
System.out.println(numbers.get("Three"));
System.out.println(numbers.get("Uno"));

Die Verwendung einer Hash Map erfordert die Anweisung import java.util.HashMap; am Anfang der Klasse.

Beim Erstellen einer Hash Map sind zwei Typ-Parameter erforderlich: der Typ des Schlüssels und der Typ des hinzugefügten Wertes. Wenn die Schlüssel der Hash Map vom Typ String und die Werte vom Typ Integer sind, wird die Hash Map mit der folgenden Anweisung erstellt: HashMap<String, Integer> hashmap = new HashMap<>();

Das Hinzufügen zur Hash Map erfolgt über die Methode put(*key*, *value*), die zwei Parameter hat, einen für den Schlüssel und einen für den Wert. Das Abrufen aus einer Hash Map erfolgt mit der Methode get(*key*), bei der der Schlüssel als Parameter übergeben wird und einen Wert zurückgibt.

Hash Map-Schlüssel entsprechen höchstens einem Wert

Die Hash Map enthält pro Schlüssel maximal einen Wert. Wenn ein neues Schlüssel-Wert-Paar zur Hash Map hinzugefügt wird, aber der Schlüssel bereits mit einem anderen Wert in der Hash Map verknüpft ist, verschwindet der alte Wert aus der Hash Map.

HashMap<String, String> numbers = new HashMap<>();
numbers.put("Uno", "One");
numbers.put("Dos", "Zwei");
numbers.put("Uno", "Ein");

String translation = numbers.get("Uno");
System.out.println(translation);

System.out.println(numbers.get("Dos"));
System.out.println(numbers.get("Tres"));
System.out.println(numbers.get("Uno"));

Eine Referenztyp-Variable als Hash Map-Wert

Betrachten wir, wie ein Tabellenkalkulationsprogramm funktioniert, indem wir ein Beispiel aus der Bibliothek verwenden. Sie können nach Büchern anhand des Buchtitels suchen. Wenn ein Buch mit dem angegebenen Suchbegriff gefunden wird, gibt die Bibliothek eine Referenz auf das Buch zurück. Beginnen wir mit der Erstellung einer Beispielklasse Book, die als Instanzvariablen den Namen, den Inhalt und das Erscheinungsjahr hat.

public class Book {
    private String name;
    private String content;
    private int published;

    public Book(String name, int published, String content) {
        this.name = name;
        this.published = published;
        this.content = content;
    }

    public String getName() {
        return this.name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getPublished() {
        return this.published;
    }

    public void setPublished(int published) {
        this.published = published;
    }

    public String getContent() {
        return this.content;
    }

    public void setContent(String content) {
        this.content = content;
    }

    public String toString() {
        return "Name: " + this.name + " (" + this.published + ")\n"
            + "Content: " + this.content;
    }
}

Erstellen wir eine Hash Map, die den Namen des Buches als Schlüssel verwendet, also ein String-Objekt, und das gerade erstellte Buch als Wert.

HashMap<String, Book> directory = new HashMap<>();

Die oben gezeigte Hash Map verwendet ein String-Objekt als Schlüssel. Erweitern wir das Beispiel so, dass zwei Bücher zum Verzeichnis hinzugefügt werden: "Sense and Sensibility" und "Pride and Prejudice".

Book senseAndSensibility = new Book("Sense and Sensibility", 1811, "...");
Book prideAndPrejudice = new Book("Pride and Prejudice", 1813, "...");

HashMap<String, Book> directory = new HashMap<>();
directory.put(senseAndSensibility.getName(), senseAndSensibility);
directory.put(prideAndPrejudice.getName(), prideAndPrejudice);

Bücher können anhand des Buchtitels aus dem Verzeichnis abgerufen werden. Eine Suche nach "Persuasion" führt zu keinem Ergebnis, in diesem Fall gibt die Hash Map einen null-Verweis zurück. Das Buch "Pride and Prejudice" wird jedoch gefunden.

Book book = directory.get("Persuasion");
System.out.println(book);
System.out.println();
book = directory.get("Pride and Prejudice");
System.out.println(book);

Wann sollten Hash Maps verwendet werden?

Die Hash Map ist intern so implementiert, dass die Suche nach einem Schlüssel (key) sehr schnell ist. Die Hash Map generiert aus dem Schlüssel einen "Hash-Wert", d.h. einen Code, der verwendet wird, um den Wert an einem bestimmten Ort zu speichern. Wenn ein Schlüssel verwendet wird, um Informationen aus einer Hash Map abzurufen, identifiziert dieser spezielle Code den Ort, an dem der Wert gespeichert ist, der mit dem Schlüssel verknüpft ist. In der Praxis ist es nicht erforderlich, alle Schlüssel-Wert-Paare in der Hash Map zu durchlaufen, um nach einem Schlüssel zu suchen; der zu überprüfende Satz ist deutlich kleiner. Wir werden uns mit der Implementierung einer Hash Map in den Kursen Fortgeschrittene Programmierung und Datenstrukturen und Algorithmen näher beschäftigen.

Betrachten Sie das oben eingeführte Bibliotheksbeispiel. Das gesamte Programm könnte ebenso gut unter Verwendung einer Liste implementiert worden sein. In diesem Fall würden die Bücher anstelle des Verzeichnisses in der Liste platziert und die Buchsuche würde durch Iteration über die Liste erfolgen.

Im folgenden Beispiel wurden die Bücher in einer Liste gespeichert und die Suche nach ihnen erfolgt durch Durchlaufen der Liste.

ArrayList<Book> books = new ArrayList<>();
Book senseAndSensibility = new Book("Sense and Sensibility", 1811, "...");


Book prideAndPrejudice = new Book("Pride and Prejudice", 1813, "....");
books.add(senseAndSensibility);
books.add(prideAndPrejudice);

// searching for a book named Sense and Sensibility
Book match = null;
for (Book book: books) {
    if (book.getName().equals("Sense and Sensibility")) {
        match = book;
        break;
    }
}

System.out.println(match);
System.out.println();

// searching for a book named Persuasion
match = null;
for (Book book: books) {
    if (book.getName().equals("Persuasion")) {
        match = book;
        break;
    }
}

System.out.println(match);

Für das obige Programm könnten Sie eine separate Klassenmethode get erstellen, die eine Liste und den Namen des abzurufenden Buches als Parameter erhält. Die Methode gibt ein Buch zurück, das durch den angegebenen Namen gefunden wurde, falls es existiert. Andernfalls gibt die Methode einen null-Verweis zurück.

public static Book get(ArrayList<Book> books, String name) {

    for (Book book: books) {
        if (book.getName().equals(name)) {
            return book;
        }
    }

    return null;
}

Jetzt ist das Programm etwas klarer.

ArrayList<Book> books = new ArrayList<>();
Book senseAndSensibility = new Book("Sense and Sensibility", 1811, "...");
Book prideAndPrejudice = new Book("Pride and Prejudice", 1813, "....");
books.add(senseAndSensibility);
books.add(prideAndPrejudice);

System.out.println(get(books, "Sense and Sensibility"));

System.out.println();

System.out.println(get(books, "Persuasion"));

Das Programm würde jetzt genauso funktionieren wie das Programm, das mit der Hash Map implementiert wurde, oder?

Funktional, ja. Betrachten wir jedoch die Leistung des Programms. Die Methode System.nanoTime() von Java gibt die Zeit des Computers in Nanosekunden zurück. Wir werden der oben betrachteten Funktionalität des Programms eine Berechnung hinzufügen, um festzustellen, wie lange es dauert, die Bücher abzurufen.

ArrayList<Book> books = new ArrayList<>();

// adding ten million books to the list

long start = System.nanoTime();
System.out.println(get(books, "Sense and Sensibility"));

System.out.println();

System.out.println(get(books, "Persuasion"));
long end = System.nanoTime();
double durationInMilliseconds = 1.0 * (end - start) / 1000000;

System.out.println("The book search took " + durationInMilliseconds + " milliseconds.");

Mit zehn Millionen Büchern dauert es fast eine Sekunde, um zwei Bücher zu finden. Natürlich hat die Art und Weise, wie die Liste sortiert ist, Einfluss. Wenn das gesuchte Buch zuerst in der Liste steht, wäre das Programm schneller. Wenn das Buch jedoch nicht in der Liste steht, muss das Programm alle Bücher in der Liste durchlaufen, bevor es feststellen kann, dass das Buch nicht existiert.

Betrachten wir dasselbe Programm unter Verwendung einer Hash Map.

HashMap<String, Book> directory = new HashMap<>();

// adding ten million books to the list

long start = System.nanoTime();
System.out.println(directory.get("Sense and Sensibility"));

System.out.println();

System.out.println(directory.get("Persuasion"));
long end = System.nanoTime();
double durationInMilliseconds = 1.0 * (end - start) / 1000000;

System.out.println("The book search took " + durationInMilliseconds + " milliseconds.");

Es dauerte etwa 0,4 Millisekunden, um mit der Hash Map zwei Bücher von zehn Millionen Büchern zu durchsuchen. Der Leistungsunterschied in unserem Beispiel ist mehr als tausendfach.

Der Leistungsunterschied liegt darin, dass beim Durchsuchen eines Buches in einer Liste im schlimmsten Fall alle Bücher in der Liste durchgegangen werden müssen. In einer Hash Map ist es nicht notwendig, alle Bücher zu überprüfen, da der Schlüssel den Speicherort eines bestimmten Buches in der Hash Map bestimmt. Der Leistungsunterschied hängt von der Anzahl der Bücher ab - bei beispielsweise 10 Büchern sind die Leistungsunterschiede vernachlässigbar. Bei Millionen von Büchern sind die Leistungsunterschiede jedoch deutlich sichtbar.

Bedeutet das, dass wir in Zukunft nur noch Hash Maps verwenden werden? Natürlich nicht. Hash Maps funktionieren gut, wenn wir genau wissen, wonach wir suchen. Wenn wir Bücher identifizieren wollten, deren Titel eine bestimmte Zeichenfolge enthält, wäre die Hash Map wenig nützlich.

Hash Maps haben auch keine interne Ordnung, und es ist nicht möglich, die Hash Map basierend auf den Indizes zu durchsuchen. Die Elemente in einer Liste befinden sich in der Reihenfolge, in der sie zur Liste hinzugefügt wurden.

Typischerweise werden Hash Maps und Listen zusammen verwendet. Die Hash Map bietet schnellen Zugriff auf einen bestimmten Schlüssel oder Schlüssel, während die Liste beispielsweise verwendet wird, um die Reihenfolge zu erhalten.

Hash Map als Instanzvariable

Das oben betrachtete Beispiel zum Speichern von Büchern ist problematisch, da das Schreibformat des Buches genau in Erinnerung bleiben muss. Jemand kann nach einem Buch mit einem Kleinbuchstaben suchen, während eine andere Person beispielsweise ein Leerzeichen eingeben kann, um mit dem Schreiben eines Namens zu beginnen. Betrachten wir als nächstes eine etwas verzeihendere Suche nach dem Buchtitel.

Wir machen uns die Werkzeuge zunutze, die die String-Klasse zum Verarbeiten von Zeichenfolgen bereitstellt. Die Methode toLowerCase() erstellt eine neue Zeichenfolge, bei der alle Buchstaben in Kleinbuchstaben umgewandelt wurden. Die Methode trim() erstellt hingegen eine neue Zeichenfolge, bei der leere Zeichen wie Leerzeichen am Anfang und Ende entfernt wurden.

String text = "Pride and Prejudice ";
text = text.toLowerCase(); // text currently "pride and prejudice "
text = text.trim(); // text now "pride and prejudice"

Die oben beschriebene Konvertierung der Zeichenfolge führt dazu, dass das Buch gefunden wird, auch wenn die Nutzerin oder der Nutzer den Titel des Buches mit Kleinbuchstaben eintippt.

Erstellen wir eine Library-Klasse, die eine Hash Map mit Büchern kapselt und eine case-unabhängige Suche nach Büchern ermöglicht. Wir fügen der Klasse Library Methoden zum Hinzufügen, Abrufen und Löschen hinzu. Jede dieser Methoden basiert auf einem bereinigten Namen - dies beinhaltet das Konvertieren des Namens in Kleinbuchstaben und das Entfernen unnötiger Leerzeichen vom Anfang und Ende.

Skizzieren wir zuerst die Hinzufügemethode. Das Buch wird der Hash Map hinzugefügt, wobei der Buchname als Schlüssel und das Buch selbst als Wert verwendet wird. Da wir kleinere Rechtschreibfehler zulassen möchten, wie z. B. groß- oder kleingeschriebene Zeichenfolgen oder solche mit Leerzeichen am Anfang und/oder Ende, wird der Schlüssel - der Titel des Buches - in Kleinbuchstaben konvertiert und Leerzeichen am Anfang und Ende werden entfernt.

public class Library {
    private HashMap<String, Book> directory;

    public Library() {
        this.directory = new HashMap<>();
    }

    public void addBook(Book book) {
        String name = book.getName();
        if (name == null) {
            name = "";
        }

        name = name.toLowerCase();
        name = name.trim();

        if (this.directory.containsKey(name)) {
            System.out.println("Book is already in the library!");
        } else {
            directory.put(name, book);
        }
    }
}

Die containsKey-Methode der Hash Map wird oben verwendet, um das Vorhandensein eines Schlüssels zu überprüfen. Die Methode gibt true zurück, wenn ein Wert mit dem angegebenen Schlüssel zur Hash Map hinzugefügt wurde. Andernfalls gibt die Methode false zurück.

Wir sehen bereits, dass der Code zur Bereinigung von Zeichenfolgen in jeder Methode erforderlich ist, die ein Buch verarbeitet, was ihn zu einem guten Kandidaten für eine separate Hilfsmethode macht. Die Methode wird als Klassenmethode implementiert, da sie keine Objektvariablen verarbeitet.

public static String sanitizedString(String string) {
    if (string == null) {
        return "";
    }

    string = string.toLowerCase();
    return string.trim();
}

Die Implementierung ist viel sauberer, wenn die Hilfsmethode verwendet wird.

public class Library {
    private HashMap<String, Book> directory;

    public Library() {
        this.directory = new HashMap<>();
    }

    public void addBook(Book book) {
        String name = sanitizedString(book.getName());

        if (this.directory.containsKey(name)) {
            System.out.println("Book is already in the library!");
        } else {
            directory.put(name, book);
        }
    }

    public Book getBook(String bookTitle) {
        bookTitle = sanitizedString(bookTitle);
        return this.directory.get(bookTitle);
    }



    public void removeBook(String bookTitle) {
        bookTitle = sanitizedString(bookTitle);

        if (this.directory.containsKey(bookTitle)) {
            this.directory.remove(bookTitle);
        } else {
            System.out.println("Book was not found, cannot be removed!");
        }
    }

    public static String sanitizedString(String string) {
        if (string == null) {
            return "";
        }

        string = string.toLowerCase();
        return string.trim();
    }
}

Betrachten wir die Verwendung der Klasse.

Book senseAndSensibility = new Book("Sense and Sensibility", 1811, "...");
Book prideAndPrejudice = new Book("Pride and Prejudice", 1813, "....");

Library library = new Library();
library.addBook(senseAndSensibility);
library.addBook(prideAndPrejudice);

System.out.println(library.getBook("pride and prejudice"));
System.out.println();

System.out.println(library.getBook("PRIDE AND PREJUDICE"));
System.out.println();

System.out.println(library.getBook("SENSE"));

Im obigen Beispiel haben wir das DRY-Prinzip (Don't Repeat Yourself) eingehalten, wonach Code-Duplikationen vermieden werden sollten. Das Bereinigen einer Zeichenfolge, d. h. das Umwandeln in Kleinbuchstaben und das Trimmen, d. h. das Entfernen leerer Zeichen vom Anfang und Ende, wäre in unserer Bibliotheksklasse ohne die Methode sanitizedString häufig wiederholt worden. Wiederholter Code wird oft erst bemerkt, wenn er bereits geschrieben ist, was bedeutet, dass er fast immer in den Code gelangt. Daran ist (zunächst) nichts auszusetzen - das Wichtigste ist, dass der Code so bereinigt wird, dass Stellen, die aufgeräumt werden müssen, erkannt werden.

Iterieren über die Schlüssel einer Hash Map

Manchmal möchten wir nach einem Buch anhand eines Teils seines Titels suchen. Die get-Methode in der Hash Map ist in diesem Fall nicht anwendbar, da sie für die Suche nach einem bestimmten Schlüssel verwendet wird. Die Suche nach einem Teil eines Buchtitels ist damit nicht möglich.

Wir können die Werte einer Hash Map durchlaufen, indem wir eine for-each-Schleife über die Menge verwenden, die von der keySet()-Methode der Hash Map zurückgegeben wird.

Im Folgenden wird eine Suche nach allen Büchern durchgeführt, deren Namen die angegebene Zeichenfolge enthalten.

public ArrayList<Book> getBookByPart(String titlePart) {
    titlePart = sanitizedString(titlePart);

    ArrayList<Book> books = new ArrayList<>();

    for(String bookTitle : this.directory.keySet()) {
        if(!bookTitle.contains(titlePart)) {
            continue;
        }

        // if the key contains the given string
        // we retrieve the value related to it
        // and add it to the set of books to be returned

        books.add(this.directory.get(bookTitle));
    }

    return books;
}

Auf diese Weise verlieren wir jedoch den Geschwindigkeitsvorteil, der mit der Hash Map verbunden ist. Die Hash Map ist intern so implementiert, dass die Suche nach einem einzelnen Schlüssel extrem schnell ist. Im obigen Beispiel werden alle Buchtitel durchgegangen, wenn mit einem bestimmten Schlüssel nach einem Buch gesucht wird, um das Vorhandensein eines einzelnen Buches zu überprüfen.

Durchlaufen der Werte einer Hash Map

Die zuvor beschriebene Funktionalität könnte auch durch das Durchlaufen der Werte der Hash Map implementiert werden. Die Menge der Werte kann mit der Methode values​​() der Hash Map abgerufen werden. Auch diese Menge an Werten kann mit einer for-each-Schleife durchlaufen werden.

public ArrayList<Book> getBookByPart(String titlePart) {
    titlePart = sanitizedString(titlePart);

    ArrayList<Book> books = new ArrayList<>();

    for(Book book : this.directory.values()) {
        if(!book.getName().contains(titlePart)) {
            continue;
        }

        books.add(book);
    }

    return books;
}

Wie im vorherigen Beispiel geht auch bei dieser Methode der Geschwindigkeitsvorteil verloren, der mit der Hash Map verbunden ist.

Primitive Variablen in Hash Maps

Eine Hash Map erwartet, dass nur Referenz-Variablen hinzugefügt werden (wie auch ArrayList). Java konvertiert primitive Variablen in ihre entsprechenden Referenztypen, wenn eine der eingebauten Datenstrukturen von Java (wie ArrayList und HashMap) verwendet wird. Obwohl der Wert 1 als Wert der primitiven Variablen int dargestellt werden kann, sollte sein Typ als Integer definiert werden, wenn ArrayLists und HashMaps verwendet werden.

HashMap<Integer, String> hashmap = new HashMap<>(); 
hashmap.put(1, "Ole!"); // funktioniert (!)
HashMap<int, String> map2 = new HashMap<>(); // funktioniert nicht

Der Schlüssel und das Objekt, das in einer Hash Map gespeichert wird, sind immer Referenztyp-Variablen. Wenn Sie eine primitive Variable als Schlüssel oder Wert verwenden möchten, gibt es eine Referenztyp-Version für jede davon. Einige davon sind unten aufgeführt.

Java konvertiert primitive Variablen automatisch in Referenztypen, wenn sie entweder zu einer HashMap oder einer ArrayList hinzugefügt werden. Diese automatische Konvertierung in eine Referenztyp-Variable wird in Java als Auto-Boxing bezeichnet, d. h. das automatische Platzieren in einer Box. Die automatische Konvertierung ist auch in die andere Richtung möglich.

int key = 2;
HashMap<Integer, Integer> hashmap = new HashMap<>();
hashmap.put(key, 10);
int value = hashmap.get(key);
System.out.println(value);

Das folgende Beispiel beschreibt eine Klasse, die zur Zählung der Sichtungen von Fahrzeugkennzeichen verwendet wird (z.B. um zu zählen, wie oft ein Auto mit einem Fahrzeugkennzeichen an einer Überwachungskamera vorbei fährt). Eine automatische Typkonvertierung findet in den Methoden addSighting und timesSighted statt.

public class registerSightingCounter {
    private HashMap<String, Integer> allSightings;

    public registerSightingCounter() {
        this.allSightings = new HashMap<>();
    }

    public void addSighting(String sighted) {
        if (!this.allSightings.containsKey(sighted)) {
            this.allSightings.put(sighted, 0);
        }

        int timesSighted = this.allSightings.get(sighted);
        timesSighted++;
        this.allSightings.put(sighted, timesSighted);
    }

    public int timesSighted(String sighted) {
        return this.allSightings.get(sighted);
    }
}

Bei Typkonvertierungen besteht jedoch ein Risiko. Wenn wir versuchen, einen null-Verweis - eine Sichtung, die nicht in der HashMap enthalten ist - in eine Ganzzahl umzuwandeln, tritt ein java.lang.reflect.InvocationTargetException Fehler auf. Ein solcher Fehler kann in der Methode timesSighted im obigen Beispiel auftreten - wenn die allSightings-HashMap den gesuchten Wert nicht enthält, gibt sie einen null-Verweis zurück und die Konvertierung in eine Ganzzahl schlägt fehl.

Bei der Durchführung einer automatischen Konvertierung sollten wir sicherstellen, dass der zu konvertierende Wert nicht null ist. Zum Beispiel sollte die Methode timesSighted im Programm oben wie folgt korrigiert werden.

public int timesSighted(String sighted) {
    return this.allSightings.getOrDefault(sighted, 0);
}

Die getOrDefault-Methode der HashMap sucht nach dem als Parameter übergebenen Schlüssel in der HashMap. Wenn der Schlüssel nicht gefunden wird, gibt sie den Wert des zweiten übergebenen Parameters zurück. Die oben gezeigte Einzeiler-Methode ist in ihrer Funktion gleichwertig mit der folgenden.

public int timesSighted(String sighted) {
    if (this.allSightings.containsKey(sighted)) {
        return this.allSightings.get(sighted);
    }

    return 0;
}

Wir können auch die Methode addSighting etwas übersichtlicher gestalten. In der ursprünglichen Version wird der Sichtungsanzahl-Wert in der HashMap auf 0 gesetzt, wenn der angegebene Schlüssel nicht gefunden wird. Dann wird die Anzahl der Sichtungen abgerufen, um eins erhöht und der vorherige Sichtungswert wird durch den neuen Wert ersetzt, indem die inkrementierte Anzahl wieder in die HashMap eingefügt wird. Ein Teil davon kann auch durch die Methode getOrDefault ersetzt werden.

public class registerSightingCounter {
    private HashMap<String, Integer> allSightings;

    public registerSightingCounter() {
        this.allSightings = new HashMap<>();
    }

    public void addSighting(String sighted) {
        int timesSighted = this.allSightings.getOrDefault(sighted, 0);
        timesSighted++;
        this.allSightings.put(sighted, timesSighted);
    }

    public int timesSighted(String sighted) {
        return this.allSightings.getOrDefault(sighted, 0);
    }
}