5

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

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

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

    return res;
}
4

2 回答 2

5

该实现是 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"应该存储相应记录的位置。反过来，哈希表用于实现关联数组和动态集。有关更多详细信息，我建议从Wikipedia 页面开始。

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

于 2013-03-19T12:02:37.960 回答
0

为什么“res *31 + *key”

假设如果它只是res = res + *key; 然后哈希只会将键中的所有值相加。这将为 hello、elloh、olleh、loleh 等置换字符串产生相同的哈希值。乘以 > 1 的值会降低这种可能性。

为什么是 31？

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

于 2013-03-19T12:01:15.937 回答