在哈希冲突的情况下，哈希表如何读取正确的值？

Question

我有一些哈希表。例如，我有两个实体如下：

john = { 1stname: jonh, 2ndname: johnson },
eric = { 1stname: eric, 2ndname: ericson }

然后我将它们放入哈希表中：

ht["john"] = john;
ht["eric"] = eric;

假设发生了冲突并且哈希表使用链式解决。因此，这里应该有一个包含这两个实体的链表，如下图所示 哈希表如何知道哪个实体应该返回给相应的键？哈希值是一样的，它对实体结构一无所知。例如，如果我写var val = ht["john"];哈希表将如何找出该值应为john记录而不是eric，因为它只有键和哈希值。

- mtkachenko

---

请查看此链接：https://msdn.microsoft.com/en-us/library/ms379571(v=vs.80).aspx。 - a-man

Answer 1

我认为你所困惑的是哈希表中相邻列表中存储的内容。你似乎认为只有值被存储。事实上，每个列表节点中的数据都是一个元组（键，值）。

一旦你请求ht['john']，哈希表会找到与hash('john')相关联的列表，如果列表不为空，它会在列表中搜索键'john'。如果键作为元组的第一个元素被找到，那么返回值（元组的第二个元素）。如果未找到键，则表示该元素不在哈希表中。

总结一下，键哈希用于快速识别单元格中是否存在应存储的元素。实际上，键等式测试是用来决定键是否存在的。

- George Octavian Rabanca

---

在复杂对象的情况下，键相等是如何工作的？哈希表中的值是具有不同属性的对象，但您只使用键来获取它。哈希表不知道对象结构以及我使用哪个属性作为键。 - mtkachenko

看起来我明白了。我猜哈希表应该将完整的键和整个对象保持在一起，以确定该键是否等于所需的键，对吗？ - mtkachenko

正如我在答案中提到的那样，关键字与对象一起存储在哈希表中：(key, value)。在你的情况下，关键字是值的一部分，但并不总是这样。因此，哈希表在找到您搜索的关键字之前根本不关心您的值。然后，它返回相关联的值，而不以任何方式分析它。 - George Octavian Rabanca

另外，我开始阅读C#字典的源代码，发现它在内部将键和值保持在一起。 - mtkachenko

Answer 2

这是您要求的内容吗？我已经放在评论中了，但似乎您没有跟随链接。

Hashtable类中的冲突解决方法：

回想一下，当将一个项插入或检索一个项从哈希表中时，可能会发生冲突。插入项时，必须找到一个空槽。检索项时，如果它不在预期位置，则必须找到实际项。我们之前简要地研究了两种冲突解决策略：

- 线性探测 - 二次探测

Hashtable类使用一种称为重新散列的不同技术。 (有些源将重新散列称为双重散列。)

重新散列的工作原理如下：有一组不同的哈希函数H1 ... Hn，当从哈希表中插入或检索项时，最初使用H1哈希函数。如果这导致冲突，则尝试使用H2，以此类推，直到需要使用Hn。前一节仅显示了一个哈希函数，即初始哈希函数（H1）。其他哈希函数与此函数非常相似，只是通过乘法因子区分。通常，哈希函数Hk定义为：

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

数学注释：在重新散列时，每个哈希表中的插槽被访问一次非常重要。也就是说，对于给定的键，你不希望Hi和Hj哈希到哈希表中的同一个插槽。使用Hashtable类使用的重新散列公式，如果(1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))和hashsize互质，则保持此属性。 （如果两个数字没有共同因素，则它们是互质的。）如果hashsize是质数，则这两个数字保证是互质的。重新散列提供比线性探测或二次探测更好的冲突避免。

源代码在这里

- a-man