哈希映射中的哈希部分如何工作？

Question

因此，有在hash maps article维基百科上这样漂亮的图片：

都清楚了，到目前为止，除了中间的散列函数。

• 函数如何从任何字符串中生成正确的索引？这些索引是否也是现实？如果是的话，John Smith,2的Lisa Smith等功能如何输出1等？

Answer 1

这是hashmaps/dictionaries等关键问题之一。你必须选择一个好的散列函数。一个非常糟糕但快速的散列函数可能是密钥的长度。你马上就会看到，你会得到很多的碰撞（不同的键，但相同的散列）。另一个不好的哈希函数可能是您的密钥的第一个字符的ASCII值。很多也是碰撞。
所以你需要一个比这两个更好的函数。您可以添加（xor）关键字符的所有ASCII值并混合长度。在实践中，你经常依赖于你想散列的对象的值（字段）（相同的值给出相同的hash =>值类型）。例如，对于参考类型，您可以在内存位置混合使用。

在你的例子中，这只是简化了很多。没有真正的散列函数会将这些键映射到连续的数字。

也许你想读我的previous answers to hashmaps

Answer 2

散列函数最常（但不一定总是）输出所需范围内的整数（通常参数哈希函数）之一。该整数可以用作索引。注意，散列函数不能保证在给予散列的不同数据时始终产生唯一结果。这被称为散列冲突，并且散列算法必须总是以某种方式处理它。

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

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

Answer 3

一个简单的散列函数可以如下：

$hash = $string[0] % HASH_TABLE_SIZE; 

该函数将返回0和HASH_TABLE_SIZE之间的数 - 1，根据字符串的第一个字母。这个数字可以用来到哈希表中的正确位置。

一个真正的散列函数将考虑字符串中的所有字母，并且它将被设计为使得在这些桶之间存在均匀分布。

Answer 4

散列函数所需要的只是它返回给定相同键的相同整数。从技术上讲，总是返回'1'的散列函数并不正确。

Answer 5

有一个关于如何散列函数（和colision检测/分辨率）在MSDN上一个真正的好文章：

Part 2: The Queue, Stack, and Hashtable

您可以向下跳到压缩有序索引与散列函数头

有一些特定于.NET的元素（当他们谈论默认使用哪种Hash算法.NET时），但大多数情况下它是语言不可知的。