Tutorium 20.05¶

Wiederholung¶

Jede Collection beantwortet eine andere Art von Frage.

Überblick über typische Collections¶
Problem	Typische Collection	Gedanke
Werte in einer Reihenfolge speichern	`List`	Reihenfolge ist wichtig, Duplikate sind erlaubt.
Werte nur einmal speichern	`Set`	Duplikate sollen automatisch vermieden werden.
Werte über einen Schlüssel finden	`Map`	Ein Schlüssel verweist auf einen Wert.
Elemente in Eingangsreihenfolge verarbeiten	`Queue`	First in, first out.
Letzte Aktion zuerst rückgängig machen	`Deque`	Last in, first out.
Werte sortiert speichern	`TreeSet` oder `TreeMap`	Elemente werden automatisch sortiert gehalten.

Diese Fragen sollten bei jeder Aufgabe gestellt werden:

Sind Duplikate erlaubt?
Muss die Reihenfolge erhalten bleiben?
Muss ich Werte über einen Schlüssel finden?
Muss ich zählen oder gruppieren?
Muss ich schnell prüfen, ob ein Wert existiert?
Muss die Ausgabe sortiert sein?

Eine List merkt sich Reihenfolge. Ein Set verhindert Duplikate. Eine Map ordnet Schlüssel Werten zu. Eine Queue modelliert Warteschlangen. Eine Deque modelliert Verlauf, Undo oder Stack-Verhalten.

Aufgabe 1¶

Entscheide für jedes Szenario, welche Collection sinnvoll wäre. Es geht zunächst nicht um Programmcode, sondern nur um die Modellierung.

Szenario A¶

Die Namen von Studierenden sollen in der Reihenfolge gespeichert werden, in der sie sich angemeldet haben.

Szenario B¶

Für einen Newsletter sollen E-Mail-Adressen gespeichert werden. Jede Adresse darf nur einmal vorkommen.

Szenario C¶

Studierende sollen über ihre Matrikelnummer gefunden werden können.

Szenario D¶

Druckaufträge sollen in der Reihenfolge verarbeitet werden, in der sie angekommen sind.

Szenario E¶

In einem Text soll gezählt werden, wie oft jedes Wort vorkommt.

Aufgabe 2¶

Im folgenden Programm werden Benutzernamen gespeichert. Ein Benutzername darf aber nur einmal vorkommen.

Fehlerhafte Modellierung mit einer List¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> usernames = new ArrayList<>();

        usernames.add("anna");
        usernames.add("tom");
        usernames.add("anna");

        System.out.println(usernames);
    }
}

Aufgabe:

Erkläre, warum List hier nicht ideal ist.
Korrigiere den Code.
Erkläre, was mit dem zweiten "anna" passiert.

Aufgabe 3¶

Im folgenden Programm werden besuchte Webseiten gespeichert.

Besuchte Seiten mit Duplikaten¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> visitedPages = new ArrayList<>();

        visitedPages.add("/home");
        visitedPages.add("/login");
        visitedPages.add("/home");
        visitedPages.add("/products");
        visitedPages.add("/login");

        System.out.println(visitedPages);
    }
}

Aufgabe:

Was gibt das Programm aus?
Welche Collection wäre sinnvoll, wenn jede Seite nur einmal erscheinen soll?
Welche Information geht verloren, wenn man ein Set verwendet?

Aufgabe 4¶

Zähle, wie oft jeder Name in der Liste vorkommt.

Startercode für einen Häufigkeitszähler¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> names = List.of(
            "Anna", "Tom", "Anna", "Lisa", "Tom", "Anna"
        );

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

        // TODO: Namen zählen

        System.out.println(counts);
    }
}

Aufgabe:

Ergänze den Code.
Erkläre, warum eine Map<String, Integer> sinnvoll ist.
Was ist der Schlüssel, was ist der Wert?

Aufgabe 5¶

In dieser Aufgabe sollen mehrere Studierende einem Kurs zugeordnet werden.

Startercode zur Gruppierung nach Kurs¶

import java.util.*;

class Student {
    String name;
    String course;

    Student(String name, String course) {
        this.name = name;
        this.course = course;
    }

    @Override
    public String toString() {
        return name;
    }
}

public class Main {
    public static void main(String[] args) {
        List<Student> students = List.of(
            new Student("Anna", "Java"),
            new Student("Tom", "Python"),
            new Student("Lisa", "Java"),
            new Student("Ben", "Databases")
        );

        Map<String, List<Student>> studentsByCourse = new HashMap<>();

        // TODO: Studierende nach Kurs gruppieren

        System.out.println(studentsByCourse);
    }
}

Aufgabe:

Ergänze den Code.
Erkläre den Typ Map<String, List<Student>>.
Warum reicht hier keine Map<String, Student>?

Aufgabe 6¶

Ein Telefonbuch ordnet Namen Telefonnummern zu.

Telefonbuch mit einer Map¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<String, String> phoneBook = new HashMap<>();

        phoneBook.put("Anna", "12345");
        phoneBook.put("Tom", "99999");
        phoneBook.put("Lisa", "54321");

        System.out.println(phoneBook.get("Tom"));
    }
}

Aufgabe:

Was gibt das Programm aus?
Was passiert, wenn danach phoneBook.put("Tom", "11111") ausgeführt wird?
Dürfen zwei verschiedene Namen dieselbe Telefonnummer haben?

Aufgabe 7¶

Eine Warteschlange verarbeitet Elemente in der Reihenfolge, in der sie eingefügt wurden.

Warteschlange mit Queue und ArrayDeque¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Queue<String> waitingLine = new ArrayDeque<>();

        waitingLine.add("Anna");
        waitingLine.add("Tom");
        waitingLine.add("Lisa");

        System.out.println(waitingLine.poll());
        System.out.println(waitingLine.poll());

        waitingLine.add("Ben");

        System.out.println(waitingLine.poll());
        System.out.println(waitingLine.poll());
    }
}

