Die Implementierung einer hash-Tabelle

Ich begann zu Lesen über die Umsetzung der verschiedenen Daten-Strukturen, die ein paar Tage zurück, und gekommen, um zu hash-Tabellen und steckten fest auf einen bestimmten Punkt.

Meinem Verständnis, wie eine hash-Tabelle implementiert ist:
Ein Schlüssel K ist an eine hash-Funktion H gibt, die eine verschlüsselte version von K, HK. HK sollte wohl mindestens ein uint32_t berücksichtigen, Kollisionen, wir haben ein array der Größe X, die das Element gespeichert wird, auf den index HK dieses array.. aber wäre das nicht verlangen, eine pre-allokiert array der Länge uint32_t atleast (oder was auch immer der return-Wert von H ist)? unter der Annahme, dass wir nicht die Daten gespeichert, die sich innerhalb des Arrays, und stattdessen store einen ptr auf die Daten, dann würden wir benötigen ein array von ptr_t der Länge uint32_t.. das scheint ziemlich verschwenderisch, auf 64bit würde das bedeuten, dass die Speicherauslastung von:
2^32 * 8 = 34359738368 Byte oder ~32GB nur für die Reihe von ptrs zu den Daten, die offensichtlich nicht, wie Ihr tatsächlich in die Praxis umgesetzt..

So was bin ich?

  • Ich denke, die typische Umsetzung ist nicht mit einem array, sondern eine verknüpfte Liste.
  • Ich denke, die typische Implementierung ist nicht mit einer verknüpften Liste sondern ein array.
  • Über Kollisionen, bei Verwendung einer Hashtabelle, wird es collsions. Sollten Sie behandelt werden, nicht vermieden. Sie können minimiert werden durch anständiges hashing und dimension.
  • tatsächlich, Sie verwenden ein array von verknüpften Listen für die run-of-the-mill Umsetzung. Es ist nicht optimal, im Falle von Kollision und hat eine schlechte Lokalität der Referenz (zwischen den Elementen), aber die Komplexität der Vorgänge ist ziemlich vorhersehbar.
  • Nun ja, das war ein missunderstanding, ich dachte, er Sprach über die zweite Stufe.
InformationsquelleAutor Kim Sun-wu | 2012-01-20
  1. 4

    Es hängt von der Umsetzung. Es gibt drei grundlegende Möglichkeiten, wie Sie dies tun können:

    1) Kleiner-hashes verwendet werden. Anstatt also mit einer 32-bit-hash, sagen wir, eine 8-bit-hash verwendet wird.

    2) Mehrere Ebenen von hashing verwendet werden. So zum Beispiel ein 12-bit-hash kann bestimmen, welche "Eimer" einen Eintrag in das geht, aber eine Kollision tritt nur auf, wenn die vollen 32-bit-hash-übereinstimmungen. Jeder Gruppe werden in eine verkettete Liste oder eine ähnliche Struktur. (Vielleicht eine optimale Version für die Suche nach der vollen 32-bit-hash innerhalb es.)

    3) Sparse arrays verwendet werden. Diese sind Datenstrukturen, die nicht brauchen, zu speichern Leerzeichen für nicht gefüllte slots. (In der Praxis, es könnte etwas ganz anderes sein wie ein Baum, aber es wirkt wie ein sparse-array mit einer effizienten Suche.)

    InformationsquelleAutor David Schwartz
  2. 2

    Sollten Sie bauen Ihre hash-Tabelle, so dass es erweitert werden kann. Es gibt einige Methoden, das zu tun. Lesen diese wird es hilfreich sein. In diesem Beispiel wird eine verknüpfte Liste verwendet wird. Und Sie müssen auch die Erweiterung Ihrer Tabelle, wenn es keine leeren Werte mehr. Sie erhalten Folgendes problem: wenn verlängern Sie Ihre Karte, Ihre H-Funktion zurückgeben kann neue HK-Werte für die alten K-Tasten. So müssen Sie denken, wie dieses Problem zu lösen. Eine der Methoden ist, um neu zu laden, alle Werte, wenn die Tabelle erweitert wurde. Ist es normal, wenn Sie es verlängern, aber nicht oft.

    • Hash table oder hash map ist eine Datenstruktur, die verwendet eine hash-Funktion, um anzeigen zu identifizieren Werte, bekannt als Tasten, um die zugehörigen Werte. Es gibt Schlüssel und hash-Werte in Ihrem hash-Tabelle. Sie brauchen nur zu zählen neue Werte für die alten Schlüssel. Wenn Sie noch keine Schlüssel (ich.e es gibt nur einen Satz von hash-Werten) warum brauchen Sie es überhaupt?
    • Ich Rede hash-sets, aber Matthieu M beantwortet die Frage.
    InformationsquelleAutor shift66
  3. 2

    Realistisch, Sie haben eine Reihe von einigen kleineren, festen Betrag, der Eimer, die entweder chaining (Ergebnis in einer verknüpften Liste) oder Sondierung (schlechtestes Beispiel: wenn hash(x) aufgenommen wird, versuchen hash(x)+1) auf Kollisionen. Sie nehmen Ihren, uint32 und mod von der bucket-Größe, der einfachste Fall.

    Definieren Sie einen load-Faktor - sobald man auf N% der array voll ist, werden wir, sagen wir mal, verdoppeln Sie die Größe des Arrays, und sofort wieder alles in das neue array. Lasst uns sagen, irgendwo zwischen 50% und 75% Auslastung.

    Gut, ist nicht teuer, sagen Sie? Naja, nicht wirklich. Sagen wir, verdoppeln Sie die Größe des array jedes mal. So fügen Sie N Elemente, von denen die Letzte Auslöser für eine Kopie. N fügt in O(1), und dann ein O(N) kopieren. Aber warten Sie - O(N) /N im Durchschnitt auf O(1), also den fortgeführten durchschnittlichen Kosten der Zugabe ist immer noch O(1) - vorausgesetzt, Ihre Auslastung ist klug gewählt,.

    • Im Falle der re-hashing, was passiert, wenn ein hash-set, ich.e, Sie nicht über die original-Daten zur Verfügung zu re-hash?
    • Sie können einfach speichern Sie die hash-neben den Daten zu vermeiden, re-computing.
    • Die Speicherung der vollständige 32-bit-hash kann ein Gültiger Optimierung für den Zugriff, auch wenn Sie nicht erweitern Sie die Tabelle, vergleichen Sie die 32-bit-hash-Werte vor der überprüfung auf Gleichheit.
    • richtig! Hätte ich auch nicht gedacht (aber dann, ich nie wirklich implementiert eine hash-Tabelle selbst...)
    InformationsquelleAutor James
  4. 1

    Die typische Implementierung von hash-Tabellen ein array von verknüpften Listen. Die verkettete Liste kann leicht ausgetauscht für ein weiteres datastructure, so nennen wir es ein Bucket von nun an.

    Die Idee ist einfach:

    class HashTable {
public:


private:
  std::vector<Bucket*> _array;
};

    Dann nehmen Sie HK und reduzieren es, um es zu passen in die Reihe, in der Regel mit einer modulo: HK % size(_array) gibt den index der Eimer verwendet werden.

    InformationsquelleAutor Matthieu M.
Schreibe einen Kommentar