WikiDer > Hashtabelle
EIN Hash-tabelle oder Hash-Karte wie im . verwendet Informatik ist ein Datenstruktur wobei Schlüssel mit Werten verknüpft sind. Es ist eine Implementierung von a assoziatives Array. Dies wird in erster Linie für eine Suchoperation verwendet, bei der man zu einem bestimmten Schlüssel, beispielsweise einem Namen, einen zugehörigen Wert, beispielsweise den Wohnort, wissen möchte.
Hash-Tabellen werden oft für die Implementierung verwendet Konfigurationsdateien.
Die Operation einer Hash-Tabelle basiert auf a Hash-Funktion das wandelt den Schlüssel in a . um Hashwert die verwendet wird, um die (Schlüssel, Wert)-Kombination effizient zu finden. Im Durchschnitt gibt eine Hash-Tabelle den gesuchten Wert in einer konstanten Zeit zurück, O(1), wie bei einem normalen Array aber in Ausnahmefällen kann die Zeit proportional zur Anzahl der Elemente in der Hash-Tabelle sein Auf). Aufgrund der Zeit, die benötigt wird, um den Hash-Wert zu berechnen und schließlich die Kombination zu finden, eignet sich eine Hash-Tabelle am besten für Fälle, in denen eine große Anzahl von Kombinationen verwendet wird.
Die zugrundeliegende Funktion besteht darin, dass die Tasten mit Hilfe von a Hash-Funktion werden in eine halbzufällige Zahl, den Hash-Wert, in einem bestimmten Bereich umgewandelt. Wenn eine Kombination gesucht werden muss, wird dieser Hashwert als Index in einer linearen Tabelle verwendet und überprüft, ob der Wert an der Indexposition mit dem Schlüssel übereinstimmt. Ist dies der Fall, kann der Wert zurückgegeben werden, O(1). Ist dies nicht der Fall, muss geprüft werden, ob nicht versehentlich mehrere Schlüssel mit dem aktuellen Wert vorhanden sind, sodass der Schlüssel nicht im Index sondern an anderer Stelle, z ersten gefundenen Index oder dass der gesuchte Schlüssel überhaupt nicht in der Hash-Tabelle vorhanden ist.
Ein Nachteil einer Hash-Tabelle besteht darin, dass die Schlüssel im Speicher verstreut sind: Nicht verwendete Schlüssel nehmen Platz zwischen den verwendeten Schlüsseln ein. Wenn der Zugriff auf die Schlüssel in einer bestimmten Reihenfolge erforderlich ist, ist dies wahrscheinlich nicht die effizienteste Lösung. In diesem Fall ist zum Beispiel ein ausgewogenes Binärbaum könnte eine bessere Lösung sein.
Hash-Tabellen werden in allen Arten von Programmen verwendet. Die meisten Programmiersprachen bieten in ihren Standardbibliotheken Unterstützung für Hash-Tabellen; C bietet zum Beispiel (ab Version C 11) die Klasse ungeordnete_map an und Java die Klasse HashMap. Die meisten Skriptsprachen Unterstützen Sie Hashtables mit einem speziellen Syntax (beispielsweise perl, Python, PHP und Rubin). In diesen Sprachen werden Hash-Tabellen auch häufig als Datenstrukturen verwendet und ersetzen manchmal Strukturen und Arrays.
Kollisionen
Beim Einfügen von Items in die Hash-Tabelle kann es vorkommen, dass die berechnete Position bereits belegt ist (Kollision oder Kollision). Manchmal kann der alte Wert einfach entfernt werden, zum Beispiel wenn die Hashtable für die Implementierung von a . verwendet wird Zwischenspeicher. Soll der alte Wert nicht gelöscht werden, kann eine der folgenden Methoden gewählt werden: