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_
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.
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
Irgendeine Funktion, die mit einem Zahlenwert hochkommt, wenn man ihr einen String übergibt. zb
1 | int CalcHash( const char* Text ) |
2 | {
|
3 | return ( Text[0] * 256 + Text[1] ) % HASHTABLE_LEN; |
4 | }
|
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
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.