Wie funktioniert eine Hashtabelle?

U

um94

Grünschnabel
Hallo Forum,

ich versuche zu verstehen wie eine Hashtabelle funktioniert und wie ich diese programmieren kann.
Hat jemand ein Beispiel oder kann mir sagen wie ich eine Hashtabelle erstellen soll?

Von hashtabellen weiss ich aus internetquellen dass es ein indexverzeichnis ist. Eine liste in welcher man sich schneller zurecht findet als in bspw. einer array-list o.ä.

Wäre froh wenn mir jmnd helfe könnte.

Gruss um94
 
Hi und Willkommen bei tutorials.de,

es gibt nicht die "eine" Hashtabelle, aber ein Beispiel:
Du hast ein Array,in dem von allen Einwohnern Deutschlands Nachname, Vorname, Adresse stehen.
Also 80 Mio. Einräge.

Wenn du jetzt von allen "Max Mueller"´s die Adresse wissen willst
musst du alle 80 Mio. Einträge durchsuchen.

Andere Möglichkeit, die Daten zu speichern, wäre zB. 26*26 = 676 Arrays
Eins für AA, AB, AC...AZ, BA, BB, BC...
(die Arrays können wiederum in ein 676 Elemente größes Array zusammengefasst werden)
Die Namen+Adresse teilst du dann so auf die 676 Arrays auf,
dass die ersten zwei Buchstaben vom Name zum Array passen.
Mueller kommt in das für Mu.

Um jetzt die MaxMueller-Adressen zu bekommen muss nur noch das Mu-Array durchsucht werden.
Eins von 676. Im Durchschnitt sollten in jedem der 676 Arrays 118000 Namen stehen.
Nur noch 118000 statt 80000000, die durchsucht werden müssen.
(das Ermitteln, in welchem Array Mueller wohl stehen wird, dauert ja nicht lang. Vernachlässigbar).

Das System, wie Namen auf die Arrays aufgeteilt werden, ist die sog. Hashfunktion.
In dem Fall einfach "Nimm die ersten zwei Buchstaben vom Nachnamen".
Je nach Art der Daten (und was man damit vorhat) kann sich das sehr unterscheiden.


Statt in einzelne Arrays/Listen/... aufteilen gibt es zB. auch Varianten,
wo alles trotzdem in einem einzigen 80Mio-Array ist
und durch die Hashfunktion bestimmt wird, wo ein Name zu suchen/einzufügen ist.
Falls an der Stelle, wo man was einfügen will, schon "voll" ist,
brauchts dann auch ein System, wie/wo stattdessen nach freien Alternativen gesucht wird.


Um beim Aussuchen eines HT-Typs, einer Hashfunktion und/oder Implementierung zu helfen
wären Infos über die Daten und die Verwendung hilfreich.
 
Vielen Dank!
Das war mal eine logische Erklärung.
Ich würde vorschlagen ich beginne mit einfachen Beispielen.

Wie erstelle ich eine Hashtabelle
Wie füge ich Daten hinzu
Wie lösche ich diese erneut
und wie suche in in der Hashtabelle nach eingefügten Daten

Ich möchte Name und Wohnort in meiner Hashtabelle abspeichern mit GLib.
Wie soll ich da vorgehen?
 
Hi,
wie sheel schon sagte ist das A und O bei einer Hastabelle die Größe abzuschätzen. Einerseits möchte man den Zugriff möglichst beschleunigen, andererseits auch nicht viel Speicher verschwenden.

Wenn du jetzt sagen wir 100 Namen+Wohnorte hast, wäre ein 32bit Hashcode bspw. aus einer md5()-Hashfunktion viel zu aufwändig. Da würde zB. eine Funktion die Name+Wohnort nimmt und z.B auf ein Array mit 50 Plätzen aufteilt reichen.
Diese Funktionen können meist einfach sein, wie auch sheel sagte mit Anfansgbuchstaben vom Nachnamen, oder auch komplizierter. Das kommt aber ganz darauf an, wie die Daten gestrickt sind. Weißt du das alle deine Namen zu 90% in einer Stat wohnen, wäre es ungünstig die Stadt für den Hashcode zu nutzen.

Wichtig ist auch, dass die Funktion die Daten ungefähr gleichverteilt aufs Array. Daher ist das finden einer geeigneten Funktion auch meistens das schwierigste bei der Aufgabe.

Grüße
 
Danke, jedoch möchte ich zunächst einige Übungen machen bevor ich die HashTabelle implementiere

Ich möchte als Übung eine Tabelle erstellen in welche ich dann folgende strings einfüllem möchte:
Name, Vorname, Strasse, StrassenNr, Plz, Wohnort

bin ich mit diesem Befehl damit auf dem richtigen Weg?

Code: 
//erstellen einer Hashtabelle
GHashTable* hash = g_hash_table_new(g_str_hash, g_str_hash, g_str_hash, g_str_hash, g_str_hash, g_str_hash);

