c - 计算散列数的函数，它到底做了什么，为什么？

Question

我知道这个函数是用散列数做的， 但不明白这个功能的目的是什么？ 为什么是“res *31 + *key”？ 为什么31p>

unsigned int HashAlg(char* key)
{
    unsigned int res = 0;

    while (*key != 0)
    {
        res = res * 31 + *key;
        ++key;
    }

    return res;
}

Answer 1

该实现是 D.J. 的乘法字符串哈希函数的变体。伯恩斯坦:

unsigned djb_hash ( void *key, int len )
{
  unsigned char *p = key;
  unsigned h = 0;
  int i;

  for ( i = 0; i < len; i++ )
    h = 33 * h + p[i];

  return h;
}

像这样的哈希函数的目的是将搜索关键字(如字符串 "item1")映射到一个索引，然后可以在哈希表、缓存等中使用该索引；简单地说，散列值为我们提供了表中应存储 "item1" 的相应记录的位置。哈希表反过来用于实现关联数组和动态集。有关更多详细信息，我建议从 Wikipedia page 开始.

您可以看到，在您的实现中，常量 33 已切换为 31。没有多少真正的数学工作可以明确地证明素数和哈希函数之间的关系。在散列函数中使用质数的基本概念围绕着转换散列函数当前状态的概念(对散列值应用某种形式的数学运算，例如乘法或加法)。结果被限制为一个新的散列值，该值在统计上应该具有更高的熵值，或者换句话说，新散列值中的任何位都具有非常低的位偏差。简单来说，当您将一组随机数乘以一个素数时，所得数字(在位级别分析时)应该不会偏向于一种状态或另一种状态，即 P(Bi = 1) ~ = 0.5。没有具体证据表明情况确实如此，或者它只发生在质数上，这似乎只是我们似乎有义务遵循的一种持续不断的自称直觉。这些属性是事后判断的，这意味着我们尝试使用选定的常数来分析哈希函数(或 PRNG)的属性，并形成一种直觉，该常数“工作良好”，即产生特定分布或证明雪崩效应，为 a 产生均匀分布特定的一组输入等。