如何在没有无符号整数的情况下制作一个好的散列函数？

Question

我正在寻找一个不依赖于整数溢出且不依赖于无符号整数的简单哈希函数。

问题是我必须在 Unreal Engine 的蓝图中创建散列函数（只有带符号的 32 位整数，具有未定义的溢出行为）并且在 PHP5 中的版本使用64 位有符号整数。

因此，当我使用 'common' 简单散列函数时，它们在两个平台上不会给出相同的结果，因为它们都依赖于无符号整数的位溢出行为。

唯一真正重要的是它的优点 'randomness'。有谁知道可以做到这一点的简单方法吗？

它适用于向服务器发送消息的非常基本的签名系统。不需要最高安全性......它用于在服务器上存储简单游戏的高分。这个想法是我将从消息中生成几个散列整数（使用不同的'start numbers'）并将它们附加到一个散列签名中）。我只需要确保如果人们嗅探发送到服务器的网络消息，他们就无法轻易发送伪造的消息。他们需要为他们的消息提供正确的散列签名，除非他们知道正在使用的散列函数，否则他们不应该这样做。当然，如果他们对游戏进行逆向工程，他们仍然可以 'hack'，但我不知道如何应对... 我无法访问 unreal engine 蓝图系统中的现有哈希函数。

Answer 1

我要尝试的第一件事是使用有符号整数来模拟无符号整数的行为，方法是在累积的哈希值变得足够大以至于可能有溢出的风险时显式应用模运算符。

C 中的示例代码（对于糟糕的散列函数表示歉意，但相同的技术应该适用于任何散列函数，至少在原则上是这样）：

#include <stdio.h>
#include <string.h>

int hashFunction(const char * buf, int numBytes)
{
   const int multiplier      = 33;
   const int maxAllowedValue = 2147483648-256;  // assuming 32-bit ints here
   const int maxPreMultValue = maxAllowedValue/multiplier;

   int hash = 536870912;  // arbitrary starting number
   for (int i=0; i<numBytes; i++)
   {
      hash = hash % maxPreMultValue;    // make sure hash cannot overflow in the next operation!
      hash = (hash*multiplier)+buf[i];
   }
   return hash;
}

int main(int argc, char ** argv)
{
   while(1)
   {
      printf("Enter a string to hash:\n");
      char buf[1024]; fgets(buf, sizeof(buf), stdin);
      printf("Hash code for that string is:  %i\n", hashFunction(buf, strlen(buf)));
   }
}

如何在没有无符号整数的情况下制作一个好的散列函数？

How can I make a good hash function without unsigned integers?

hash

integer

signed