函数计算哈希数,它到底是做什么的,为什么？

Question

我知道这个函数正在用哈希数做一些事情,但是没有完全理解这个函数的用途？为什么"res*31 +*key"？为什么31？

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

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

    return res;
}

Answer 1

该实现是DJ Bernstein的乘法字符串哈希函数的变体:

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"应该存储相应记录的表中的位置.反过来,散列表用于实现关联数组和动态集.有关更多详细信息,我建议从维基百科页面开始.

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

Answer 2

为什么“res *31 + *key”

假设如果只是 ; 会发生什么res = res + *key？那么哈希只会将键中的所有值相加。这将为 hello、elloh、olleh、loleh 等排列后的字符串产生相同的哈希值。乘以 > 1 的值会大大降低这种情况的可能性。

为什么是31？

可能是为了避免 2 的幂，它会简单地向左移动一个值，并在几次移位后丢失它。非 2 的幂可以避免这个问题。