ein Kapitel zurück                                           ein Kapitel weiter

Es exvisitstieren viele gute Dokumentationen zum Thema Hashing. Leider sind viele dieser Informationen, sowohl Literatur als auch das World Wide Web, recht komplex dargestellt. Mein Versuch ist es nun Ihnen Hashing etwas Näher zu bringen ohne zu sehr in Fachbegriffe zu fallen.

Was ist Hashing?

Hashing in der Informatik hat eine andere Bedeutung als im realen Leben ;)
Hashing ist eine Methode mit der wir Datensätze, anhand einer Tabelle, durchsuchen indem wir einen Schlüssel in eine Tabellenadresse umwandeln.

Durch diese Umwandlung können wir bei einer Suche sofort auf diese Tabellenadresse springen, ohne den kompletten Datensatz (oder bei binärer Suche, einen Teil des Datensatzes) zu Durchlaufen.

Ziele sind eine effiziente Nutzung der verfügbaren Speicherkapazität und ein schneller Zugriff.

Wo wird Hashing verwendet?

Das beste Beispiel für Hashing dürften wohl Symbol-Tabellen sein, wo Werte durch jedem Element mit einer dynamischen Menge von Strings assoziert werden. So geschieht dies bei Ihrem Compiler zum Beispiel. Oder wie denken sie kann ein Compiler alle Variablen eines Programms am effizientersten verwalten?

Ein weiteres Beispiel dürfte die (veräterische) Autovervollständigung Ihres Browsers sein. Oder auch der Cache Ihres Webbrowsers die den Verlauf speichert. Ein simples Beispiel für Hashing wäre es die Häufigkeit von Wörtern zu zählen. Ein Englisch-Deutsch Wörterbuch dürfte sich auch sehr effizient mit Hashing lösen lassen. Die Hauptanwendung von Hashing dürfte wohl aber in der Programmierung von großen Datenbanken liegen. Denn in diesem Fall trifft es wohl am ehesten zu unglaublich viel Daten in effizienter Zeit zu durchsuchen.

In Perl zum Beispiel gehören Hash sowieso zur Grundlage. Und wer den Vorteil hat, ein wenig Perl zu können, dem dürfte dies Kapitel sowieso nicht allzu schwer fallen.

Was benötigt man für das Hashing?

  • Hash-Funktion - Mit der Hashfunktion wird der Platz (Adresse) in der Hash-Tabelle berechnet.
  • Hash-Tabelle - In der Hash-Tabelle befinden sich die eindeutigen Adressen die im Falle einer Suche sofort "angesprungen" werden. Die Suchanfrage wird natürlich wiederum zuvor mit der Hashfunktion in eine Tabellen-Adresse bezeichnet.

Wir benötige also für das Hashing nur eine Funktion und eine Tabelle. Diese beiden Elemente wollen wir jetzt natürlich etwas genauer durchleuchten.

Die Hasfunktion geben wir in der Praxis an, meist mit einem Array passender Größe welches wir zur Kompilierzeit Mitanlegen.
Einfach ausgedrückt, eine Hashtabelle mit 10 Elementen ist ein Array mit verketteter Listen, mit der Größe von 10*Arraygröße. In jedem Index diese Arrays könnte praktisch eine verkettete Liste sein. Wir wollen das ganze erst mal etwas praktischer sehen. Sie werde verblüfft sein wie einfach dieses Prinzip ist.

Unser Postleitzahlen-Beispiel....... 

struct plz{
            char ort[MAX];
            unsigned int plz;
            struct plz *next;
          };

Unsere Hash-Tabelle die wir nun für die verkettete Liste verwenden sieht wie folgt aus.... 

struct plz *hash_tabelle[MAX_HASH];

Um es mir leichter zu machen, Ihnen diese Thematik besser zu Erklären, verwenden wir eine recht geringe Arraygröße..... 

#define MAX_HASH 10

Hier unsere Hash-Tabelle bildlich........




Nun benötigen wir eine Funktion zum Hinzufügen eines neuem Datensatzes im Hash..... 

struct plz *insert(char *o, unsigned int p)
{
 struct plz *pointer;
 /*Hashwert (bucket) an hash_adresse (0-9)*/
 int hash_adresse = hash_funktion(o);

 /*printf("%d\n",hash_adresse);*/

