如何用链接实现哈希表？

这可能是一个愚蠢的问题，但是，我不能让上帝的爱弄清楚我在链接散列表背后的理论中丢失了什么。如何用链接实现哈希表？

这是我的理解：

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

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

我不明白的是：

当你输入一个密钥和散列函数产生在其中有链接的位置，它是如何确定哪些链接列表中的值在该位置属于那个特定的钥匙，而不是另一个涉及碰撞的钥匙？

我意识到这是基础理论，但如果任何人都可以在我的推理中指出错误或告诉我我错过了什么，我将非常感激。

来源

2011-04-09 Sind

在ELF格式规范中有很好的讨论。我实际上一次理解它，或者以为我做过：^） – 2011-04-09 05:09:56

简单的方法：维护一个“哈希表条目”的链表，它是键/值对。一旦到达存储桶，请检查存储桶中所有密钥的查询键。

来源

2011-04-09 05:12:57 rlibby

这正是ocaml所做的。它被实现为具有键值对的链表的数组。 – nlucaroni 2011-04-09 17:55:32

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

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

您可以理解写入F＃下面迷你哈希表实现，从this blog 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函数执行。

来源

2011-05-05 11:18:33

如何用链接实现哈希表？

回答

相关问题