哈希表如何在碰撞时读取正确的值？

我有一些哈希表.例如,我有两个实体,如

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

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

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

让我们假设有一个碰撞和哈希表使用链接来修复它.因此,应该有这样两个实体的链表 哈希表如何理解应该为密钥返回什么实体？哈希值是相同的,它对实体结构一无所知.例如,如果我写这个var val = ht["john"];哈希表(只有键值及其哈希值)如何发现该值应该是john记录而不是eric.

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

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

总而言之,密钥散列用于快速识别元素应存储在其中的单元(如果存在).测试实际密钥相等性以确定密钥是否存在.