 /*Zeiger auf errechnete Tabellenadresse durch hash_funktion*/
 pointer = hash_tabelle[hash_adresse];
 /*Wir suchen freien Platz für einen neuen Eintrag in hash_tabelle[hash_adresse]*/
 while(pointer != NULL)
  {
    if(strcmp(o, pointer->ort) == 0)  /*Stadt gleich?*/
     if(pointer->plz == p)    /*Postleitzahlen auf gleich?*/
      {
        printf("%s mit PLZ %d ist bereits vorhanden\n",o,p);
        return pointer; /*Doppelte Einträge vermeiden*/
      }
    pointer=pointer->next;
  }

 /*Speicher für neues Element allokieren*/
 pointer = (struct plz *)malloc(sizeof(struct plz));
 if(pointer == NULL)
  {
    fprintf(stderr, "Konnte keinen Speicher für neue PLZ reservieren\n");
    return NULL;
  }
 strcpy(pointer->ort, o);
 pointer->plz = p;
 pointer->next = hash_tabelle[hash_adresse];
 hash_tabelle[hash_adresse] = pointer;

 return pointer;
}

Wir wollen jetzt mal diese Funktion Schritt für Schritt erläutern..... 

int hash_adresse = hash_funktion(o);

Hiermit bekommt die Variable hash_adresse einen errechneten Hashwert, der logischerweise zwischen 0 und 9 liegen muss, da unsere Hash-Tabelle ja nur 10 Slots besitzt. Diese Funktion sehen wir uns danach an. Wir gehen nun mal davon aus, dass unserer Funktion insert folgende Werte übergeben wurden..... 

insert("Augsburg",86163);

Unsere Hash-Funktion errechnet uns in diesem Beispiel aus dem String "Augsburg" den Wert 6. Somit kommt der String "Augsburg" in den Index (Slot) 6 der Hash-Tabelle. Darauf wollen wir nun einen Zeiger zeigen lassen mit...... 

 /*Zeiger auf errechnete Tabellenadresse durch hash_funktion*/
 pointer = hash_tabelle[hash_adresse];

Bildlich sieht diese wie folgt aus........




Als nächsten Schritt wollen wir einen freien Speicherplatz für unsere neuen Daten suchen....... 

 while(pointer != NULL)
  {
    if(strcmp(o, pointer->ort) == 0)  /*Stadt gleich?*/
     if(pointer->plz == p)    /*Postleitzahlen auf gleich?*/
      {
        printf("%s mit PLZ %d ist bereits vorhanden\n",o,p);
        return pointer; /*Doppelte Einträge vermeiden*/
      }
    pointer=pointer->next;
  }

....was im ersten Fall recht trival ist. Also können wir unseren neuen Datensatz gleich in die Hash_Tabelle einfügen........ 

 strcpy(pointer->ort, o);
 pointer->plz = p;
 pointer->next = hash_tabelle[hash_adresse];
 hash_tabelle[hash_adresse] = pointer;

Nun ist unser erstes Element in der Hash-Tabelle was man sich bildlich wie folgt vorstellen kann....




Nun wollen wir folgenden neuen Datensatz einfügen...... 

insert("Friedberg", 86316);

Unsere Hash-Funktion, die ich Ihnen immer noch vorenthalten will, errechnet hierbei den Index (Slot) 8 Somit sieht unsere Hash_Tabelle nach abarbeiten der Funktion insert wie folgt aus....




Jetzt wollen wir uns eine speziellen Fall ansehen, der Ihnen wahrscheinlich schon durch die Gedanken geschossen ist. Nun wird folgender neue Datensatz eingefügt..... 

insert("Stuttgart", 71234);

Unsere Hash-Funktion errechnet aus dem String "Stuttgart" nun den Indexwert (slot) 8. Wenn sie unser Bild nun oben sehen, können sie erkenne das Slot 8 ja bereits einen Inhalt hat ("Friedberg"). Wir haben hier also eine sogenannte Kollision. Dies bedeutet unsere Hash-Funktion, kann zu Unterschiedlichen Schlüsseln gleiche Werte liefern. Dafür haben wir aber eine lineare verkettete Liste eingebaut. Nun wird also der neuen Datensatz einfache hinter "Friedberg" eingefügt.......




Hash-Funktion

