mikrocontroller.net

Forum: PC-Programmierung Hashfunktion


Autor: rain (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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_

Autor: Tom Ekman (tkon)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: rain (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: rain (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
aber was ist denn jetzt die "mathematische Funktion" daran?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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;
}

Autor: Matthias H. (experimentator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.