Erklären Sie das Prinzip der offenen Adressierung bei der Implementierung von assoziativen Containern vom Typ map.

Offene Adressierung ist eine Methode zur Lösung von Kollisionen in Hashtabellen wie map. Beim Hinzufügen eines Schlüssel-Wert-Paares, wenn der berechnete Hash auf eine belegte Zelle zeigt, erfolgt die Suche nach einer freien Zelle innerhalb des Arrays nach einer bestimmten Sequenz (z.B. lineares oder quadratisches Sondieren).

Anstelle von verketteten Listen für Kollisionen (Ketten) speichert die offene Adressierung alle Elemente in einem einzigen Array, wobei benachbarte Positionen sequenziell überprüft werden, bis eine leere gefunden wird.

Beispiel für lineares Sondieren:

// hash - Hashfunktion
// table - Array zur Speicherung der Elemente
// i - Versuchszahl
index := (hash(schlüssel) + i) % len(table)

Dieser Ansatz spart Speicher für Zeiger, erfordert jedoch die Kontrolle der Tabellenbelastung, um eine Verschlechterung der Leistung zu vermeiden.