Ich bin in letzter Zeit einige Male auf diese Begriffe gestoßen, aber ich bin ziemlich verwirrt, wie sie funktionieren und wann sie üblicherweise eingesetzt werden.
Antworten
Zu viele Anzeigen?
Nun, sehen Sie es einmal so.
Wenn Sie ein Array, eine einfache indexbasierte Datenstruktur, verwenden und es mit zufälligen Daten füllen, wird die Suche nach einem bestimmten Eintrag immer kostspieliger, je mehr Daten Sie einfügen, da Sie im Grunde genommen von einem Ende zum anderen suchen müssen, bis Sie den gewünschten Eintrag finden.
Wenn Sie einen schnelleren Zugriff auf die Daten wünschen, sortieren Sie das Array und verwenden eine binäre Suche. Dies beschleunigt zwar die Suche nach einem vorhandenen Wert, macht aber das Einfügen neuer Werte langsam, da Sie vorhandene Elemente verschieben müssen, wenn Sie ein Element in der Mitte einfügen wollen.
Eine Hashtabelle hingegen hat eine zugehörige Funktion, die einen Eintrag nimmt und ihn auf eine Zahl reduziert, einen Hash-Schlüssel. Diese Zahl wird dann als Index für das Array verwendet, in dem Sie den Eintrag speichern.
Eine Hashtabelle dreht sich um ein Array, das anfangs leer ist. Leer bedeutet nicht, dass es keine Länge hat. Das Array hat zu Beginn eine Größe, aber alle Elemente im Array enthalten nichts.
Jedes Element hat zwei Eigenschaften: Daten und einen Schlüssel, der die Daten identifiziert. Eine Liste von Postleitzahlen in den USA wäre beispielsweise eine Assoziation vom Typ Postleitzahl -> Name. Die Funktion reduziert den Schlüssel, berücksichtigt aber nicht die Daten.
Wenn Sie also etwas in die Hashtabelle einfügen, reduziert die Funktion den Schlüssel auf eine Zahl, die als Index in diesem (leeren) Array verwendet wird, in dem Sie die Daten speichern, sowohl den Schlüssel als auch die zugehörigen Daten.
Wenn Sie später einen bestimmten Eintrag suchen, für den Sie den Schlüssel kennen, lassen Sie den Schlüssel durch dieselbe Funktion laufen, erhalten seinen Hash-Schlüssel und gehen zu dieser bestimmten Stelle in der Hashtabelle und rufen die Daten dort ab.
Die Theorie besagt, dass die Funktion, die Ihren Schlüssel auf einen Hash-Schlüssel, diese Zahl, reduziert, rechnerisch viel billiger ist als die lineare Suche.
Eine typische Hashtabelle verfügt nicht über eine unendliche Anzahl von Elementen, die für die Speicherung zur Verfügung stehen, daher wird die Anzahl in der Regel auf einen Index reduziert, der in die Größe des Arrays passt. Eine Möglichkeit, dies zu tun, besteht darin, einfach den Modulus des Indexes im Vergleich zur Größe des Arrays zu nehmen. Bei einem Array mit einer Größe von 10 wird der Index 0-9 direkt auf einen Index abgebildet, und der Index 10-19 wird wieder auf 0-9 abgebildet, und so weiter.
Einige Schlüssel werden auf denselben Index reduziert wie ein vorhandener Eintrag in der Hashtabelle. An diesem Punkt werden die eigentlichen Schlüssel direkt verglichen, mit allen Regeln, die mit dem Vergleich der Datentypen des Schlüssels verbunden sind (z. B. normaler String-Vergleich). Bei einer vollständigen Übereinstimmung werden die neuen Daten entweder ignoriert (sie sind bereits vorhanden), überschrieben (die alten Daten für diesen Schlüssel werden ersetzt) oder hinzugefügt (mehrwertige Hashtabelle). Gibt es keine Übereinstimmung, d. h. die Hash-Schlüssel waren zwar identisch, die tatsächlichen Schlüssel jedoch nicht, wird in der Regel ein neuer Speicherort für den Schlüssel und die Daten gefunden.
Für die Kollisionsauflösung gibt es viele Implementierungen, wobei die einfachste darin besteht, einfach zum nächsten leeren Element im Array zu gehen. Diese einfache Lösung hat jedoch andere Probleme, so dass die Suche nach dem richtigen Auflösungsalgorithmus auch eine gute Übung für Hashtabellen ist.
Hashtabellen können auch wachsen, wenn sie vollständig (oder annähernd) gefüllt sind. Dies geschieht in der Regel durch die Erstellung eines neuen Arrays mit der neuen Größe, die erneute Berechnung aller Indizes und die Platzierung der Elemente in dem neuen Array an ihren neuen Positionen.
Die Funktion, die den Schlüssel auf eine Zahl reduziert, erzeugt keinen linearen Wert, d. h. "AAA" wird zu 1, dann wird "AAB" zu 2, so dass die Hashtabelle nicht nach einem typischen Wert sortiert ist.
Es gibt auch einen guten Wikipedia-Artikel zu diesem Thema, aquí .
Nrj
Punkte
6513
Wenn Sie von Java sprechen, sind beides Sammlungen, die das Hinzufügen, Löschen und Aktualisieren von Objekten erlauben und intern Hasing-Algorithmen verwenden.
Der wesentliche Unterschied besteht jedoch darin, dass Hash-Tabellen von Natur aus synchronisiert und daher thread-sicher sind, während Hash-Maps keine thread-sicheren Sammlungen sind, wenn wir uns auf Java beziehen.
Abgesehen von der Synchronisierung ist der interne Mechanismus zum Speichern und Abrufen von Objekten in beiden Fällen Hashing.
Wenn Sie wissen wollen, wie Hashing funktioniert, empfehle ich Ihnen, ein wenig über Data Structers und Hashing-Techniken zu googeln.
tzot
Punkte
86792
