Eine Datenstruktur wählen

Unter 1023 Schlüsseln macht eine lineare Suche nach einem fehlenden Schlüssel 1023 Vergleiche, die binäre Suche 10, und eine Hashtabelle mit 1023 Buckets kam im Labor mit höchstens 6 aus.

Bei den Fragen anfangen, die du stellen wirst

Keine Struktur ist in allem die beste. Jede macht manche Operationen billig, indem sie andere teuer macht. Wählen kannst du also, indem du auflistest, was dein Programm am häufigsten tun wird. MIT 6.006 teilt die Möglichkeiten in zwei Schnittstellen. Eine Sequenz hält Elemente in einer Reihenfolge, die du festlegst (erstes, zweites, drittes), und du fragst Elemente nach ihrer Position ab. Eine Menge (Set) hält Elemente nach Schlüssel, und du fragst, ob ein Schlüssel da ist, nach dem kleinsten Schlüssel oder nach dem nächsten nach einem bestimmten Schlüssel. Eine Menge ohne die Ordnungsfragen heißt Wörterbuch (Dictionary).

Ein paar häufige Situationen und die übliche Antwort:

• Elemente nach Position lesen, am Ende anfügen: ein dynamisches Array (ein JavaScript-Array).
• Rückgängig-Verlauf, passende Klammern, Tiefensuche: ein Stapel, also ein Array, das nur am Ende benutzt wird.
• Aufträge in der Reihenfolge des Eintreffens, Breitensuche: eine Warteschlange, mit head-Index oder Ringpuffer statt shift auf einem langen Array.
• Dinge nach Name oder ID nachschlagen: eine Hashtabelle, in JavaScript also Map oder Set.
• Schlüssel beim Einfügen und Löschen sortiert halten, nach dem nächsten Schlüssel fragen: ein ausgeglichener binärer Suchbaum.
• Viele Einfügungen und Löschungen an einer Stelle, die du schon hast: eine verkettete Liste.

Dieselbe Suche in fünf Strukturen

Das Labor unten speichert dieselben Schlüssel auf fünf Arten und zählt die Vergleiche, die nötig sind, um einen davon zu finden. Die Schlüssel sind 15, 127 oder 1023 zufällige ganze Zahlen. Das unsortierte Array nutzt die lineare Suche. Das sortierte Array nutzt die binäre Suche. Der ausgeglichene Baum wurde gebaut, indem zuerst die mittleren Schlüssel eingefügt wurden, er ist also so niedrig wie möglich. Der andere Baum wurde aus den sortierten Schlüsseln gebaut und ist daher eine Kette. Die Hashtabelle hat so viele Buckets wie Schlüssel und zählt 1 für die Berechnung von h(k).

Bei 15 Schlüsseln sind die Unterschiede klein: Die lineare Suche braucht im Mittel 8 Vergleiche, die binäre Suche etwa 3.3. Bei 1023 Schlüsseln nicht mehr. Die lineare Suche braucht im Mittel 512 und für einen fehlenden Schlüssel 1023, während die binäre Suche und der ausgeglichene Baum nie mehr als 10 brauchen. Der Ketten-Baum ist so schlecht wie die lineare Suche. Die Hashtabelle bleibt bei jeder Größe im Mittel zwischen 2.3 und 2.5, weil ihre Ketten kurz bleiben, und in diesem Labor lag ihr schlechtester Fall bei 1023 Schlüsseln bei 6. Deshalb ist Map die Standardwahl zum Nachschlagen, und deshalb lohnen sich sortierte Strukturen nur, wenn du auch die Ordnung brauchst.

Jede Zelle dieser beiden Tabellen ist die Wachstumsrate der Kosten bei n Elementen, nach den Tabellen in den MIT-Vorlesungsunterlagen 2, 4 und 7. Hashtabellen und Suchbäume stehen nur in der zweiten Tabelle, weil sie nach Schlüssel arbeiten, nicht nach Position. In einem unsortierten Array oder einer Liste kostet das Einfügen eines Schlüssels n, weil man erst prüfen muss, dass er nicht schon da ist. Das sortierte Array findet schnell, muss aber Werte verschieben, um Platz für einen neuen Schlüssel zu machen.

Map oder Objekt?

JavaScript-Programme verwenden oft ein normales Objekt als Wörterbuch und schreiben prices["apple"]. MDN nennt Gründe, Map vorzuziehen, wenn die Schlüssel aus Daten stammen: Ein Objekt hat einen Prototyp und enthält daher Standardschlüssel, die mit deinen kollidieren könnten. Eine Map kann jeden Wert als Schlüssel nehmen, nicht nur Strings und Symbole. Ihre Größe ist eine einzige Eigenschaft, map.size. Und sie wird in Einfügereihenfolge durchlaufen. Für Datensätze mit einer festen Menge benannter Felder bleiben Objekte die natürliche Wahl.