哈希图中的哈希部分是如何工作的？

Question

在维基百科的哈希表文章中有一张很好的图片：

到目前为止，一切都很清楚，除了中间的哈希函数。

• 一个函数如何从任何字符串生成正确的索引？这些索引实际上也是整数吗？如果是，那么这个函数如何能够为John Smith输出1，为Lisa Smith输出2等等？

- sub

Answer 1

这是哈希表/字典等的一个主要问题之一。你必须选择一个好的哈希函数。一个非常糟糕但快速的哈希函数可以是键的长度。你立刻会看到，你将得到很多冲突（不同的键，但是相同的哈希）。另一个糟糕的哈希函数可能是你的键的第一个字符的ASCII值。也会有很多冲突。
因此，你需要一个比这两个更好的函数。你可以添加（异或）所有密钥字符的ASCII值，并混合长度。实际上，你经常依赖于要哈希的对象的值（字段）（相同的值给出相同的哈希值=>值类型）。对于引用类型，你可以混合内存位置。

在你的例子中，这只是大大简化了一下。没有真正的哈希函数会将这些键映射到连续的数字。

也许你想读一下我关于哈希表的以前的回答

- tanascius

Answer 2

一个简单的哈希函数可能如下所示：

$hash = $string[0] % HASH_TABLE_SIZE;

此函数将返回一个数字，介于0和HASH_TABLE_SIZE - 1之间，具体取决于字符串的第一个字母。该数字可用于转到哈希表中的正确位置。

真正的哈希函数将考虑字符串中的所有字母，并且它将被设计为在桶之间有均匀分布。

- Sjoerd

Answer 3

哈希函数通常（但不一定总是）输出所需范围内的整数（通常是哈希函数的参数）。该整数可以用作索引。请注意，当给出不同的数据进行哈希处理时，哈希函数不能保证始终产生唯一结果。这称为哈希碰撞，哈希算法必须以某种方式处理它。

至于您的具体问题，字符串如何变成数字。任何字符串都由字符（J、o、h、n等）组成，而字符可以被解释为数字（在计算机中）。 ASCII和UTF标准将特定的值绑定到特定的字符，因此结果是确定性的，并且在所有计算机上始终相同。因此，哈希函数对这些字符执行操作，将它们处理为数字，并得出另一个数字（输出）。例如，您可以简单地对所有值求和并使用模运算来限制结果值的范围。

这将是一个相当可怕的哈希函数，因为例如“ab”和“ba”将获得相同的结果。设计哈希函数很困难，因此除非情况需要其他解决方案，否则应使用一些现成的算法。

- Pasi Savolainen

Answer 4

在 MSDN 上有一篇关于哈希函数（以及冲突检测/解决）的非常好的文章：

第二部分：队列、堆栈和哈希表

您可以跳到标题使用哈希函数压缩序数索引

有一些是 .NET 特定的内容（当他们谈论 .NET 默认使用哪个哈希算法时），但大部分是与语言无关的。

- Justin Niessner

Answer 5

一个哈希函数所要求的仅仅是在给定相同的键时返回相同的整数。从技术上讲，一个总是返回“1”的哈希函数并不是错误的。

- Erix