c - 哈希码无效

Question

我发现这个哈希函数是用 Java 编写的，并在 stackoverflow 的帮助下将它转换为 C。问题是它每次在同一个词上运行时都会给出不同的哈希值。

这是原始函数:

long sfold(String s, int M) 
{
  int intLength = s.length() / 4;
  long sum = 0;
  for (int j = 0; j < intLength; j++) 
  {
     char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
     long mult = 1;
     for (int k = 0; k < c.length; k++) 
     {
        sum += c[k] * mult;
        mult *= 256;
     }
  }

  char c[] = s.substring(intLength * 4).toCharArray();
  long mult = 1;
  for (int k = 0; k < c.length; k++) 
  {
     sum += c[k] * mult;
     mult *= 256;
  }

  return(Math.abs(sum) % M);
 }

下面是我们如何重写它:

include <stdlib.h>
include <stdio.h>
include <math.h>
include <string.h>

long sfold(char * s, int M);

int main(void)
{
    char *  s = "test";
    int M;
    long x;
    M = 525;
    x = sfold(s,M);

    printf("%ld\n",x);
}   
long sfold(char * s, int M)
{
    int intLength = strlen(s) / 4;
    long sum = 0;

    for (int j = 0; j < intLength; j++) 
    {
       char c[4];
       memcpy(c, s + 4 * j, 4);

       //char c[] = s.substring(j * 4, (j * 4) + 4).toCharArray();
       long mult = 1;

       for (int k = 0; k < strlen(c); k++) 
       {
           sum += c[k] * mult;
           mult *= 256;
       }
    }

    char c[intLength];
    memcpy(c,s,intLength);
    //char c[] = s.substring(intLength * 4).toCharArray();
    long mult = 1;

    for (int k = 0; k < strlen(c); k++) 
    {
       sum += c[k] * mult;
       mult *= 256;
    }

    return(abs(sum) % M);
}

我们每次运行程序时，这不应该给出相同的值吗？任何人都知道出了什么问题吗？

Answer 1

所有那些字符串复制真的很愚蠢。如果您只需要字符值，那么复制有什么意义？

这是它在 C 中的样子:

long sfold(char* s, unsigned long M) {
   unsigned long mult = 1, sum = 0;
   while (*s) {
      sum += (uint8_t)(*s++) * mult;
      mult *= 256;
      if (!mult) mult = 1;
   }
   return sum % M;
}

但这是一个糟糕的哈希算法。你最好使用一个简单的模块化哈希(这也不是很好，但也没有那么糟糕):

/* This could be any small prime */
static const unsigned long mult = 31;
long sfold(char* s, unsigned long M) {
   /* Avoid having the hash of the empty string be 0 */
   unsigned long sum = 0xBEA00D1FUL;
   while (*s)
      sum += (uint8_t)(*s++) * mult;
   return sum % M;
}