如何用链式实现哈希表？

Question

这可能是一个愚蠢的问题，但是，看在上帝的份上，我无法弄清楚我在带有链接的哈希表背后的理论中缺少什么。

这就是我的理解：

哈希表使用哈希将键与存储值的位置相关联。有时，散列会为不同的键产生相同的位置，即可能会发生冲突。

在这种情况下，我们可以通过将具有相同位置的所有值存储到该位置的链表来实现链接。

我不明白的是：

当您输入一个键并且哈希函数生成一个存在链接的位置时，它如何确定该位置的链表中的哪个值属于该特定键，而不是另一个值碰撞中涉及钥匙？

我意识到这是基本理论，但如果有人能指出我推理中的错误或告诉我我错过了什么，我将非常感激。

Answer 1

简单的方法：维护一个“哈希表条目”的链表，这些条目是键/值对。到达存储桶后，根据存储桶中的所有键检查您的查询键。

Answer 2

当您输入一个键并且哈希函数生成一个存在链接的位置时，它如何确定该位置的链表中的哪个值属于该特定键，而不是涉及冲突的另一个键？

您只需通过键对存储桶进行线性搜索即可。

您可能会欣赏以下用 F# 编写的迷你哈希表实现，摘自 此博客post：

> let hashtbl xs =
    let spine = [|for _ in xs -> ResizeArray()|]
    let f k = spine.[k.GetHashCode() % spine.Length]
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);;
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality

此 hashtbl 函数采用键值对的关联序列 xs，构建一个表示为 spine 数组的哈希表ResizeArray 存储桶并返回一个 lambda 函数，该函数查找适当的存储桶并在其中针对给定键 k 进行线性搜索。线性搜索是使用 Seq.pick 函数执行的。