Efficient data structures: Sets & Maps

Codeoptimierung in Java

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

Raum-/Zeitkomplexität anwenden

Jetzt kennen wir Raum- und Zeitkomplexität!

Wie setzen wir das ein, um effizienteren Code zu schreiben?

Indem wir die richtige Datenstruktur wählen!

Codeoptimierung in Java

Ein Benutzerverwaltungssystem

  • Wir bauen ein Benutzerverwaltungssystem

  • Für einen gegebenen Benutzernamen müssen wir prüfen, ob ein Benutzer existiert

  • Mit einer Liste: Komplexität $O(n)$

public boolean usernameExists(ArrayList<String> users, String newUsername) {
    for (String username : users) {
        if (username.equals(newUsername)) {
            return true;
        }
    }
    return false;
}
Codeoptimierung in Java

Sets

  • Eine Sammlung eindeutiger Elemente mit schneller Suche
  • $O(1)$ durchschnittliche Zeitkomplexität für Einfügen, Entfernen und Existenzprüfung

Verbesserte Lösung für die Benutzerverwaltung:

public class UserRegistry {
    private HashSet<String> users = new HashSet<>();

    public boolean userExists(String username) {
        return users.contains(username); // O(1) average time
    }
}
Codeoptimierung in Java

Maps

  • Wie ein Wörterbuch: Wort (Schlüssel) -> Definition (Wert)
  • HashMap: $O(1)$ durchschnittliche Zeitkomplexität für Operationen
public class UserCache {
    private HashMap<String, UserProfile> userProfiles = new HashMap<>();

    public UserProfile getUser(String username) {
        return userProfiles.get(username);  // O(1) average time
    }
}
Codeoptimierung in Java

Hashcode-Methode

  • Warum sind die schnell? -> hashCode()
  • Im ArrayList-Beispiel kannten wir den Index des gesuchten Benutzernamens nicht
  • Mit der Methode hashcode() können wir ein Objekt in einen suchbaren Index umwandeln
  • Zum Beispiel pavlos.2020 -> 35189

pavlos.2020, verarbeitet durch hashcode, ergibt 35189

Codeoptimierung in Java

Elemente indizieren

  • HashMap und HashSet basieren auf einem Array
  • Wenn wir ein Element hinzufügen:
    • Java ruft hashCode() auf deinem Element auf und erhält eine ganze Zahl
    • Darauf wird Modulo angewendet, um die Bucket-Nummer zu bekommen

Beispiel:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

"optimizingCodeInJava" -> 1406313774 // Implemented by Java
1406313774 % 16 = 14 <- das ist unser Bucket!
Codeoptimierung in Java

Kollisionen

  • Wenn mehr als ein Eintrag im selben Bucket landet
    • Das nennt man eine Kollision
  • LinkedList für den Bucket
  • Darum sagen wir $O(1)$ im Durchschnitt
Codeoptimierung in Java

Merksatz

Die Wahl der Datenstruktur ist wie das richtige Werkzeug für eine Aufgabe – ein Hammer (ArrayList) ist super für Nägel, aber schlecht für Schrauben (da passt ein Set besser).

Ein offener Werkzeugkoffer mit Hammer, Schraubendreher, Schraubenschlüssel und Zange nebeneinander

Codeoptimierung in Java

Lass uns üben!

Codeoptimierung in Java

Preparing Video For Download...