Was ist der Unterschied zwischen einem Array und einer Hash-Tabelle in einer Programmiersprache?


Antwort 1:

Hash-Tabellen verwenden Arrays. Arrays haben eine wichtige Eigenschaft für das Hashing: Sie können in konstanter Zeit auf jedes Element zugreifen, wenn Sie dessen Index kennen.

Sie können Arrays für Buckets verwenden. Angenommen, Sie möchten, dass Sie zählen, wie viele Buchstaben in einem Text enthalten sind, um beispielsweise etwas wie Morsecode zu entwerfen. Sie erstellen ein Array mit 26 Einträgen (für das einfache römische Alphabet ohne Akzent). Immer wenn Sie einen Buchstaben sehen, berechnen Sie den Index und gehen zu diesem Eintrag im Array.

Hash-Tabellen erweitern dies für beliebig lange Schlüssel. Sie berechnen einen Hash des Schlüssels und gehen zu diesem Index. Das Problem ist, wenn mehrere Schlüssel denselben Hash haben. Es gibt verschiedene Möglichkeiten, damit umzugehen, von denen einige den Zweck des Hashs zunichte machen (aber einfach zu implementieren sind). Einige von ihnen behalten die Eigenschaft der konstanten Zeit zumindest im Durchschnitt nicht bei.

Das Beste, was ich gesehen habe, ist das Add-the-Hash-Rehash, bei dem Gonnet und Munroe nachweislich im Durchschnitt etwas mehr als 4 Zugriffe mit einem Auslastungsfaktor von 50% hatten, unabhängig von der Größe des Hash-tabelle. Dies erfordert jedoch die Verwendung von Primzahlen, und dies macht die Implementierung schwierig. Man muss die Primzahlen irgendwie finden. Glücklicherweise werden Hash-Tabellen nicht so groß, dass dies lächerlich wird.