data-structures - 发生冲突时，哈希表如何读取正确的值？

Question

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

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

然后我把它们放在哈希表中:

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

让我们想象一下有一个冲突，哈希表使用链接来修复它。因此，应该有一个包含这两个实体的链表，如
哈希表如何理解应该为键返回哪个实体？哈希值是相同的，它对实体结构一无所知。例如，如果我写这个 var val = ht["john"]; hashtable(只有键值及其散列)如何找出值应该是 约翰 记录而不是 埃里克 .

Answer 1

我认为您对哈希表相邻列表中每个位置存储的内容感到困惑。您似乎假设只存储了值。实际上，每个列表节点中的数据都是一个元组(键，值)。

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

总而言之， key 哈希用于快速识别元素应存储在的单元格(如果存在)。实际键相等测试以确定 key 是否存在。