# Wie funktioniert eine Hashtabelle?



## um94 (28. Juni 2013)

*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


----------



## sheel (28. Juni 2013)

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.


----------



## um94 (28. Juni 2013)

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?


----------



## Jennesta (28. Juni 2013)

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


----------



## um94 (28. Juni 2013)

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?


```
//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");
```


----------



## Der Wolf (28. Juni 2013)

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


```
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


----------



## Jennesta (28. Juni 2013)

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


----------



## deepthroat (28. Juni 2013)

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. ^^


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
> 
> 
> ```
> ...


Für die vglFunktion wäre in dem Fall (für Strings) g_str_equal passend.


----------



## Der Wolf (29. Juni 2013)

deepthroat hat gesagt.:


> Nein, damit sollen nicht die Hashwerte verglichen werden, sondern die Keys deiner Hashtabelle.



Aber die Keys einer Hash-Tabelle sind doch normalerweise "Hash" Werte. Sonst macht die Benennung der Funktion "g_str_hash" auch nicht soviel Sinn, denke ich.

Gruß,
Wolf


----------



## deepthroat (1. Juli 2013)

Der Wolf hat gesagt.:


> Aber die Keys einer Hash-Tabelle sind doch normalerweise "Hash" Werte.


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.


Warum? Diese Funktion berechnet lediglich aus einem String einen Hashwert. Da ist der Name doch ausgesprochen passend.


----------



## Der Wolf (1. Juli 2013)

Hey,

aber die Schlüssel einer Hash-Tabelle sollten ja eindeutig sein. Wenn man also aus den Schlüsseln einen Hash-Wert berechnet um die Schlüssel auf die Eimer aufzuteilen, ist doch implizit der Hash-Wert der eigentliche Schlüssel.


----------



## deepthroat (1. Juli 2013)

Der Wolf hat gesagt.:


> Hey,
> 
> aber die Schlüssel einer Hash-Tabelle sollten ja eindeutig sein.


Ja, die Schlüssel sind eindeutig. Aber nicht die Hashwerte der Schlüssel. Es kann bei Hashfunktionen immer zu Kollisionen kommen. Deswegen muss man auch eine Funktion haben mit der man die Schlüssel direkt vergleichen kann.

Es gilt eben nur die Implikation:

x = y => H(x) = H(y)


Der Wolf hat gesagt.:


> Wenn man also aus den Schlüsseln einen Hash-Wert berechnet um die Schlüssel auf die Eimer aufzuteilen, ist doch implizit der Hash-Wert der eigentliche Schlüssel.


Nein, denn allein mit dem Hashwert kannst du nicht den richtigen Wert finden - er ist nicht eindeutig.


----------



## um94 (3. Juli 2013)

Ich denke langsam habe ich es begriffen, jedoch lasse ich das  Thema offen, da schnell weitere Fragen meinerseits auftauchen können.

Gruss
um94


----------

