About this episode
Nach einem kurzen Feedback gehen wir diesmal zu Karten… nein, Abbildungen über. Das ist am Anfang kein Problem. Nur wenn die Eimer für Streuwertfunktionen kleiner werden, hat ttimeless etwas Schwierigkeiten.Shownotes
Rückbezug STP077: Liste von Listen
verschiedene Datenstrukturen implementieren dasselbe Datenformat mit unterschiedlichen Laufzeitcharakteristiken
heute analog dazu Besprechung von assoziativen Datenfeldern
Rückbezug STP072: assoziative Datenfelder (wir sagen hier "Maps"; heißt je nach Programmiersprache auch "Objekt", "Dictionary", etc.)
eine Sammlung von Wertepaaren mit jeweils einem eindeutigen Schlüssel ("Key") und einem zugeordneten Wert ("Value")
z.B. Wörterbuch: Schlüssel ist das Lemma, Wert ist die Definition
z.B. Verzeichnis im Dateisystem: Schlüssel ist der Dateiname, Wert ist die Datei (bzw. das Unterverzeichnis)
praktisches Beispiel: Wörter zählen
es geht hier nur um Wertepaare, die aktiv im Speicher vorliegen, nicht um berechnete Abbildungen (Gegenbeispiel: Suchmaschine bildet von Suchanfrage auf Ergebnisseite ab)
Ansatz 1: "Sammlung von Wertepaaren" als Liste umsetzen
sofern unsortiert, ist die algorithmische Komplexität für die meisten Operationen sehr schlecht
z.B. Suchen nach einem bestimmten Schlüssel in linearer Zeit (O(n)), wenn man die Liste von vorne nach hinten durchgehen muss
z.B. Einfügen eines neuen Schlüssels auch nur in linearer Zeit, weil man einen evtl. existierenden Eintrag mit demselben Schlüssel finden und ersetzen
praktikable Umsetzung unter Verwendung einer sortierten Liste, um bestimmte Schlüssel schnell aufzufinden
meistens mittels eines balancierten Baums, z.B. in Rust BTreeMap oder in C++ std::map
Problem: Schlüssel müssen sortierbar sein (Beispiel: Strings, Ganzzahlen; Gegenbeispiel: komplexe Zahlen, Fließkommazahlen, ungeordnete Mengen)
Problem: auch bei sortierbaren Schlüsseln können Vergleiche teuer sein
Wie können wir die Vergleiche günstiger machen?
Ansatz 2: Vorsortierung anhand von Streuwertfunktionen (Hashes)
Idee: bei Suche nach einem bestimmten Schlüssel wird ein Hash des Schlüssels ermittelt (in Größenordnung einer kleinen Ganzzahl, z.B. 4 oder 8 Byte; nicht ein kryptografisch starker Hash wie SHA-2 mit 28-64 Bytes); damit schnelle Vergleiche möglich -> Hashtabelle
Strategie 1: Gruppierung der Wertepaare in "Buckets" anhand der ersten K Bits des Hash-Wertes des Schlüssels
K richtet sich nach der Gesamtanzahl an Wertepaaren (z.B. für 50 Elemente könnt
