Was sind Hashtabellen und Hashmaps und ihre typischen Anwendungsfälle?

Question

Ich bin in letzter Zeit einige Male auf diese Begriffe gestoßen, aber ich bin ziemlich verwirrt, wie sie funktionieren und wann sie normalerweise implementiert werden?

Answer 1

Nun, denken Sie an es auf diese Weise.

Wenn Sie einen Array verwenden, eine einfache Index-basierte Datenstruktur, und füllen Sie es mit random stuff up, einen bestimmten Eintrag zu finden, wird ein teurer Betrieb sein, wie Sie es mit Daten füllen, da Sie im Grunde genommen haben Start von einem Ende zum anderen suchen, bis Sie das gewünschte finden.

Wenn Sie einen schnelleren Zugriff auf Daten erhalten möchten, typicall Sie greifen das Array zu sortieren und mit einer binären Suche. Dies ist jedoch während der Geschwindigkeit zu erhöhen, einen vorhandenen Wert aufzublicken macht neue Werte langsam eingeführt wird, wie Sie benötigen um vorhandene Elemente zu bewegen, wenn Sie ein Element in der Mitte eingelegt werden muss.

A Hashtable, auf der anderen Seite, hat eine zugeordnete Funktion, die einen Eintrag erfolgt, und reduziert sie auf eine Zahl, ein Hash-Key. Diese Zahl wird dann als Index in das Array verwendet wird, und das ist, wo Sie den Eintrag speichern.

Eine Hash-Tabelle dreht sich um eine Anordnung, die zunächst leer beginnt. Leer bedeutet nicht, die Länge Null, beginnt das Array mit einer Größe, aber alle Elemente im Array enthält nichts.

Jedes Element hat zwei Eigenschaften, die Daten und einen Schlüssel, der die Daten identifiziert. Zum Beispiel wäre eine Liste der Postleitzahlen der USA eine Zip-Code -> Name Art der Assoziation. Die Funktion reduziert den Schlüssel, aber die Daten nicht in Betracht ziehen.

So

, wenn man etwas in die Hash-Tabelle einfügen, reduziert die Funktion den Schlüssel zu einer Zahl, die als Index in diesen Abschnitt (Leer) Array verwendet wird, und das ist, wo Sie die Daten speichern, die beide die Schlüssel und die zugehörigen Daten.

Dann später, mögen Sie einen bestimmten Eintrag finden, dass Sie den Schlüssel für kennen, so dass Sie den Schlüssel durch die gleiche Funktion ausführen, erhalten ihren Hash-Schlüssel und gehen an diesem besonderen Ort in der Hash-Tabelle und rufen die Daten es.

Die Theorie besagt, dass die Funktion, die Ihren Schlüssel zu einem Hash-Schlüssel reduziert, diese Zahl ist rechnerisch viel billiger als die lineare Suche.

Eine typische Hashtable nicht eine unendliche Anzahl von Elementen zur Verfügung steht für die Lagerung, so dass die Anzahl der Regel auf einen Index weiter nach unten reduziert wird, die in die Größe des Arrays entspricht. Eine Möglichkeit, dies zu tun ist, nehmen Sie einfach den Modul des Index im Vergleich zur Größe des Arrays. Für ein Array mit einer Größe von 10, Index 0-9 wird direkt auf einen Index abzubilden, und den Index 10-19 wird Karte bis auf 0-9 wieder, und so weiter.

Einige Tasten werden in der Hash-Tabelle auf den gleichen Index wie ein vorhandener Eintrag reduziert werden. An diesem Punkt werden die tatsächlichen Tasten direkt miteinander verglichen, wobei alle Regeln im Zusammenhang mit Vergleich der Datentypen des Schlüssels (dh. Normaler String-Vergleich zum Beispiel). Wenn es eine vollständige Übereinstimmung ist, entweder Sie die neuen Daten außer Acht lassen (es ist bereits vorhanden) oder Sie überschreiben (Sie können die alten Daten für diesen Schlüssel ersetzen) oder Sie es (mehrwertig hashtable) hinzuzufügen. Wenn es keine Übereinstimmung gibt, was bedeutet, dass, obwohl der Hash-Schlüssel identisch war, wurden die eigentlichen Schlüssel nicht, Sie in der Regel einen neuen Standort finden in diesen Schlüssel + Daten zu speichern.

Kollisionsauflösung hat viele Implementierungen, und die einfachste ist, einfach in der Anordnung in die nächste leere Element zu gehen. Diese einfache Lösung obwohl andere Probleme hat, so die richtige Auflösung Algorithmus zu finden, ist auch eine gute Übung für Hash-Tabellen.

Hashtables kann auch wachsen, wenn sie vollständig ausfüllen (oder in der Nähe), und dies in der Regel durch die Schaffung einer neuen Reihe der neuen Größe getan, und die Berechnung alle Indizes noch einmal, und die Elemente in das neue Array platzieren in ihren neuen Standorten.

