Die Grundlagen der Hash-Tabellen?
https://stackoverflow.com/questions/282712
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin ganz verwirrt über die grundlegenden Konzepte einer Hash-Tabelle. Wenn ich einen Hash codieren waren wie würde ich auch nur ansatzweise? Was ist der Unterschied zwischen einer Hash-Tabelle und nur ein normales Array?
Im Grunde genommen, wenn jemand diese Frage beantwortet denke ich, alle meine Fragen würden beantwortet: Wenn ich 100 zufällig generierten Zahlen hatte (als Schlüssel), wie würde ich eine Hash-Tabelle implementieren und warum sollte das über ein Array von Vorteil sein?
Psuedo-Code oder Java würde als Lerninstrument verstanden werden ...
Lösung
Die Antworten bisher haben dazu beigetragen, Hash-Tabellen zu definieren und eine Theorie zu erklären, aber ich denke, ein Beispiel können Ihnen helfen, ein besseres Gefühl für sie zu erhalten.
Was ist der Unterschied zwischen einer Hash-Tabelle und nur ein normales Array?
Eine Hash-Tabelle und eine Reihe sind beide Strukturen, die Sie speichern und Abrufen von Daten ermöglichen. Beide können Sie einen Index angeben und einen Wert damit verbundenen abzurufen. Die Differenz, wie Daniel Spiewak erwähnt, ist, dass die Indizes eines Arrays sind sequenziellen , während jene einer Hash-Tabelle auf der Basis der Wert der Daten mit ihnen verbunden sind.
Warum sollte ich verwenden, um eine Hash-Tabelle?
Eine Hash-Tabelle kann eine sehr effiziente Art und Weise zur Verfügung stellt für Elemente in großen Mengen von Daten zu suchen, insbesondere Daten, die sonst nicht leicht gefunden werden kann. ( "Large" bedeutet hier ginormous , in dem Sinne, dass es würde eine lange Zeit, um eine sequentielle Suche durchzuführen).
Wenn ich einen Hash codieren waren wie würde ich sogar anfangen?
Kein Problem. Der einfachste Weg ist, eine beliebige mathematische Operation zu erfinden, die Sie auf den Daten durchführen können, die eine Reihe N zurückgibt (in der Regel eine ganze Zahl). Dann nutzen Sie diese Nummer als Index in ein Array von „Eimer“ und speichern Sie Ihre Daten in Eimer #N. Der Trick ist, eine Operation bei der Auswahl, die Werte zu setzen in verschiedenen Eimern in einer Art und Weise neigt, die es einfach macht für sie später zu finden.
Beispiel: Ein großes Einkaufszentrum hält eine Datenbank von seinen Gönnern die Autos und Parkstandorte, um Käufer zu helfen sich zu erinnern, wo sie geparkt. Die Datenbank speichert make, color, license plate und parking location. Beim Verlassen findet den Laden ein Käufer sein Auto durch die seine Marke und Farbe eingeben. Die Datenbank liefert eine (relativ kurze) Liste der Nummernschilder und Parkplätze. Ein schneller Scan sucht die Käufer des Autos.
Sie können dies mit einer SQL-Abfrage implementieren:
SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"
Wenn die Daten in einem Array gespeichert wurden, die im Wesentlichen nur eine Liste ist, können Sie die Abfrage vorstellen Implementierung durch das Scannen eines Arrays für alle passenden Einträge.
Auf der anderen Seite, stellen Sie sich eine Hash-Regel:
Fügen Sie die ASCII-Zeichencodes aller Buchstaben in der Marke und Farbe, Division durch 100, und den Rest als der Hash-Wert verwendet werden.
Diese Regel wird jedes Element auf eine Zahl zwischen 0 und 99 konvertieren, im wesentlichen Sortierung die Daten in 100 Eimer. Jedes Mal, wenn ein Kunde ein Auto lokalisieren muss, können Sie die Marke und Farbe hash die ein Eimer von 100 zu finden, die die Informationen enthält. Sie haben reduziert sofort die Suche um den Faktor 100!
Nun das Beispiel große Datenmengen skalieren, sagt eine Datenbank mit Millionen von Einträgen, die auf Basis von Zehn Kriterien gesucht wird. Eine „gute“ Hash-Funktion werden die Daten in Eimern in einer Art und Weise verteilen, dass jede zusätzliche Such minimiert, eine erhebliche Menge an Zeit zu sparen.
Andere Tipps
Als erstes müssen Sie ein verstehen, was eine Hash-Funktion ist. Eine Hash-Funktion ist eine Funktion, die einen Schlüssel (beispielsweise eine Reihe von arbiträrer Länge) hat und gibt eine Zahl so einzigartig wie möglich . Der gleiche Schlüssel muss immer den gleichen Hash zurück. Eine wirklich einfache String-Hashing-Funktion in Java aussehen könnte
public int stringHash(String s) {
int h = s.length();
for(char c : s.toCharArray()) {
h ^= c;
}
return h;
}
Sie können eine gute Hash-Funktion studieren unter http://www.azillionmonkeys.com/qed/ hash.html
Nun wird die Hash-Karte verwendet diesen Hash-Wert den Wert in ein Array zu platzieren. Simplistic Java-Methode:
public void put(String key, Object val) {
int hash = stringHash(s) % array.length;
if(array[hash] == null) {
array[hash] = new LinkedList<Entry<String, Object> >();
}
for(Entry e : array[hash]) {
if(e.key.equals(key)){
e.value = val;
return;
}
}
array[hash].add(new Entry<String, Object>(key, val));
}
(Diese Karte erzwingt eindeutigen Schlüssel. Nicht alle Karten tun.)
Es ist möglich, zwei verschiedene Schlüssel auf den gleichen Wert Hash oder zwei unterschiedliche Hashes mit dem gleichen Array-Index abzubilden. Es gibt viele Techniken für den Umgang mit diesem. Die einfachste ist eine verknüpfte Liste (oder binären Baum) für jeden Array-Index zu verwenden. Wenn die Hash-Funktion gut genug ist, werden Sie nie eine lineare Suche benötigen.
Jetzt einen Schlüssel suchen:
public Object get(String key) {
int hash = stringHash(key) % array.length;
if(array[hash] != null) {
for(Entry e : array[hash]) {
if(e.key.equals(key))
return e.value;
}
}
return null;
}
Hashtables sind assoziative . Das ist ein großer Unterschied von Arrays, die nur lineare Datenstrukturen sind. Mit einer Reihe, können Sie etwas tun:
int[] arr = ...
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i] + 1);
}
Beachten Sie, wie Sie ein Element aus dem Array werden immer durch einen exakten Speicher Angabe Offset (i). Dies kontrastiert mit Hash-Tabellen, die Sie Schlüssel / Wert-Paare speichern erlauben, später den Wert auf dem Schlüssel basierend Abrufen:
Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);
Mit der obigen Tabelle können wir den folgenden Aufruf machen:
int n = table.get("Chris");
... und sicher sein, dass n wird bei 18 bewertet werden.
Ich denke, das wahrscheinlich die meisten Ihrer Fragen beantworten. Die Implementierung einer Hash-Tabelle ist ein ziemlich interessantes Thema, ein der Wikipedia-Adressen leidlich .
„Ich bin mehr daran interessiert, wie Hash Tables den Schlüssel suchen und, wie der Schlüssel erzeugt wird.“
-
Hashing wandelt ein Schlüsselobjekt in eine Zahl. Dies wird als „Hashing“ genannt - es macht einen Hash aus dem Objekt. Siehe Hash-Funktion . Summieren der Zeichen einer Zeichenkette, beispielsweise ist eine Standard-Hash-Technik. Sie berechnen die Summe Modulo 2 32 den Hash auf eine überschaubare Größe zu halten. Hash gibt immer die gleiche Antwort. Dies ist O (1).
-
Die Zahl gibt Ihnen einen "Schlitz" in der HashTable. Gegeben ein beliebige Schlüsselobjekt berechnet der Hash-Wert einen Hash-Wert. Der Hash-Wert gibt Ihnen dann den Schlitz in der Tabelle. Normalerweise
mod( hash, table size ). Dies ist O (1), auch.
Das ist die allgemeine Lösung. Zwei numerische Berechnungen und Sie haben von beliebigem Objekt als Schlüssel für beliebiges Objekt als Wert weg. Nur wenige Dinge können so schnell sein.
Die Transformation von Objekt zu Hashwert geschieht in einer dieser gemeinsamen Art und Weise.
-
Wenn es ein "primitives" Objekt von 4 Bytes ist, dann wird das nativen Wert des Objekts ist eine Zahl.
-
Die Adresse des Objekts ist 4 Byte, dann ist die Adresse des Objektes als ein Hash-Wert verwendet werden.
-
Eine einfache Hashfunktion (MD5, SHA1, was auch immer) akkumuliert die Bytes die Aufgabe, eine 4-Byte-Zahl zu erzeugen. Die erweiterten Hashes sind nicht einfache Summen von Bytes, eine einfache Summe der alle Bits ursprünglichen Eingangs nicht reflektiert ziemlich genug.
Der Schlitz in der Hash-Tabelle ist mod (Anzahl, die Größe der Tabelle).
Wenn das Schlitz den gewünschten Wert hat, sind Sie fertig. Wenn das nicht der gewünschte Wert, müssen Sie woanders suchen. Es gibt mehrere populäre Sondierung Algorithmen für eine freie Stelle in der Tabelle zu suchen. Linear ist eine einfache Suche nach dem nächsten freien Platz. Quadratic ist ein nichtlineares Hopping um für einen freien Steckplatz suchen. Ein Zufallszahlengenerator (mit einem festen Samen) verwendet werden, kann eine Reihe von Sonden zu erzeugen, die Daten gleichmäßig verteilt werden, sondern willkürlich.
Die Sondierung Algorithmen sind nicht O (1). Wenn die Tabelle ist groß genug, sind die Chancen der Kollision niedrig und Sonden sind nicht wichtig. Wenn die Tabelle zu klein ist, dann Kollisionen passieren und Sondierung passiert. An diesem Punkt wird es eine Frage des „Tuning und Tweaking“ Sondierung und Tabellengröße zu balancieren Leistung zu optimieren. Normalerweise haben wir nur die Tabelle größer machen.
Siehe Hash Table .
Etwas, das ich nicht speziell sah bemerkt noch:
Der Punkt, eine Hash-Tabelle über eine Anordnung zu verwenden, ist die Leistung.
Iterieren durch ein Array typischerweise von O überall würde (1) bis O (x), wobei x die Anzahl der Elemente in dem Array ist. Doch zu der Zeit, um Ihre Artikel extrem werden finden Variable , expecially, wenn wir über Hunderttausende von Elementen im Array sprechen.
Eine richtig gewichtete Hash-Tabelle hat in der Regel eine fast Konstante Zugriffszeit von knapp über O (1), egal wie viele Artikel sind in der Hash-Tabelle.
Sie würden nicht eine Hash-Tabelle für 100 zufällig generierten Zahlen verwendet werden sollen.
Eine gute Möglichkeit, um Hash-Tabellen zu denken ist über Wertepaare zu denken. Lassen Sie uns Studenten verwenden und sagen jeder eine Matrikelnummer hat. In Ihrem Programm speichern Sie Informationen über Studenten (Namen, Telefonnummern, Rechnungen, etc.). Sie möchten alle Informationen über einen Schüler finden, mit nur grundlegende Informationen (Name oder Studentenausweis, zum Beispiel).
Angenommen, Sie haben 10.000 Studenten. Wenn Sie sie alle in einem Array speichern, dann müssen Sie eine Schleife durch das gesamte Array Vergleich der einzelnen Schüler-IDs Eintrag mit dem für Sie suchen.
Wenn Sie stattdessen „hash“ (siehe unten), um ihre Matrikelnummer auf eine Position im Array, dann haben Sie nur Schüler, die die Nummern suchen den gleichen Hash haben. Viel weniger Arbeit zu finden, was Sie wollten.
In diesem Beispiel lassen Sie uns sagen, Studentenausweise sind nur 6-stellige Zahlen. Unsere Hash-Funktion nur die unteren drei Ziffern der Nummer als „Raute-Taste“ verwenden werden könnte. So wird 232145 an Matrixlokation gehasht 145. So dann nur ein Array von 999 Elemente benötigt (jedes Element eine Liste von Studenten zu sein).
Das sollte ein guter Start für Sie sein. Sie sollen natürlich, ein Textbuch oder wikipedia für diese Art von Informationen lesen. Aber ich nehme an, Sie haben bereits getan, und sind des Lesens müde.
Hier ist, kurz gesagt, wie eine Hash-Tabelle funktioniert.
Stellen Sie sich eine Bibliothek voller Bücher. Wenn Sie die Bücher in einem Array zu speichern, würden Sie jedes Buch auf einem Fleck auf einem Regal, und dann, wenn jemand Sie gebeten, ein Buch zu finden, würden Sie alle Regale schauen durch - ziemlich langsam. Wenn jemand sagt, „Buch # 12345“, könnte man es ziemlich leicht zu finden, though.
Lassen Sie uns sagen, anstatt Sie sagen, wenn der Buchtitel mit ‚A‘ beginnt, geht es in der Zeile 1. Wenn der zweite Buchstabe ist ‚B‘, geht es in Zeile 1, Rack 2. Wenn der dritte Buchstabe ist ‚C ‘, es geht in Reihe 1, Rack 2, Regal 3 ... und so weiter, bis Sie das Buch Position identifizieren. Dann wird basierend auf dem Titel des Buchs, könnten Sie genau wissen, wo es sein sollte.
Nun, es gibt einige Probleme in der simplen „Hashing“ Algorithmus I beschrieben - einige Regale werden werden Art und Weise überlastet, während andere leer stehen, werden einige Bücher auf den gleichen Steckplatz zugewiesen werden .. so die eigentlichen Hash-Funktionen sind sorgfältig zu versuchen, so konstruiert, um Probleme zu vermeiden.
Aber das ist die Grundidee.
Ich werde diesen Teil über den Unterschied zwischen einer Hash-Tabelle beantworten und einer Reihe ... aber da habe ich noch nie einen Hashing-Algorithmus jeden Import implementiert, ich werde, dass mehr Wissen an jemandem verlassen:)
Ein Array ist nur eine geordnete Liste von Objekten. Das Objekt selbst ist nicht wirklich wichtig ... was wichtig ist, ist, dass, wenn Sie die Objekte in der Reihenfolge der Einfügung auflisten mögen, es ist immer das gleiche (was bedeutet, dass das erste Element immer hat einen Index von 0).
Wie für eine Hash-Tabelle, die von Schlüsseln indiziert ist, nicht, um ... Ich denke, dass eine grundlegende Suchalgorithmen auf Hashing werden Sie viel mehr Einblick als ich ... Wikipedia einen sehr anständiges hat ... dass bestimmt „Eimer“, dass die Tasten für den schnellen Abruf gehen in auf beliebige Objekte als Schlüssel verwendet.
Was Vorteil: Wenn die Reihenfolge der Einfügung wichtig ist, ein Array oder eine Art geordnete Liste erforderlich. Wenn schnelle Nachschau durch beliebige Taste (verkeilt durch verschiedene Hash-Funktionen) wichtig ist, dann eine Hash-Tabelle macht Sinn.
[Dies ist die Antwort auf eine Bemerkung von me.yahoo.com/a oben]
Das hängt von Ihrer Hash-Funktion. Lets nehme an, dass Ihre Hash-Funktion ein Wort nach der Länge Ihres Wort-Hashes, wird der Schlüssel für chris 5. In ähnlicher sein, Schlüssel für Yahoo auch 5. Nun wird, werden beide Werte (chris und Yahoo) unter 5 gehen (dh in einem ‚Eimer‘ verkeilte von 5). Auf diese Weise müssen Sie nicht ein Array der Größe Ihrer Daten gleich machen.
Die Frage, glaube ich, ist ganz eindeutig zu beantworten und auf vielen verschiedenen Arten von jetzt.
Ich möchte nur eine andere Perspektive hinzuzufügen (die auch einen neuen Leser verwirren)
in einer Menge von mindestens Abstraktion, Arrays sind nur zusammenhängender Speicherblock. Angesichts der Startadresse (startAddress), Größe (sizeOfElement) und der index eines einzelnen Elements, die Adresse des Elements wird berechnet als:
elementAddress = startAddress + sizeOfElement * index
Das Interessante hierbei ist, dass Arrays können als Hash-Tabellen mit index als Schlüssel und der obigen Funktion als Hash-Funktion, die die Position eines Wertes in O (1)
Hash-Tabelle ist eine Datenstruktur, die für eine schnelle Look erstellt wird.
Die Hash-Tabellen sind nicht wirksam, wenn die Anzahl der Einträge sehr klein sind.
Einige Beispiele:
import java.util.Collection;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Set;
public class HashtableDemo {
public static void main(String args[]) {
// Creating Hashtable for example
Hashtable companies = new Hashtable();
// Java Hashtable example to put object into Hashtable
// put(key, value) is used to insert object into map
companies.put("Google", "United States");
companies.put("Nokia", "Finland");
companies.put("Sony", "Japan");
// Java Hashtable example to get Object from Hashtable
// get(key) method is used to retrieve Objects from Hashtable
companies.get("Google");
// Hashtable containsKey Example
// Use containsKey(Object) method to check if an Object exits as key in
// hashtable
System.out.println("Does hashtable contains Google as key: "+companies.containsKey("Google"));
// Hashtable containsValue Example
// just like containsKey(), containsValue returns true if hashtable
// contains specified object as value
System.out.println("Does hashtable contains Japan as value: "+companies.containsValue("Japan"));
// Hashtable enumeration Example
// hashtabl.elements() return enumeration of all hashtable values
Enumeration enumeration = companies.elements();
while (enumeration.hasMoreElements()) {
System.out.println("hashtable values: "+enumeration.nextElement());
}
// How to check if Hashtable is empty in Java
// use isEmpty method of hashtable to check emptiness of hashtable in
// Java
System.out.println("Is companies hashtable empty: "+companies.isEmpty());
// How to find size of Hashtable in Java
// use hashtable.size() method to find size of hashtable in Java
System.out.println("Size of hashtable in Java: " + companies.size());
// How to get all values form hashtable in Java
// you can use keySet() method to get a Set of all the keys of hashtable
// in Java
Set hashtableKeys = companies.keySet();
// you can also get enumeration of all keys by using method keys()
Enumeration hashtableKeysEnum = companies.keys();
// How to get all keys from hashtable in Java
// There are two ways to get all values form hashtalbe first by using
// Enumeration and second getting values ad Collection
Enumeration hashtableValuesEnum = companies.elements();
Collection hashtableValues = companies.values();
// Hashtable clear example
// by using clear() we can reuse an existing hashtable, it clears all
// mappings.
companies.clear();
}
}
Ausgabe:
Does hashtable contains Google as key: true
Does hashtable contains Japan as value: true
hashtable values: Finland
hashtable values: United States
hashtable values: Japan
Is companies hashtable empty: false
Size of hashtable in Java: 3
