Warum verwenden wir Hash-Code in HashTable anstelle eines Index?

Question

• Wie dieser Integer-Hash von der GetHashCode() - Funktion generiert wird? Ist es ein zufälliger Wert, der nicht einzigartig ist?

• In Zeichenfolge wird es überschrieben, um sicherzustellen, dass nur ein Hash-Code für eine bestimmte Zeichenfolge vorhanden ist. Wie geht das?

• Wie wird die Suche nach einem bestimmten Schlüssel in einer Hash-Tabelle mit Hash-Code beschleunigt?

• Was sind die Vorteile der Verwendung von Hash-Code gegenüber der Verwendung eines Index direkt in der Sammlung (wie in Arrays)?

Kann jemand helfen?

Answer 1

Im Grunde verwenden Hash-Funktionen eine generische Funktion, um Daten zu verdauen und einen Fingerabdruck (und eine ganze Zahl) für diese Daten zu generieren. Im Gegensatz zu einem Index hängt dieser Fingerabdruck NUR von den Daten ab und sollte auf der Grundlage der Daten keine vorhersehbare Reihenfolge aufweisen. Jede Änderung an einem einzelnen Bit der Daten sollte auch den Fingerabdruck erheblich verändern.

Beachten Sie, dass dies nirgendwo garantiert, dass verschiedene Daten nicht den gleichen Hash geben. Im Gegenteil, das passiert sehr oft und wird Kollision genannt. Bei einer ganzen Zahl beträgt die Wahrscheinlichkeit dagegen 1 zu 4 Milliarden (1 in 2^32). Wenn eine Kollision auftritt, vergleichen Sie einfach das tatsächliche Objekt, das Sie hashen, um zu sehen, ob sie übereinstimmen.

Dieser Fingerabdruck kann dann als Index für ein Array (oder eine Arraylist) gespeicherter Werte verwendet werden. Da der Fingerabdruck nur von den Daten abhängig ist, können Sie einen Hash für etwas berechnen und einfach das Array-Element für diesen Hash-Wert überprüfen, um zu sehen, ob es bereits gespeichert wurde. Andernfalls müssten Sie das gesamte Array durchsuchen und prüfen, ob es mit einem Objekt übereinstimmt.

Sie können auch sehr schnell assoziative Arrays verwenden, indem Sie zwei Arrays verwenden, eines mit Key-Werten (indiziert durch Hash) und ein zweites mit Werten, die diesen Schlüsseln zugeordnet sind. Wenn Sie einen Hash verwenden, müssen Sie nur den Hash des Schlüssels kennen, um den passenden Wert für den Schlüssel zu finden. Dies ist viel schneller als eine binäre Suche in einer sortierten Schlüsselliste oder ein Scan des gesamten Arrays, um übereinstimmende Schlüssel zu finden.

Es gibt viele Möglichkeiten, einen Hash zu generieren, und alle von ihnen haben verschiedene Vorzüge, aber nur wenige sind einfach. Ich schlage vor, die Wikipedia-Seite auf Hash-Funktionen für weitere Informationen zu konsultieren.

Answer 2

Ein HashCode ist ein Pseudo-eindeutiger Schlüssel. Wir hätten gerne einen wirklich einzigartigen Schlüssel, aber das ist nicht machbar. Wir vereinbaren eine schnelle und sichere (keine Ausnahmen) Funktion.

A HashTable verwendet den HashCode, um zunächst in O (1) -Zeit nachzusehen. Jedes Indexierungsschema erfordert O (log (n)) Zeit. Aber mit einer ineffizienten HashCode-Funktion kann die Kollisionsverarbeitung die HashTable sehr viel langsamer machen.

In .NET gibt es eine Standardimplementierung für GetHashCode, aber Typen können dies überschreiben.

Die System.String überschreibt GetHashCode(), weil es Equals() überschreibt und GetHashCode dann konsistent gehalten werden muss.

Answer 3

jede Ihrer Fragen zu beantworten direkt:

Wie der Integer-Hash von erzeugt wird, die GetHashCode() Funktion? Ist es ein Zufallswert, der nicht eindeutig ist?

Ein Integer-Hash wird mit der für das Objekt geeigneten Methode generiert. Die Generierungsmethode ist nicht zufällig, sondern muss konsistenten Regeln folgen, um sicherzustellen, dass ein für ein bestimmtes Objekt generierter Hash dem für ein gleichwertiges Objekt generierten Hash entspricht. Als Beispiel würde eine Hash-Funktion für eine ganze Zahl einfach diese ganze Zahl zurückgeben.