Die Funktion, die der Schlüssel zu einer Anzahl reduziert keinen linearen Wert erzeugen, das heißt. „AAA“ 1 wird, dann „AAB“ wird 2, so dass die Hash-Tabelle wird von jedem typischen Wert nicht sortiert.

Es gibt einen guten Wikipedia-Artikel zur Verfügung zu diesem Thema auch, hier .

Answer 2

Die Antwort von Lassevk ist sehr gut, enthält aber möglicherweise etwas zu viele Details.Hier ist die Zusammenfassung.Ich bin bestimmte relevante Elemente absichtlich weggelassen Informationen, die Sie in 99 % der Fälle getrost ignorieren können.

Es gibt kein wichtiger Unterschied zwischen Hash-Tabellen und Hash-Maps in 99 % der Fälle.

Hash-Tabellen sind magisch

Ernsthaft.Es ist eine magische Datenstruktur, die alles andere als garantiert drei Dinge.(Es gibt Ausnahmen.Sie können sie weitgehend ignorieren, obwohl es für Sie nützlich sein könnte, sie eines Tages zu lernen.)

1) Alles in der Hash-Tabelle ist Teil eines Paares – es gibt ein Schlüssel und ein Wert.Sie geben Daten ein und aus, indem Sie den Schlüssel angeben, mit dem Sie arbeiten.

2) Wenn Sie etwas mit einem einzelnen Schlüssel in einer Hash-Tabelle tun, ist dies der Fall rasend schnell.Das impliziert das put(key,value), get(key), contains(key), Und remove(key) sind alle sehr schnell.

3) Generische Hash-Tabellen es nicht schafft, etwas zu tun, was nicht in Nr. 2 aufgeführt ist!(Mit „scheitern“ meinen wir, dass sie unglaublich langsam sind.)

Wann verwenden wir Hashtabellen?

Wir verwenden Hash-Tabellen wenn ihre Magie zu unserem Problem passt.

Zum Beispiel, Caching Am Ende wird häufig eine Hash-Tabelle verwendet. Nehmen wir beispielsweise an, wir haben 45.000 Studenten an einer Universität und ein Prozess muss die Aufzeichnungen für alle von ihnen aufbewahren.Wenn Sie den Schüler regelmäßig anhand seiner ID-Nummer bezeichnen, dann a ID => student Cache macht absolut Sinn.Der Vorgang, den Sie für diesen Cache optimieren, ist schnelle Suche.

Hashes sind auch außerordentlich nützlich für Speichern von Beziehungen zwischen Daten wenn Sie nicht aufs Ganze gehen und die Objekte selbst verändern möchten.Beispielsweise könnte es bei der Kursanmeldung sinnvoll sein, den Studierenden eine Zuordnung zu den Kursen zu ermöglichen, an denen sie teilnehmen.Aus irgendeinem Grund möchten Sie jedoch möglicherweise nicht, dass das Student-Objekt selbst davon erfährt.Benutze einen studentToClassRegistration Hash und behalten Sie es bei sich, während Sie tun, was auch immer Sie tun müssen.

Sie machen auch eine ziemlich gute erste Wahl für eine Datenstruktur außer wenn Sie einen der folgenden Schritte ausführen müssen:

Wann man Hash-Tabellen nicht verwenden sollte

Iterieren Sie über die Elemente.Hash-Tabellen eignen sich normalerweise nicht besonders gut für die Iteration.(Allgemeine, das heißt.Bestimmte Implementierungen enthalten manchmal verknüpfte Listen, die dazu dienen, das Durchlaufen dieser Listen zu vereinfachen.Beispielsweise in Java, LinkedHashMap ermöglicht Ihnen eine schnelle Iteration über Schlüssel oder Werte.)

Sortierung. Wenn Sie nicht iterieren können, ist das Sortieren ebenfalls eine echte Qual.

Vom Wert zum Schlüssel.Verwenden zwei Hash-Tabellen.Vertrauen Sie mir, ich habe Ihnen gerade viel Schmerz erspart.

Answer 3

Wenn Sie in Bezug auf Java sprechen, sind sowohl die Sammlungen erlauben Objekte Hinzufügen, Löschen und updation und Verwendung Häsing Algorithmen intern.

Der wesentliche Unterschied jedoch, wenn wir in Bezug auf Java sprechen ist, dass Hash-Tabellen von Natur aus synchronisiert sind und damit Thread-sicher sind, während die Hash-Karten nicht sicher Sammlung Thread werden.

Neben der Synchronisation der internen Mechanismus zu speichern und Objekte abzurufen ist Hashing in beiden Fällen.

Wenn Sie sehen möchten, wie Hashing arbeitet, würde ich ein wenig googeln auf Daten Structers und Hashing-Techniken empfehlen.

Answer 4

Hashtables / Hashmaps einen Wert zuzuordnen (so genannten ‚Schlüssel‘ für Begriffsklärung Zwecke) mit einem anderen Wert. Sie können sie als Art eines Lexikons denken (Wort: Definition) oder einem Datenbankeintrag. (Schlüssel: Daten)