Hashfunktion

[rain (Gast)]

Hallo ihr:D:D
ich hab die Aufgabe einen Vortrag zu Hashtabellen für meinen Grundkurs 
Informatik auszuarbeiten.
Ich habe mich jetzt erstmal mit dem hashcode beschäftigt und wollte 
fragen ob ich das so richtig verstanden habe:
Also wenn jetzt zB eine Firma ein Register über ihre Mitarbeiter anlegt 
und Anstatt für jeden Namen auf jetzt zB den Registrierkarten nur den 
Anfangsbuchstaben schreibt. Dadruch verringert sich ja dann die Anzahl 
der zu durchsuchenden Karten wenn man nach einem Sucht da man nur nach 
dem ersten Buchstaben des Nachnamens suchen muss. Aber da kommt jetzt 
mein problem, da ja mehrere Mitarbeiter mit dem gleichen Buchstaben im 
nachnamen anfangen.
Ist dies dann die Kollision oder wie müsste man dann damit umgehen?

MFG Rain_

[Tom E. (tkon)]

Ja, das wäre dann eine Kollision.

In der Regel verwendet man aber deutlich komplexere Hashfunktionen mit 
möglichst wenig Kollisionen.
In deinem Fall könnte man aber z.B. einen Hash für das zweite Zeichen 
des Nachnamens verwenden.

[rain (Gast)]

ja daran hatte ich auch gedacht das ich dann bei zB meier me und bei 
schulz sch zu machen da dies die Auswahl schon deutlisch einschrenken 
würde.
Aber danke für deine Antwort also hab ich das mit den hashfunktionen 
jetzt schon mal grundlegend verstanden:D

[rain (Gast)]

aber was ist denn jetzt die "mathematische Funktion" daran?

[Karl H. (kbuchegg)]

Irgendeine Funktion, die mit einem Zahlenwert hochkommt, wenn man ihr 
einen String übergibt.

zb

int CalcHash( const char* Text )
{
  return ( Text[0] * 256 + Text[1] ) % HASHTABLE_LEN;
}

[Matthias H. (experimentator)]

Hallo rain,

der Sinn von Hashing ist allgemein, daß man eine aufwendige lineare 
Suche in größeren Datenmengen vermeiden und einen effizienten 
Arrayzugriff daraus machen kann.

Das mit den Kollisionen ist richtig.

Es gibt zwei gängige Strategien, um damit umzugehen:

Geschlossenes Hashing
Dabei wird ein Array benutzt, in dem die "Zieldaten" stehen. Im Fall von 
Kollisionen kann man z. B. den nächsten freien Eintrag nehmen.
Das bietet sich an, wenn man weiß, wieviele Daten zu erwarten sind (oder 
der Aufwand für dynamisches Anlegen und ggf. Umkopieren in ein neues, 
größeres Array akzeptabel ist).
Faustregel: Das Array sollte nie mehr als 70% gefüllt sein, sonst wird's 
ineffizient.

Offenes Hashing
Dabei ist der Eintrag in der Hashtabelle der Beginn einer Liste oder 
anderen Datenstruktur.
Natürlich wird's auch hier ineffizienter, wenn die Hashtabelle sehr voll 
wird, aber sie kann nicht überlaufen.

Es ist also in jedem Fall nötig, mit Kollisionen zu rechnen und beim 
Suchen  sicherzustellen, daß man den richtigen gefunden hat.

Zu Hashfunktionen und -algorithmen gibt es noch eine ganze Menge zu 
sagen, daher würde ich Dir empfehlen, daß Du mal einen Blick in ein 
Algorithmenbuch wirfst oder im Netz danach suchst - die eine oder andere 
Uni oder Fachhochschule hat mit Sicherheit Skripte und ähnliches im 
Netz, wo das brauchbar drinnenstehen sollte.

Tschüß, Matthias