1

当我们说哈希函数时，我发现它意味着在大多数文章中将键的序列字节转换为 32 位或 64 位无符号整数，例如看到这个

但是，当你实现 hash_table 时，看起来散列函数意味着将一个非常大的整数转换为更小的内部数组索引，而在这个域中，上面提到的“散列函数”的含义变成了键的散列值。

  1. 我的理解对吗？
  2. 有人可以提供一些关于将大整数转换为更小的内部数组索引的见解或链接或论文吗？

谢谢

4

3 回答 3

1

我对“散列函数”的理解是：从集合 A 到集合 {0, 1, 2, ..., n} 的任何函数，其中 n 是非负自然数。没有其他东西本质上是“哈希函数”的一部分。您的两个示例 - 以及许多其他示例 - 都包含“哈希函数”，因为它们将事物映射到非负整数的子集。将“散列函数”应用于问题的方式也不是定义的一部分。

我什至不认为域必须大于共域，但我可能错了。我不认为 codomain 可以是无限的，但我可能错了。

于 2012-01-06T17:48:14.430 回答
1

术语“散列”通常涵盖上述两种含义；正如其他答案所指出的那样，操作是相似的。此外，这两个过程通常是串联使用的——如果没有另一个，一个就没有真正的用处。

在寻找或设计散列系统时，繁琐的部分是生成一个分布良好的 32/64 位整数（实际的“散列函数”）。一旦你有了一个好的初始哈希值，你使用它的输出的确切方式就不是关键了，只要结果在你的最终索引中相当均匀地分布。（这种功能划分允许您独立于哈希函数更新算法/数据结构。）

生成最终索引（适用于固定大小的哈希表）的明显方法是将哈希值取模索引的数量。然而，使用散列值的方式取决于应用程序（例如，动态大小的散列表可能会做一些与固定大小的表不同的事情）。

于 2012-01-06T18:09:00.603 回答
0

哈希函数只是从大型数据集到较小数据集的映射。在哈希表的情况下，较小的数据集（通常是您指出的整数）用作存储桶的查找键。

根据您的示例文章，所有这些哈希函数输出的所有整数都将用作哈希表的查找索引。

于 2012-01-06T17:46:09.267 回答