Algorithmen und Datenstrukturen in C/ Hashtabelle

Hashtabellen sind geordnete Listen, die nicht aus einem Indexwert, sondern dessen Streuwert (engl. hashvalue) bestehen. Ein Streuwert soll Werte einer Eingabedatenmenge möglichst ideal auf eine Zieldatenmenge abbilden. Ein einfaches Beispiel:

Die Eingabedatenmenge sind die drei Vornamen: M:=[ "ADAM ", "BERT ", "CHRIS " ]. Wenn man weiß, dass dies die einzigen drei Eingabemöglichkeiten sind, kann man schnell eine Datenmenge finden, die die Eingabemenge besser abbildet: H:=[0,1,2]. Für den Datenstrom S:="ADAM BERT BERT ADAM CHRIS " kann man also äquivalent schreiben: "01102". Einfach einzusehen, dass die äquivalente Form weniger Platz wegnimmt. Toll wäre jetzt eine Funktion, die diese Transformation vornimmt. Für unser triviales Beispiel haben wir jetzt ein Programm, das den Eingabestring bei jedem Leerzeichen schneidet. Aus S wird dann S1:="ADAM ", S2:= "BERT ", S3:="BERT ",S4:="ADAM ", S5:="CHRIS ". Jetzt fehlt noch eine Funktion, mit der man die Menge H überführt. Die Triviallösung wäre jetzt, dass man die Eingabewerte S1 bis S5 mit jedem Wert von M vergleicht. Die gefundene Position wäre dann der Hashwert.

char* M [] = { "ADAM ","BERT ","CHRIS " };

int hash_funktion_trivial ( char* a_Str ) {

  int i       = 0;
  int iRetVal = 0;
  while ( i < 3 ) {
    if ( strcmp ( a_Str, M [ i ] ) == 0 ) {
      iRetVal = i;
      i       = 3; // ENDE
    } else {
      i++;
    }
  }

  return ( iRetVal );
}

In unserem Trivialbeispiel gibt es eine elegantere und vor allem effizientere Möglichkeit, den Hashwert zu ermitteln:

int hash_funktion ( char* a_Str ) {

  return ( a_Str [0] - 65 );
}

Schon bei diesem Trivialbeispiel wird klar, dass die echte Hashfunktion unter Umständen mehrdeutig sein kann, wenn die Eingabe mehrdeutig wäre: "BRITTA " hätte auch den Hashwert 1.

Hashfunktionen charakterisieren eine Eingabemenge. Wichtig zu wissen ist, dass aus dem Hashwert die Originaldaten nicht wieder gewonnen werden können. Für Hashfunktionen gibt es verschiedene Anwendungen:

  - Sicherstellen, dass eine Nachricht nicht verändert wurde (Secure hashes).
  - 

Hashtabellen werden immer dort eingesetzt, wo Eingabemöglichkeiten auf ein iche mögliche eingabewenn man aus einem begrenzten Eingabevorrat eine

Der Sinn einer Hashtabelle ist es aus einer begrenzten Eingabemenge, weitestgehend zu reduzieren.