//Einen Eintrag in die Hashtabelle setzen
g_hash_table_insert(hash, "Daniel", "Mueller", "Musterstrasse", "123", "12345", "Musterort");
 
Hallo,

also ich habe zwar noch nie eine Hash-Tabelle aus der GLib Library verwendet daher sind meine folgenden Aussagen mit Vorsicht zu geniessen. ;) Ich denke aber nicht, dass du da auf dem richtigen Weg bist.

Wie gesagt, besteht eine Hash-Tabelle immer aus einem Key-Value Pair. Was du bei dem "g_hash_table_new" als Parameter angibst, sind die Funktions-Pointer. Die erste Funktion wird wohl verwendet um aus deinem Schlüssel einen Unisgned Integer basierten - Hash-Wert zu berechnen. Die Funktion "g_str_hash()" wird dir dabei von der GLib zur Verfügung gestellt und kann benutzt werden um aus einem String den entsprechenden Integer-Schlüssel zu berechnen, der dann intern von der GLib-Hash-Tabelle benutzt wird.

Als zweiten Parameter erwartet "g_hash_table_new" eine Funktion mit der 2 Werte (ich denke mal die Hash-Werte) auf Gleichheit geprüft werden können. Wobei ich gerade nicht sicher bin warum da eine extra Funktion benötigt wird, wenn die Schlüssel eh in guint umgewandelt werden. ^^

Long Story short: Ich denke dein Aufruf müsste eher

C: 
GHashTable *hash = g_hash_table_new(g_str_hash, <vglFunktion>);

lauten. Und für deinen Eintrag in die Tabelle musst du dir noch überlegen was du als Schlüssel verwendest und wie du die restlichen Werte (Name, Vorname, Strasse, ...) als einzelnen String verpackst und in die Tabelle einfügst.

Ich hoffe es hilft einigermaßen obwohl ich nicht denke, dass ich das gut erklärt habe.

Gruß,
Wolf
 
Hi,

ich habe leider auch noch nicht GLib benutzt, daher kann ich dir kein Beispiel nennen. Aber ich bin mir nach deinem letzten Post unsicher, ob du weißt wie eine Hashtabelle prinzipiell aufgebaut ist.
Du darfst das nicht mit einer typischen MxN Tabelle im Matrix-Stil verwechseln.

Hashtabellen sind meist der Struktur Array[Datenstruct] bzw. Array[list<Datenstruct>]
Wobei der Hashwert den deine Hashfunktion berechnet den Index des Arrays liefert und das Datum dort hinzugefügt wird. Dabei gibt es mehrere Varianten wie man bei Kollisionen verfährt, entweder Ausweich-Index nach Schema suchen oder aber zweite Variante oben nutzen und an der Liste anhängen. Dabei können auch u.U mehrere Arrays genutzt werden, wie sheel es angedautet hat. Die Implementierung hängt stark von Anzahl Werten und Zugriffszeit ab.

Grüße,
Jennesta
 
Der Wolf hat gesagt.:
Als zweiten Parameter erwartet "g_hash_table_new" eine Funktion mit der 2 Werte (ich denke mal die Hash-Werte) auf Gleichheit geprüft werden können. Wobei ich gerade nicht sicher bin warum da eine extra Funktion benötigt wird, wenn die Schlüssel eh in guint umgewandelt werden. ^^
Zum Vergrößern anklicken....
Nein, damit sollen nicht die Hashwerte verglichen werden, sondern die Keys deiner Hashtabelle.

Wie schon beschrieben werden die Einträge in verschiedene "Eimer" verteilt. Wenn man dann einen bestimmten Wert anhand eines Schlüssels sucht, muss man in dem passenden Eimer trotzdem noch schauen, ob der gesuchte Schlüssel auch gleich einem der Schlüssel aus dem Eimer ist; Stichwort: Hash Kollision.

Der Wolf hat gesagt.:
Long Story short: Ich denke dein Aufruf müsste eher

C: 
GHashTable *hash = g_hash_table_new(g_str_hash, <vglFunktion>);
Zum Vergrößern anklicken....
Für die vglFunktion wäre in dem Fall (für Strings) g_str_equal passend.
 
Der Wolf hat gesagt.:
Aber die Keys einer Hash-Tabelle sind doch normalerweise "Hash" Werte.
Zum Vergrößern anklicken....
Nein. Die Hashes werden nur für die Aufteilung der Schlüssel auf die Eimer verwendet.

Die Schlüssel sind deine fachlichen "Objekte" die du auf andere "Objekte" abbilden möchtest.

Um sheels Beispiel aufzugreifen: wenn man Namen zu Adressen zuordnen möchte, dann sind die Namen die Schlüssel und die Adressen die Werte.
Der Wolf hat gesagt.:
Sonst macht die Benennung der Funktion "g_str_hash" auch nicht soviel Sinn, denke ich.
Zum Vergrößern anklicken....
Warum? Diese Funktion berechnet lediglich aus einem String einen Hashwert. Da ist der Name doch ausgesprochen passend.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück