Junior
Was ist eine Hashtabelle?
sobes.tech KI
Antwort von AI
Eine Hashtabelle ist eine Datenstruktur, die ein assoziatives Array (Wörterbuch) implementiert. Sie speichert Paare aus "Schlüssel-Wert", wobei die Schlüssel eindeutig sind.
Grundprinzipien:
- Hash-Funktion: Wandelt den Schlüssel in eine Zahl um (Hash-Code oder Index). Dieser Index zeigt auf den Speicherort des Wertes im Array (Korb).
- Array (Körbe): Tatsächlicher Speicher für die "Schlüssel-Wert"-Paare.
- Kollisionen: Situation, in der verschiedene Schlüssel denselben Hash-Code erzeugen.
Lösung für Kollisionen:
- Verkettungsmethode (Separate chaining): In jedem Korb befindet sich eine Liste (oder eine andere Datenstruktur) von Elementen mit demselben Hash-Code.
- Offene Adressierung (Open addressing): Bei Kollisionen wird nach einem freien Korb gesucht, wobei verschiedene Strategien verwendet werden (lineares Sondieren, quadratisches Sondieren, doppelte Hashfunktion).
Eigenschaften:
- Schneller Zugriff: Im Idealfall O(1) für Einfüge-, Such- und Löschoperationen.
- Abhängigkeit von der Hash-Funktion: Die Qualität der Hash-Funktion und die Strategie zur Kollisionslösung beeinflussen die Leistung stark.
- Speichernutzung: Erfordert zusätzlichen Speicher für das Array der Körbe.
Verwendung in QA:
- Speicherung von Testdaten (Schlüssel - Parametername, Wert - erwarteter oder tatsächlicher Wert).
- Überprüfung der Einzigartigkeit von Elementen (z.B. Benutzer-ID).
- Implementierung von Caches.