Ein Algorithmus hat keinerlei Bezug auf das Betriebssystem und ist auch nicht von irgendeiner Bibliothek abhängig. Der Algorithmus ist nichts anderes als ein Verfahren, dass verwendet wird, um ein Problem zu lösen. Als Verfahren ist der Quellcode gemeint, der etwas bestimmtes tut. C C++ C/C++ Algorithmen Sortieralgorithmen Suchalgorithmen Pattern Matching String Matching Algorithmen Sortieralgorithmen Suchalgorithmen Pattern Matching String Matching Kapitel 25: Algorithmen

25.6. Hashing (Zerhacken)            zurück zum Inhaltsverzeichnis

Hashing ist eine bekannte Methode zum Suchen und Speichern von Datensätzen mithilfe einer Tabelle, bei der ein Schlüssel in eine Tabellenadresse umgewandelt wird. Durch diese Umwandlung kann bei einer Suche sofort auf diese Tabellenadresse gesprungen werden, ohne den vollständigen Datensatz (bei binärer Suche, einen Teil des Datensatzes) zu durchlaufen. Die Ziele beim Hashing sind dabei eine effizientere Nutzung der verfügbaren Speicherkapazität und ein schnellerer Zugriff.

25.6.1 Wann wird Hashing verwendet?
Das beste Beispiel für Hashing sind Symboltabellen, bei denen Werte durch jedes Element mit einer dynamischen Menge von Strings assoziiert werden. So geschieht dies etwa beim Compiler. So kann ein Compiler alle Variablen eines Programms am effizientesten verwalten.

Ein weiteres Beispiel ist die (verräterische) Autovervollständigung des Browsers oder auch der Cache des Webbrowsers, der den Verlauf speichert. Ein simples Beispiel für Hashing ist die Zählung von Wörtern, die in einem Text vorkommen. Abfragen, angewendet auf ein digitales Wörterbuch, können mit Hashing ebenso effizient gestaltet werden wie die Programmierung von großen Datenbanken. Denn in diesen Fällen ist es wirklich geboten, unglaublich viele Daten in kurzer Zeit zu durchsuchen.

25.6.2 Was ist für das Hashing erforderlich?

Die Hash-Funktion wird in der Praxis meist mit einem Array passender Größe angegeben, welches zur Kompilierzeit angelegt wird. Einfach ausgedrückt: Eine Hash-Tabelle mit 10 Elementen ist ein Array mit verketteten Listen - mit der Größe von 10* Arraygröße. In jedem Index dieses Arrays könnte eine verkettete Liste sein. Das soll jetzt in der Praxis untersucht werden.

Hier wird wieder das Postleitzahlen-Beispiel verwendet:

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

Die Hash-Tabelle, die jetzt für die verkettete Liste verwendet wird, sieht wie folgt aus:

struct plz *hash_tabelle[MAX_HASH];

Um es einfach zu halten , wird eine niedrige Arraygröße verwendet:

#define MAX_HASH 10

Hierzu die aktuelle Hash-Tabelle grafisch dargestellt:

Abbildung 25.25: Leere Hash-Tabelle

Abbildung 25.25: Leere Hash-Tabelle

Jetzt benötigen Sie eine Funktion zum Hinzufügen eines neuen 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->postleit == p)
            /*Postleitzahlen gleich?*/
               {
                  printf("%s mit PLZ %d ist bereits "
                         "vorhanden\n",o,p);
                  /*Doppelte Einträge vermeiden*/
                  return pointer;
               }
            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->postleit = p;
   pointer->next = hash_tabelle[hash_adresse];
   hash_tabelle[hash_adresse] = pointer;
   return pointer;
}

Die Funktion wird jetzt Schritt für Schritt erläutert:

int hash_adresse = hash_funktion(o); 

Hiermit bekommt die Variable hash_adresse einen errechneten Hashwert, der logischerweise zwischen 0 und 9 liegen muss, da die Hash-Tabelle 10 Slots besitzt.

Es sei gegeben, dass der Funktion insert() folgende Werte übergeben wurden:

insert("Augsburg",86163); 

Die Hashfunktion errechnet in diesem Beispiel aus dem String "Augsburg" den Wert 6. Somit kommt der String "Augsburg" in den Index (Slot) 6 der Hash-Tabelle. Auf diesen Slot soll jetzt erst ein Zeiger verweisen:

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

Bildlich sieht diese wie folgt aus:

Abbildung 25.26: Zeiger auf errechneten Index

Abbildung 25.26: Zeiger auf errechneten Index

Jetzt muss ein freier Speicherplatz für die neuen Daten gesucht werden:

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

Im ersten Fall ist dies recht trivial. Also kann der neue Datensatz gleich in die Hash-Tabelle eingefügt werden mit:

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

Jetzt befindet sich das erste Element in der Hash-Tabelle, grafisch dargestellt sieht dies dann so aus:

Abbildung 25.27: Erster Datensatz hinzugefügt

Abbildung 25.27: Erster Datensatz hinzugefügt

Nun folgt ein weiterer Datensatz:

insert("Friedberg", 86316); 

Die Hashfunktion, die Ihnen immer noch vorenthalten wurde, errechnet hierbei den Index (Slot) 8. Darauf sieht die Hash-Tabelle nach Abarbeiten der Funktion insert() so aus:

Abbildung 25.28: Einen weiteren Datensatz hinzugefügt

