Hash Funktion
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Wird bei HashTabellen verwendet um aus einem Schlüssel den sogenannten Hash zu berechnen. Der Hash wird dann auf einen bestimmten Wertebereich eingeschränkt "INDEX = (HASH mod BEREICH)" und als Index in ein konventionelles Array verwendet.

Ziel einer HashFunktion ist eine möglichst gleichmäßige Verteilung der Indexwerte bei möglichst geringem Rechenaufwand. Da dabei die Abbildung des Hashes auf Indices in das Array dabei auch eine Rolle spielt, wird meist für BEREICH meist eine Primzahl, jedenfalls aber keine Zweier-Potenz verwendet.

Beispiel für eine einfache HashFunktion:

unsigned long StrRetHash(char *s)
{
   unsigned long hash=0;
   while(*s) {
      hash = hash*33 + (*s++);
   }
   return hash;
}

Beispiel für eine komplexere Hash-Funktion:
ulong hash(char *name)
{
   ulong  h, g;
   for (h=0;  *name;  ++name)  {
      h<<=4; h+= *name;
      if (g= h&0xf0000000)  h^= g>>24;
      h&=~g;
   }
   return (h);
}

Hab ich mal in irgendeiner Unix-Doku gefunden. Der Ursprungsautor ist irgendein Deutscher.
http://uw713doc.caldera.com/en/SDK_cprog/OF_HashTable.html
Das URL-Ziel ist nicht die soeben angesprochene Unix-Doku, enthält aber diese hash-Funktion. --hs

Weitere Links:


KategorieProgrammierBeispiele KategorieDefinition


StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 24. September 2004 18:06 (diff))
Suchbegriff: gesucht wird
im Titel
im Text