table lookup 遇到的问题，求解释

keneth2078

#define HASHSIZE 101

struct nlist {       /* table entry: */
       struct nlist *next;   /* next entry in chain */
       char *name;           /* defined name */
       char *defn;           /* replacement text */
   };

static struct nlist *hashtab[HASHSIZE];  /* pointer table */
  

/* hash:  form hash value for string s */
   unsigned hash(char *s)
   {
       unsigned hashval;

       for (hashval = 0; *s != '\0'; s++)
           hashval = *s + 31 * hashval;    // 这里的hashval为什么乘于31. 而且与*s相加？  请解释~
       return hashval % HASHSIZE;
   }



/* lookup:  look for s in hashtab */
   struct nlist *lookup(char *s)
   {
       struct nlist *np;

       for (np = hashtab[hash(s)];  np != NULL; np = np->next)   
           if (strcmp(s, np->name) == 0)
               return np;     /* found */
       return NULL;           /* not found */
   }

hellioncu

这个hash函数就是这样的，理论上说换成其他的值也行

keneth2078

这个hash函数就是这样的，理论上说换成其他的值也行
hellioncu 发表于 2011-03-24 17:12

    明白了，这是自定义的hash因式。。谢谢~

ypyf3000

一般认为用质数因子（这里的31）更好，这样可以减小冲突，也可以用其他值