哈希码无效

Question

我发现这个 Hash 函数是用 Java 编写的，在 Whosebug 的帮助下将它转换为 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;
}

Answer 2

我想我已经为您解决了大部分错误。我让它符合 C99，主要是出于习惯。主要问题是使用 strlen(c)：c 是字符数组，而不是字符串（这是一个以空 '[=14=]' 字符结尾的字符数组）。您需要重写您的函数，以便在 calloc()/malloc() 失败时，该函数会因错误而终止。或者，如果您的编译器支持，您可以像以前使用的那样返回到可变长度数组。 There are likely better hash functions in other posts on Whosebug，但这至少可以帮助您以确定性的方式工作，而不会调用未定义的行为。

代码清单

/******************************************************************************/
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <string.h>

#define BUF_SIZE  (4)

/******************************************************************************/
long sfold(const char* s, int M);

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

   printf("String:%s - Hash:%ld\n", s, x);
}

/******************************************************************************/
long sfold(const char* s, int M) {
   int intLength = strlen(s) / 4;
   char* c = calloc(intLength, sizeof(char));   /* Warning, test if c==NULL, this
                                                 * call can fail.
                                                 */
   long sum = 0;
   int j, k;

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

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

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

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

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

   free(c);
   return(abs(sum) % M);
}

示例输出

for i in $(seq 1 5); do echo $i; ./a.out; done
1
String:test string - Hash:384
2
String:test string - Hash:384
3
String:test string - Hash:384
4
String:test string - Hash:384
5
String:test string - Hash:384

哈希码无效

hash code no working

c

hash