Datenstrukturen

Der Werkzeugkasten

Arrays und Listen kamen schon in der Speicherhierarchie vor: Ein Array liegt am Stück im Speicher, eine verkettete Liste verstreut. Dass die Liste in der O-Notation beim Einfügen besser aussieht, ändert wenig – man muss die Einfügestelle ja erst finden, und das ist bei ihr O(n) mit vielen Cache-Fehlschlägen.

Die Hashtabelle: wie HashMap funktioniert

Eine Hashtabelle ist ein Array von Fächern (Buckets). Aus dem Schlüssel wird eine Zahl berechnet, der Hashcode, und daraus das Fach. Zum Finden rechnet man dasselbe noch einmal und schaut in genau ein Fach – egal, wie groß die Tabelle ist. Landen zwei Schlüssel im selben Fach, ist das eine Kollision; sie liegen dann in einer kleinen Liste nebeneinander. Probier es mit echten Java-Hashcodes:

Drei Dinge folgen daraus für jeden Java-Entwickler:

• equals und hashCode gehören zusammen. Gleiche Objekte müssen gleiche Hashcodes haben, sonst findet die Map sie nicht – sie schaut im falschen Fach nach. Records erzeugen beides automatisch und richtig.
• Schlüssel dürfen sich nicht ändern. Ändert sich ein Feld, das in den Hashcode eingeht, nachdem der Schlüssel in der Map liegt, liegt er im falschen Fach – und ist für get unauffindbar, obwohl er noch da ist.
• Ein schlechter Hashcode macht aus O(1) O(n). Seit Java 8 wandelt HashMap ein überfülltes Fach in einen kleinen Baum um und begrenzt den Schaden auf O(log n). Gute Verteilung bleibt trotzdem wichtig.

Suchbäume: sortiert und trotzdem schnell

Ein binärer Suchbaum hält Werte so, dass links von jedem Knoten nur Kleinere und rechts nur Größere stehen. Gesucht wird von der Wurzel abwärts, bei jedem Schritt eine Richtung – wie die binäre Suche aus dem vorigen Eintrag. Aber nur, wenn der Baum ausgewogen ist. Füge die Zahlen 1 bis 15 in verschiedener Reihenfolge ein:

Deshalb benutzen echte Implementierungen selbstbalancierende Bäume, die sich beim Einfügen und Löschen umbauen. Javas TreeMap ist ein Rot-Schwarz-Baum: Jeder Knoten trägt eine Farbe, und ein paar Regeln über die Farben garantieren, dass kein Weg mehr als doppelt so lang ist wie ein anderer. Datenbanken benutzen die breiteren B-Bäume, deren Knoten eine ganze Speicherseite füllen. Der Lohn für den Aufwand: Ein Baum kennt die Reihenfolge. firstKey(), ceilingKey(x), subMap(von, bis) – all das kann eine Hashtabelle nicht.

Der Heap: immer das Kleinste zuerst

Manchmal braucht man nicht alles sortiert, sondern nur immer das kleinste Element: die nächste fällige Aufgabe, den kürzesten offenen Weg, die Anfrage mit der höchsten Priorität. Dafür gibt es den Heap: ein Baum, in dem jeder Knoten kleiner ist als seine Kinder. Die Wurzel ist also immer das Minimum. Der Clou: Er wird lückenlos in einem Array gespeichert – die Kinder von Position i stehen an 2i+1 und 2i+2.

Ein neues Element kommt ans Ende und steigt auf, solange es kleiner ist als sein Elternknoten. Beim Entnehmen rückt das letzte Element an die Spitze und sinkt ab. Beides berührt nur einen Weg von der Wurzel zu einem Blatt – O(log n). Auf diesem Prinzip beruhen auch der Sortieralgorithmus Heapsort und Dijkstras Algorithmus für kürzeste Wege in Navigationssystemen.

Graphen

Ein Graph besteht aus Knoten und Kanten: Städte und Straßen, Personen und Freundschaften, Klassen und ihre Abhängigkeiten, Dienste und ihre Aufrufe. Gespeichert wird er meist als Adjazenzliste – für jeden Knoten die Liste seiner Nachbarn – oder bei dichten Graphen als Matrix. Die wichtigsten Algorithmen darauf: Breitensuche (kürzester Weg nach Anzahl Schritten), Tiefensuche (Erreichbarkeit, Zyklen finden), Dijkstra (kürzester Weg nach Gewicht) und topologisches Sortieren – genau das tut Maven, wenn es Module in die richtige Build-Reihenfolge bringt.

Für Entwickler übersetzt

// Seit Java 21: SequencedCollection – einheitlicher Zugriff auf Anfang und Ende
List<String> liste = new ArrayList<>(List.of("a", "b", "c"));
liste.getFirst();   liste.getLast();   liste.reversed();

LinkedHashMap<String, Integer> m = new LinkedHashMap<>();
m.putFirst("neu", 1);                    // vorn einfügen
m.firstEntry();  m.pollLastEntry();

Häufige Irrtümer

Verwandte Begriffe