短字符串(标记名称)的最佳32位哈希函数是什么？

Question

对于相对较短的字符串,最好的32位散列函数是什么？

字符串是包含英文字母,数字,空格和一些其他字符(标签名称#,$,.,...).例如:Unit testing,C# 2.0.

我正在寻找"最佳碰撞"中的"最佳",性能对我的目标并不重要.

Answer 1

我不确定它是否是最佳选择,但这里是字符串的哈希函数:

编程实践(HASH TABLES,第57页)

/* hash: compute hash value of string */
unsigned int hash(char *str)
{
   unsigned int h;
   unsigned char *p;

   h = 0;
   for (p = (unsigned char*)str; *p != '\0'; p++)
      h = MULTIPLIER * h + *p;
   return h; // or, h % ARRAY_SIZE;
}

根据经验,值31和37已被证明是
ASCII字符串的散列函数中乘数的良好选择.

Answer 2

如果性能不重要,只需采用安全散列(如MD5或SHA1),并将其输出截断为32位.这将为您提供与随机无法区分的哈希码的分布.

Answer 3

对此,我很抱歉.今年早些时候,我创作了一个名为Hashing Short Strings的页面,这可能对本次讨论很有帮助.总之,我发现CRC-32和FNV-1a优于散列短串.在我的测试中,它们是高效的并且产生广泛分布和无碰撞的哈希.当输出被折叠到32位时,我惊讶地发现MD5,SHA-1和SHA-3产生了少量的冲突.