Diese Website setzt Cookies ein, um das Angebot für Sie zu personalisieren und Ihr Erlebnis zu verbessern.
Weitere Informationen: Datenschutzerklärung & Cookies, Impressum
Eine Hash-Tabelle ist eine Datenstruktur in der Informatik, die zum schnellen Abrufen von Daten verwendet wird. Es handelt sich um eine spezielle Art von assoziativem Array, das einen Schlüsselwert verwendet, um auf den Wert eines Elements zuzugreifen.
Eine Hash-Tabelle besteht aus einem Array, in dem jedes Element einen Schlüssel und einen dazugehörigen Wert enthält. Der Schlüssel wird verwendet, um den Index zu berechnen, an dem das Element im Array gespeichert wird. Dieser Index wird mithilfe einer sogenannten Hash-Funktion berechnet, die den Schlüssel in einen ganzzahligen Wert umwandelt.
Wenn ein neues Element in die Hash-Tabelle eingefügt wird, wird zunächst die Hash-Funktion auf den Schlüssel angewendet, um den Index zu berechnen, an dem das Element im Array gespeichert wird. Wenn an diesem Index bereits ein Element gespeichert ist, das denselben Index hat, wird ein sogenanntes Kollisionsauflösungsverfahren angewendet, um das neue Element an einem anderen Ort im Array zu speichern.
Wenn ein Element aus der Hash-Tabelle abgerufen werden soll, wird die Hash-Funktion erneut auf den Schlüssel angewendet, um den Index zu berechnen, an dem das Element im Array gespeichert ist. Da die Hash-Funktion die Schlüssel auf eindeutige Indizes abbildet, kann das Element in konstanter Zeit abgerufen werden, unabhängig von der Größe der Hash-Tabelle.
Hash-Tabellen werden häufig verwendet, um Datenbanken zu implementieren, als Cache oder als Teil von Algorithmen wie dem Suchalgorithmus oder dem Sortieralgorithmus.