Anhand dieses Beispiels, dürfte wohl klar sein das der Hash-Funktion eine entscheidende Rolle zufällt. Wie sie eine solche Funktion schreiben, bleibt Ihnen überlassen. Sie könnten sogar hergehen unter eine Funktion schreiben, die Zufallszahlen zwischen 0 und 9 zurückliefert. Doch was bringt eine solche Funktion wenn 90% der Zufallszahlen zum Beispiel zwischen 2-4 liegen. Die restlichen Slots werden dabei kaum verwendet.

Wir wollen hier 3 Arten von effektiven Hash-Funktionen ansprechen.....

  • Divisionsmethode
  • Mittquadratmethode
  • Zerlegungsmethode

Divisionsmehtode 

key = key mod m

Für m wählt man Idealerweise eine Primzahl so nahe wie möglich am höchsten Index.

Mittquadratmethode 

key=I

l ist key2 , wobei führende und endende Ziffern entfernt werden müssen. Beispielsweise..... 

H(3206) = 32062 = 10278436

Von dem Wert 10278436 werden jetzt abwechselnd, rechts und links die Ziffern abgeschnitten, bis wir einen Wert erhalten der kleiner als der Index ist. Wenn wir Beispielsweise eine Hash-Tabelle mit dem Index 10 haben sieht unser Wert wie folgt aus..... 

 1027 [8] 436 = 8

Zerlegungsmethode
Wir zerlegen den Schlüssel, bis er eine gültige Adresse hat. Beispielsweise wir haben den Schlüssel..... 

135612 = [13]+[56]+[12]= 81 = [8]+[1] = 9

...zerlegt bis er als gültige Adresse den Wert 9 besitzt.

Hashing von Strings

Ein bewährter Hashalgorithmus für Strings erzeugt einen Hashwert, in dem er jedes Byte des Strings zum Vielfachen des Strings hinzuaddiert. Eine Multiplikation verteilt diese einzelnen Bits des Bytes auf den bisher berechneten Wert. Tests haben ergeben das sich bei Strings die Werte 31 und 37 als gute Multiplikator erwiesen haben, welche wir auch für unser Programmbeispiel verwenden wollen.

Hierzu nun unser passende Hash-Funktion für unser Programm........ 

/*Die Hash-Funktion zur Berechnung des Hashwertes eines Strings*/
int hash_funktion(char *string)
{
 unsigned int hash_adresse;
 unsigned char *pointer;

 hash_adresse=0;
 pointer = (unsigned char *)string;

 while(*pointer != '\0')
  {
    hash_adresse = M * hash_adresse + *pointer;
    pointer++;
  }
 return hash_adresse % MAX_HASH;
}

Zur Sicherstellung, das auch positive Hash-Adressen für die Hash-Tabelle zurückgeliefert werden, verwenden wir hier unsigned.

Es ist relativ schwer eine optimal Hash-Funktion zu finden. In solch einem Fall muss man Testen bis man mit dem Ergebnis zufrieden ist. Hierzu nun ein komplettes Programm was das Hashing mit getrennter Verkettung demonstrieren soll........ 

/*Download:hash.c*/

#include <stdio.h>
#include <stdlib.h>
#define MAX_HASH 10
#define M 31

struct plz{
            char ort[255];
            unsigned int plz;
            struct plz *next;
          };

struct plz *hash_tabelle[MAX_HASH];


struct plz *insert(char *o, unsigned int p)
{
 struct plz *pointer;
 /*Hashwert (bucket) an hash_adresse (0-9)*/
 int hash_adresse = hash_funktion(o);

 /*printf("%d\n",hash_adresse);*/

 /*Zeiger auf errechnete Tabellenadresse durch hash_funktion*/
 pointer = hash_tabelle[hash_adresse];
 /*Wir suchen freien Platz für einen neuen Eintrag in hash_tabelle[hash_adresse]*/
 while(pointer != NULL)
  {
    if(strcmp(o, pointer->ort) == 0)  /*Stadt gleich?*/
     if(pointer->plz == p)    /*Postleitzahlen auf gleich?*/
      {
        printf("%s mit PLZ %d ist bereits vorhanden\n",o,p);
        return pointer; /*Doppelte Einträge vermeiden*/
      }
    pointer=pointer->next;
  }