Aufgabe:

Was gibt das Programm aus?
Warum passt Queue hier besser als List?
Was bedeutet FIFO?

Aufgabe 8¶

Eine Undo-Funktion macht meistens die zuletzt ausgeführte Aktion zuerst rückgängig.

Undo-Verlauf mit Deque¶

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Deque<String> history = new ArrayDeque<>();

        history.push("Typed A");
        history.push("Typed B");
        history.push("Deleted B");

        System.out.println("Undo: " + history.pop());
        System.out.println("Undo: " + history.pop());
    }
}

Aufgabe:

Was gibt das Programm aus?
Warum ist Deque hier sinnvoll?
Was bedeutet LIFO?

Aufgabe 9¶

Dieses Beispiel zeigt, dass HashSet bei eigenen Klassen von equals() und hashCode() abhängt.

Zwei scheinbar gleiche User in einem HashSet¶

import java.util.*;

class User {
    String name;

    User(String name) {
        this.name = name;
    }
}

public class Main {
    public static void main(String[] args) {
        Set<User> users = new HashSet<>();

        users.add(new User("Anna"));
        users.add(new User("Anna"));

        System.out.println(users.size());
    }
}

Aufgabe:

Ist die Ausgabe 1 oder 2?
Warum?
Wie kann man das Verhalten korrigieren?

Aufgabe 10¶

In dieser Aufgabe sollen mehrere Collections kombiniert werden.

Ein Kurs verwaltet Studierende.

Ein Student hat:

id
name
email
grade

Das Programm soll:

alle Studierenden in Einfügereihenfolge speichern,
Studierende über ihre ID finden,
doppelte E-Mail-Adressen verhindern,
Studierende nach Note gruppieren.

Entscheide, welche Collections für die einzelnen Anforderungen sinnvoll sind. Implementiere anschließend eine einfache Version.

Lösung anzeigen

Sinnvolle Collections:

Sinnvolle Datenstrukturen für die Studierendenverwaltung¶

List<Student> students = new ArrayList<>();
Map<Integer, Student> studentsById = new HashMap<>();
Set<String> usedEmails = new HashSet<>();
Map<Integer, List<Student>> studentsByGrade = new HashMap<>();

Bedeutung:

List<Student> speichert alle Studierenden in Reihenfolge.
Map<Integer, Student> ermöglicht schnellen Zugriff über die ID.
Set<String> verhindert doppelte E-Mail-Adressen.
Map<Integer, List<Student>> gruppiert mehrere Studierende nach Note.

Beispielimplementierung:

Mini-Projekt mit mehreren Collections¶

import java.util.*;

class Student {
    int id;
    String name;
    String email;
    int grade;

    Student(int id, String name, String email, int grade) {
        this.id = id;
        this.name = name;
        this.email = email;
        this.grade = grade;
    }

    @Override
    public String toString() {
        return name + "(" + id + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        Map<Integer, Student> studentsById = new HashMap<>();
        Set<String> usedEmails = new HashSet<>();
        Map<Integer, List<Student>> studentsByGrade = new HashMap<>();

        addStudent(
            new Student(1, "Anna", "anna@example.com", 1),
            students,
            studentsById,
            usedEmails,
            studentsByGrade
        );

        addStudent(
            new Student(2, "Tom", "tom@example.com", 2),
            students,
            studentsById,
            usedEmails,
            studentsByGrade
        );

        addStudent(
            new Student(3, "Lisa", "lisa@example.com", 1),
            students,
            studentsById,
            usedEmails,
            studentsByGrade
        );

        System.out.println(students);
        System.out.println(studentsById.get(2));
        System.out.println(studentsByGrade);
    }

    static void addStudent(
        Student student,
        List<Student> students,
        Map<Integer, Student> studentsById,
        Set<String> usedEmails,
        Map<Integer, List<Student>> studentsByGrade
    ) {
        if (usedEmails.contains(student.email)) {
            System.out.println("E-Mail bereits vergeben: " + student.email);
            return;
        }

        students.add(student);
        studentsById.put(student.id, student);
        usedEmails.add(student.email);

        studentsByGrade
            .computeIfAbsent(student.grade, grade -> new ArrayList<>())
            .add(student);
    }
}

Der wichtigste Punkt ist hier nicht die konkrete Syntax, sondern die Erkenntnis:

Dieselben Objekte können in mehreren Collections organisiert werden, weil jede Collection eine andere Zugriffsfrage beantwortet.

Zusatzaufgabe¶

Ordne jedem Problem eine Collection zu und begründe kurz.

Szenarien¶
Szenario	Collection
Eine Einkaufsliste, bei der die Reihenfolge erhalten bleiben soll.	?
Eine Menge erlaubter Rollen wie `ADMIN`, `USER` und `GUEST`.	?
Eine Zuordnung von Produktnummer zu Produkt.	?
Eine Warteschlange von Support-Tickets.	?
Eine Undo-Historie in einem Texteditor.	?
Eine alphabetisch sortierte Liste eindeutiger Namen.	?

Lösung anzeigen

Mögliche Lösungen¶
Szenario	Mögliche Collection
Einkaufsliste mit Reihenfolge	`List<String>`
Menge erlaubter Rollen	`Set<Role>` oder bei Enums `EnumSet<Role>`
Produktnummer zu Produkt	`Map<Integer, Product>`
Warteschlange von Support-Tickets	`Queue<Ticket>`
Undo-Historie	`Deque<Action>`
Alphabetisch sortierte eindeutige Namen	`TreeSet<String>`