Abbildung 25.28: Einen weiteren Datensatz hinzugefügt

Jetzt zu einem speziellen Fall beim Hashing. Es wird folgender neue Datensatz eingefügt:

insert("Stuttgart", 70190); 
Die Hashfunktion errechnet aus dem String "Stuttgart" den Indexwert 8.
Beim Betrachten der Abbildung 25.38 können Sie erkennen, dass Slot 8 bereits einen Inhalt hat ("Friedberg"). Dies wird Kollision genannt, und es bedeutet, dass die Hash-Funktion zu unterschiedlichen Schlüsseln gleiche Werte liefern kann. Deshalb wurde ja auch eine lineare verkettete Liste verwendet. Somit wird der neue Datensatz einfach hinter "Friedberg" eingefügt. In der Informatik wird dies als Synonymkette bezeichnet.

Abbildung 25.29: Einen Datensatz nach einer Kollision hinzugefügt

Abbildung 25.29: Einen Datensatz nach einer Kollision hinzugefügt

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

Für tatsächlich effektive Hash-Berechnungen existieren drei Methoden:

Divisionsmethode

key = key mod m

Für m sollten Sie idealerweise eine Primzahl so nahe wie möglich am höchsten Index wählen.

Mittquadratmethode

key = I

I ist key, wobei führende und endende Ziffern entfernt werden müssen. Beispielsweise:

H(3206) = 32062 = 10278436 

Von dem Wert 10278436 werden abwechselnd rechts und links die Ziffern abgeschnitten, bis ein Wert entsteht, der kleiner als der Index ist. Wenn z.B. eine Hash-Tabelle mit dem Index 10 deklariert wurde, sieht der Wert aus dem Schlüssel 10278436 wie folgt aus:

1027 [8] 436 = 8 

Zerlegungsmethode
Man zerlegt den Schlüssel, bis er eine gültige Adresse hat. Als Beispiel der Schlüssel 135612:

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

Der Schlüssel wurde zerlegt, bis er als gültige Adresse den Wert 9 besitzt.

Hashing von Strings
Ein bewährter Hash-Algorithmus für Strings erzeugt einen Hashwert, in dem er jedes Byte des Strings zum Vielfachen des Strings hinzuaddiert. Eine Multiplikation verteilt die einzelnen Bits des Bytes auf den bisher berechneten Wert. Tests haben ergeben, dass sich bei Strings die Werte 31 und 37 als gute Multiplikatoren erwiesen haben, die auch für das Programmbeispiel verwendet werden.

Theoretisch könnten Sie sich das Beispiel anhand des Postleitzahlen-Listings so vorstellen. Für String "Stuttgart" wurden die Postleitzahlen 70190 eingetragen:

hash_tabelle["Stuttgart"] = 70190; 

Dies ist eigentlich ein Array mit dem Indexwert als String. In der Praxis ist dies in C natürlich nicht möglich. Dafür schreiben Sie ja auch die Hash-Funktion.

Jetzt die passende Hash-Funktion für das Programmbeispiel:

/* Die Hash-Funktion zur Berechnung des
   Hashwerts 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, dass auch positive Hash-Adressen für die Hash-Tabelle zurückgeliefert werden, wird unsigned verwendet.

Es ist relativ schwierig, eine optimale Hash-Funktion zu finden. In solch einem Fall müssen Sie so lange testen, bis Sie mit dem Ergebnis zufrieden sind. Hierzu das vollständige Programm, welches das Hashing mit getrennter Verkettung demonstrieren soll:

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

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

struct plz *hash_tabelle[MAX_HASH];

struct plz *insert(char *, unsigned int);
void search_in_hash(char *);
int hash_funktion(char *);

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->postleit == p) /*Postleitzahlen 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->postleit = p;
   pointer->next = hash_tabelle[hash_adresse];
   hash_tabelle[hash_adresse] = pointer;
   return pointer;
}

/*Funktion zur Suche in Hash-Tabelle*/
void 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 nachsehen, 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->postleit);
         pointer = pointer->next;
      }
}

/* Die Hash-Funktion zur Berechnung des Hashwerts
   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 ähnlich wie insert(). Daher wird auf eine Erklärung verzichtet. Wichtig ist es aber auch, zu erwähnen (auch wenn dies eigentlich logisch sein sollte), dass jede Funktion, die Sie hinzufügen (suchen, sortieren, löschen, einfügen ...), dieselbe Hash-Funktion verwenden muss.

25.6.4 Hashing mit direkter Adressierung
Es ist auch möglich, die einzelnen Hashes direkt zu adressieren, sofern Sie abschätzen können, wie viele Elemente eingefügt werden. Dafür wird eine Tabelle verwendet, die nur Zeiger auf die anderen Stellen im Speicher abgelegter Datensätze enthält.

Die direkte Adressierung lässt sich folgendermaßen realisieren (Pseudocode):

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 in der größeren Schnelligkeit. Der große Nachteil ist aber die fixe Tabellengröße. Sofern Sie die Menge der Daten abschätzen können, ist diese kein Nachteil. Bei Datenbanken, bei denen die Menge der Daten vom Anwendungsfall abhängt, ist die direkte Adressierung nicht sinnvoll.

25.6.5 Vergleich von Hashing mit binären Bäumen
Vorteile des Hashings:

Vorteile binärer Bäume:

Weiter mit 25.7. Stringmatching            zum Inhaltsverzeichnis