In String, wird außer Kraft gesetzt , um sicherzustellen, dass es nur einen Hash Code für eine bestimmte Zeichenfolge vorhanden ist. Wie zu das tun?

Es gibt viele Möglichkeiten, dies zu tun. Hier ist ein Beispiel ich an Ort und Stelle zu denken:

int hash = 0; 
for(int i = 0; i < theString.Length; ++i) 
{ 
    hash ^= theString[i]; 
} 

Dies ist ein gültiger Hash-Algorithmus, weil die gleiche Abfolge von Zeichen immer die gleiche Hash-Zahl erzeugen. Es ist kein guter Hashalgorithmus (ein extremes Understatement), weil viele Strings denselben Hash erzeugen. Ein gültiger Hash-Algorithmus muss die Eindeutigkeit nicht garantieren. Ein guter Hashalgorithmus wird die Wahrscheinlichkeit, dass zwei verschiedene Objekte, die die gleiche Zahl erzeugen, sehr unwahrscheinlich machen.

Wie wird die Suche nach einem bestimmten Schlüssel in einer Hash-Tabelle mit Hash-Code beschleunigt? Was sind die Vorteile der Verwendung von Hash-Code gegenüber der Verwendung eines Index direkt in der Sammlung (wie in Arrays)?

Ein Hash-Code wird normalerweise in Hash-Tabellen verwendet. Eine Hash-Tabelle ist ein Array, aber jeder Eintrag im Array ist ein "Bucket" von Elementen, nicht nur ein Element. Wenn Sie ein Objekt haben, und Sie wollen wissen, welche Eimer es in gehört, berechnen

hash_value MOD hash_table_size. 

Dann einfach das Objekt mit jedem Element in der vergleichen müssen. Daher wird eine Hashtabellensuche höchstwahrscheinlich eine Suchzeit von O (1) haben, im Gegensatz zu O (Protokoll (N)) für eine sortierte Liste oder O (N) für eine unsortierte Liste.

Answer 4

Ein Hash-Code ist ein Index, und eine Hash-Tabelle, auf der untersten Ebene, ist ein Array. Aber für einen gegebenen Schlüsselwert bestimmen wir den Index in einer Hash-Tabelle anders, um einen viel schnelleren Datenabruf zu ermöglichen.

Beispiel: Sie haben 1.000 Wörter und ihre Definitionen. Sie möchten sie speichern, so dass Sie die Definition für ein Wort sehr, sehr schnell abrufen können - schneller als eine binäre Suche, was Sie mit einem Array tun müssten.

Sie erstellen also eine Hash-Tabelle. Sie beginnen mit einem Array, das wesentlich größer als 1.000 Einträge ist - sagen wir 5.000 (je größer, desto zeiteffizienter).

Die Art, wie Sie Ihre Tabelle verwenden, ist, nehmen Sie das Wort nachschlagen, und konvertieren Sie es in eine Zahl zwischen 0 und 4.999. Sie wählen den Algorithmus dafür; das ist der Hashalgorithmus.Aber Sie könnten zweifellos etwas schreiben, das sehr schnell wäre.

Dann verwenden Sie die konvertierte Zahl als Index in Ihr Array mit 5.000 Elementen und fügen Ihre Definition in diesen Index ein. Es gibt überhaupt keine Suche: Sie haben erstellt den Index direkt aus dem Suchwort.

Alle Operationen, die ich beschrieben habe, sind konstante Zeit; keiner von ihnen dauert länger, wenn wir die Anzahl der Einträge erhöhen. Wir müssen nur sicherstellen, dass genügend Platz im Hash vorhanden ist, um die Wahrscheinlichkeit von "Kollisionen" zu minimieren, dh die Wahrscheinlichkeit, dass zwei verschiedene Wörter in denselben Integer-Index konvertiert werden. Da dies bei jedem Hash-Algorithmus passieren kann, müssen wir Prüfungen hinzufügen, um zu sehen, ob es eine Kollision gibt, und etwas Spezielles tun (wenn "Hallo" und "Welt" beide auf 1.234 hashen und "Hallo" bereits in der Tabelle ist) werden wir mit "Welt" tun? Am Einfachsten ist es, es in 1,235 zu setzen, und passen Sie unsere Lookup-Logik, um diese Möglichkeit zu ermöglichen.)

Edit: Nach dem Lesen Ihres Beitrags: ein Hash-Algorithmus ist definitiv nicht zufällig, es muss deterministisch sein. Der Index, der in meinem Beispiel für "Hallo" generiert wird, muss jedes Mal 1.234 sein; Nur so kann die Suche funktionieren.