 /*Speicher für neues Element allokieren*/
 pointer = (struct plz *)malloc(sizeof(struct plz));
 if(pointer == NULL)
  {
    fprintf(stderr, "Konnte keinen Speicher für neue PLZ reservieren\n");
    return NULL;
  }
 strcpy(pointer->ort, o);
 pointer->plz = p;
 pointer->next = hash_tabelle[hash_adresse];
 hash_tabelle[hash_adresse] = pointer;

 return pointer;
}

/*Funktion zur Suche in Hash-Tabelle*/
struct plz *search_in_hash(char *o)
{
  struct plz *pointer;
 /*Hashwert (bucket) an hash_adresse (0-9)*/
 int hash_adresse = hash_funktion(o);

 /*printf("%d\n",hash_adresse);*/

 /*Zeiger auf errechnete Tabellenadresse durch hash_funktion*/
 pointer = hash_tabelle[hash_adresse];

 /*Jetzt wollen wir schauen ob es für o einen Eintrag in der Tabelle gibt*/
 while(pointer != NULL)
  {
   if(strcmp(pointer->ort, o) == 0)
     printf("PLZ für %s ist %d\n",o,pointer->plz);
   pointer = pointer->next;
  }
}



/*Die Hash-Funktion zur Berechnung des Hashwertes eines Strings*/
int hash_funktion(char *string)
{
 unsigned int hash_adresse;
 unsigned char *pointer;

 hash_adresse=0;
 pointer = (unsigned char *)string;

 while(*pointer != '\0')
  {
    hash_adresse = M * hash_adresse + *pointer;
    pointer++;
  }
 return hash_adresse % MAX_HASH;
}



int main()
{
  insert("Friedberg", 86316);
  insert("Augsburg", 86136);
  insert("Stuttgart", 71345);

  search_in_hash("Augsburg");
  search_in_hash("Friedberg");
  search_in_hash("Stuttgart");

  return 0;
}

Die Suchfunktion search_in_hash ist ja ähnlich wie insert. Daher erspare ich mir die Erklärungen.

Wichtig ist es aber auch zu erwähnen (auch wenn dies eigentlich logisch sein sollte), jede Funktion die sie einbauen (suchen, löschen, einfügen....), muß die selbe Hash_Funktion verwenden.

Hashing mit direkter Addressierung

Es ist aber auch möglich, die einzelnen Hashes direkt zu Adressieren, sofern wir Abschätzen könne wieviel Elemente wir einfügen werden.

Die direkte Adressierung läuft folgendermaßen ab...... 

while(Schlüssel_stimmt_nicht_überein)
 {
  if(Schlüssel_stimmt_überein){
    printf("gefunden");
    return;
   }
  else if(Speicherplatz leer){
    printf("nicht gefunden");
    return;
   }
  weiter_an_die_nächste_Position;
 }

Der Vorteil der direkten Adressierung liegt daran das die Suche schneller vorangehen kann. Der große Nachteil ist aber die fixe Tabellengröße. Sofern man die Menge der Daten abschätzen kann ist diese kein Nachteil. Bei Datenbanken aber, wo die Menge der Daten vom Kunden abhängt ist die direkte Adressierung nicht sinnvoll. Dazu will ich aber jetzt nicht mehr näher eingehen.

Vergleich von Hashing zu Binären Bäumen

Vorteile vom Hashing:

  • einfach zu Implementieren
  • schnelle Suchergebnisse

Vorteile von Binären Bäumen:

  • Garantie für Leistungsfähigkeit auch ungünstigstem Fall
  • unterstützt viele weitere Operationen (z.B. sortieren)
  • dynamisch (im Vergleich zu Hashing ist bei binären Bäumen keine Info über Anzahl der Einfügungen nötig)

Tipps zur Steigerung der Performance

Dazu kann ich Ihnen 3 gute Tipps geben.....

  • Steigerung der Tabellengröße
  • Vermeidung von Kollisionen mit linearer Verkettung anstatt direkter Adressierung
  • Testen und Proben an der Hash-Funktion (eventuell eine andere Hashfunktion testen)

Über weitere Tipps und Hinweise bezüglich des Hashing würde ich mich sehr freuen.

ein Kapitel zurück          nach oben           ein Kapitel weiter


© 2001,2002 Jürgen Wolf