October 02, 2025

STP079: Feld von Feldern

1 hour 2 minutes

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önnte man K = 5 oder 6 und damit 2^K = 32 oder 64 Buckets wählen)

innerhalb der Buckets einfache Listen von Wertepaaren, die in diesen Bucket fallen; idealerweise nur ein Eintrag pro Bucket

durch dynamisches Anpassen der Bucket-Anzahl Abwägung zwischen Speicheraufwand für evtl. leere Buckets einerseits und Zeitaufwand für Durchsuchen übervoller Buckets andererseits

Strategie 2: wie 1, aber jeder Bucket kann maximal ein Element aufnehmen

bei Kollisionen strategisches Ausweichen auf andere Buckets in einem systematischen Muster, bis ein freier Platz gefunden wird

große Variation von Implementationsstrategien für dieses "strategische Ausweichen"

Vorwärtsbezug zu STP080: Komplexitätsattacke auf Hashmaps (eine Instanz von CWE-400)

Problem, wenn Hashmap mit nutzerdefinierten Daten gefüllt wird: Angreifer könnte Daten so wählen, dass sie alle im selben Bucket landen wollen

damit extrem hohe Rechenlast durch ständige Kollisionen

Lösung: Durchmischen des Hash mittels prozessinterner Geheimzahl (siehe STP044 zu Zufallszahlen)

Feedback zu STP065

Mole schreibt:

In STP065 vermutest du, dass der Ethernet-Port wegen Authentifizierung abgeschafft wurde. "Beim WLAN muss man sich authentifizieren, beim Ethernet kann man sich einfach anstecken und lossurfen." Das ist so natürlich nicht richtig. Im Enterprise-Umfeld gibt es für sowas 802.1x. Das wird übrigens auch beim WLAN zur Authentifizierung mit einem RADIUS-Server benutzt. Außerdem gibt es da SNMP-Traps. Da schaltet dann der Port ab und der Admin bekommt eine Nachricht, wenn die falsche MAC antwortet. Das gab es schon lange vor WLAN.

Nächstes Problem: Du erklärst, das die NUCs vom VOC für das Streaming zuständig sind. Das ist so auch nicht richtig. Die machen nur das Encoding in die Subformate, wenn der Talk schon geschnitten ist. Für das Streaming sind die Cubes, ordentliche PCs mit extrem teuren Spezial-SDI-Encoding-Karten. Die Kisten brauchen auch echt Leistung, weil die das live machen.

...more

View all episodes

By Xyrillian Noises