hashing modulo funktion

eboymichi

hallo,

ich möchte eine hashfunktion schreiben. es sollte die sogenannte modulo funktion sein mit einem hashtable von 30 elementen. wie gehe ich da am besten vor. danke für die antworten. ich möchte den hashwert über die berechnung der ersten drei buchstaben eines strings berechnen, es soll sich um die modulo funktion handeln. oder gibts es auch möglichkeiten eine hash funktion nach integer werten zu schreiben?

volkard

einen string hashen zum beispiel mit

unsigned int hashString(char *str){
   unsigned int r=0;
   while(*str!='\0'){
      r=r*31+*str;
      ++str;
   }
   return r;
}

oder ums nur auf drei buchstaben zu beschränken

unsigned int hashString(char *str){
   unsigned int r=0;
   if(*str!='\0'){
      r=r*31+*str;
      ++str;
   }
   if(*str!='\0'){
      r=r*31+*str;
      ++str;
   }
   if(*str!='\0'){
      r=r*31+*str;
      ++str;
   }
   return r;
}

den modulo-trick verwendest du eh innerhalb der hashtable.

unsigned int storeString(char* str){
   unsigned int h=hashString(str);
   unsigned int p=h%30;
   ...
}

Hi!

volkard schrieb:

einen string hashen zum beispiel mit

unsigned int hashString(char *str){
   unsigned int r=0;
   while(*str!='\0'){
      r=r*31+*str;
      ++str;
   }
   return r;
}

wie kommt man auf r=r*31+*str;
?
gruß

volkard

lökjlö schrieb:

wie kommt man auf r=r*31+*str;
?

das kann ich dir nicht sagen. ich hatte damals ein wenig experimentiert und die 31 kam mir hübsch vor.

aber das war ein fehler, wie ich gerade bemerke. die 31 riecht schrecklich nach java. siehe http://stackoverflow.com/questions/822363/proof-why-does-java-lang-string-hashcodes-implementation-match-its-documentat/822394

nehmen wir lieber die 33. dann sind wir bei D.J Bernstein und fühlen uns geborgen.
http://www.fantasy-coders.de/projects/gh/html/x435.html

eboymichi

dankeschön, ich versuche es mal in mein programm einzubauen. Gruss michi

was spricht gegen

char* str = "Irgendwas";
double n = 0.0;
unsigned long number = strlen(str);

while ( str[i] && n <= 5 )
    number += (toupper(str[i++]) - 'A' + 1) *  pow( 26, n++ );

Die pow Funktion liese sich notfalls auch ersetzen.

volkard

simpl0r schrieb:

was spricht gegen
double n = 0.0;
unsigned long number = strlen(str);

while ( str[i] && n <= 5 )
    number += (toupper(str[i++]) - 'A' + 1) *  pow( 26, n++ );
Die pow Funktion liese sich notfalls auch ersetzen.

du machst auch nix anders, als

unsigned int hashString(char *str){
   unsigned int r=strlen(str);
   while(*str!='\0'){
      r=r*26+*str;
      ++str;
   }
   return r;
}

mit zusätzlich der bregrenzung auf die ersten 6 zeichen und bei dir haben die hinteren die größeren potenzen und bei mir die vorderen und du machst toupper(str[i++]) - 'A' + 1.

gründe dagegen:
a) die initialisierung r=strlen(str) kostet zeit, aber soll anscheinen "computerpanne" von "computermaus" trennen. aber strlen selber ist beinahe so teuer wie gleich den ganzen string zu haschen.
b) toupper plättet den raum. denn "Computer"!="computer". warum sollten sie den gleichen hashwert bekommen?
c) x-'A'+1 ist nutzlos und x würde gleichermaßen funktionieren.
d) *26 ist suboptimal, wenn man mehr als 5 buchstaben erlauben will.

zu d) man mag hier nie mit einer geraden zahl multiplizieren. denn wenn man mit einer geraden zahl multipliziert, werden die bits verwürfelt und um eins nach links geshiftet, wobei rechts eine neue 0 erscheint. oberflächlich: dadurch hat man effektiv nur 31 bits zur verfügung statt der 32 bits, die der int eigentlich eingebaut hat. tiefgreifend und tödlich: dadurch kann das ergebnis nur von den letzten 31 zeichen beeinflußt worden sein und "Deutschland ist schon wieder Fußballweltmeister!" hasht auf den selben wert wie "Italien ist schon wieder Fußballweltmeister!", und das wollen wir doch alle nicht, oder?