7. Wahl einer geeigneten Hash-Funktion

7.2.1. Knuth's Algorithmus

Die in Knuth's "The Art of Computer Programming" (Volume 3 "Sorting and Searching", Kapitel 6.4) vorgestelle Hash-Funktion ist vielleicht eine der bekanntesten überhaupt. Dennoch ist ihre Verteilung nur mittelmäßig. Darüber hinaus verwendet Knuth eine Modulo Operation (mit einer Primzahl) zur Beschränkung auf ein Intervall, welches ihre Performance mindert und wegen der verwendeten Primzahl ein automatisches Vergrößern der Hashtabelle komplizierter macht.

    unsigned long 
    knuth_hash(unsigned char *str, int len) 
    {
      unsigned long hash; 
    
      for (hash=len; len--;) 
      {
        hash = ((hash<<5)^(hash>>27))^*str++;
      }
      return hash;     // % prime
    }
            

7.2.2. Kernigham und Ritchies Algorithmus

Kernigham und Ritchies Algorithmus ist eine einfache additive Hash-Funktion, die jedoch ungeeignet ist für seriöse Anwendungen.

    unsigned long
    k_r(unsigned char *str)
    {
      unsigned long hash = 0;
      int c;
    
      while (c = *str++)
        hash += c;
                      
      return hash;
    } 
            

7.2.3. D.J. Bernsteins Algorithmus

    unsigned long
    djb2(unsigned char *str)
    {
      unsigned long hash = 5381;
      int c;
    
      while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    
      return hash;
    }
            

7.2.4. SDBM Algorithmus

Dieser Algorithmus wird in Sleepycat's Datenbank BDB (Berkeley DataBase) verwendet.

    unsigned long
    sdbm(unsigned char *str)
    {
      unsigned long hash = 0;
      int c;
    
      while (c = *str++)
        hash = c + (hash << 6) + (hash << 16) - hash;
    
      return hash;
    }
            

7.2.5. P.J. Weinberg Algorithmus

    unsigned long 
    hashpjw(unsigned char* str)
    {
      unsigned long hash=0;
      unsigned long g;
    
      for(;*str;++str) 
      {
        hash = (hash << 4)+ *str;
        if(g=hash&0xf0000000) 
        {
          hash ^= g>>24;
          hash ^= g;
        }
      }
    
      return hash;
    }
            

7.2.6. OCaml's Algorithmus

Dieser Algorithmus wird in der aktuellen Version (3.04) von Objective Caml verwendet.

    unsigned long
    ocaml_hash(unsigned char *str, int len) 
    {
      unsigned long hash = 0;
      int i;
    
      for (i=0; i<len; i++) {
        hash = hash*19 + str[i];
      }
    
      return hash;
    }
            

7.2.7. SML's Algorithmus

Dieser Algorithmus wird in der aktuellen Version (110.40) von SML/NJ (Standard ML/New Jersey) verwendet.

    unsigned long
    sml_hash(unsigned char *str, int len) {
      unsigned long hash = 0;
      int i;
    
      for (i=0; i<len; i++) 
      {
        hash = 33*hash + 720 + str[i];
      }
    
      return hash;
    }
            

7.2.8. STL's Algorithmus

Dieser Algorithmus wird/wurde (?) in der STL (Standard Template Library) von C++ verwendet.

    unsigned long
    stl_hash(unsigned char *str, int len) 
    {
      unsigned long hash = 0;
      int i;
    
      for (i=0; i<len; i++) 
      {
        hash = 5*hash + str[i];
      }
    
      return hash;
    }
            

7.2.9. Java's Algorithmus

Dieser Algorithmus wird (?) in Java's SDK verwendet.

    unsigned long
    java_hash(unsigned char *str, int len) 
    {
      unsigned long hash = 0;
      int i;
    
      for (i=0; i<len; i++) 
      {
        hash += ((unsigned long)s[i]*31)^(n-1-i);
      }
      return hash;
    }
            

7.2.10. Fowler/Noll/Vo Algorithmus

FNV ist ein relativ neuer und guter Hash-Algorithmus. Er wurde von Phong Vo, Glenn Fowler entwickelt und von Landon Curt Noll verbessert.

"FNV hashes are designed to be fast while maintaining a low collision rate. The FNV speed allows one to quickly hash lots of data while maintaining a reasonable collision rate."

Mehr Information zum Algorithmus sowie eine Implementation in C ist im WWW unter folgender Adresse verfügbar: http://www.isthe.com/chongo/tech/comp/fnv/index.html.

7.2.11. Bob Jenkins Algorithmus

Dies ist ein sehr schneller und guter Hash-Algorithmus. Er kommt ohne Multiplikation oder Modulo/Divison aus. Der berechneter Hash-Wert kann mittels Bitweisem UND auf einen kleineren Wertebereich eingeschränkt werden.

Mehr Information zum Algorithmus sowie eine Implementation in C ist im WWW unter folgenden Adressen verfügbar: http://burtleburtle.net/bob/hash/evahash.html und http://burtleburtle.net/bob/hash/index.html#lookup (Dateien lookupa.h und lookupa.c)

Im folgenden wird dieser Algorihmus NEW genannt.

7.3.1. Qualität der Hash-Funktionen

Für den Vergleich wurde jede Hash-Funktion mit einem Testset von ungefähr 4,3 Millionen unterschiedlichen Wörtern "gefüttert" (keine binären Daten). Dabei wurden die Kollisionen bei einer n-Zellen großen Hash-Tabelle aufgezeichnet (wobei n eine 2er Potenz ist) und daraus die Standard-Abweichung, Anzahl der leeren Zellen sowie die maximale Kollisionsrate (einer Zelle) errechnet. Gerade Letzteres ist wichtig zur besseren Abschätzung eines realen Worstcases.

7.3.2. Performance der Hash-Funktionen

Getestet wurde die Berechnung von Wörter der Länge 1 bis 24.

Der SDBM Algorithmus ist sehr schnell, NEW liegt im Mittelfeld, FNV bildet das Schlusslicht!

7.3.3. Fazit

Besonders positiv aufgefallen sind folgende drei Algorithmen:

• FNV

• NEW

• SDBM

Wobei FNV von der Qualität der Hash-Werte am besten abschneidet (gerade für kleinere n), jedoch wegen der Performance (FNV ist der langsamste Algorithmus) ausscheidet.

Der NEW Algorithmus unterscheidet sich in der Qualität der Hash-Werte kaum vom FNV Algorithmus, jedoch ist er fast doppelt so schnell.

Der SDBM Algorithmus ist mehr als 2.5 mal so schnell wie NEW und ist in der Qualität nicht wesentlich schlechter als dieser. Besonders für große n sind alle drei Algorithmen in der Qualität nahezu gleich.