如何用鏈接實現哈希表？

這可能是一個愚蠢的問題，但是，我不能讓上帝的愛弄清楚我在鏈接散列表背後的理論中丟失了什麼。如何用鏈接實現哈希表？

這是我的理解：

哈希表使用哈希一鍵到值存儲位置相關聯。有時散列會爲不同的鍵產生相同的位置，即可能發生衝突。

在這種情況下，我們可以通過將具有相同位置的所有值存儲到該位置的鏈接列表來實現鏈接。

我不明白的是：

當你輸入一個密鑰和散列函數產生在其中有鏈接的位置，它是如何確定哪些鏈接列表中的值在該位置屬於那個特定的鑰匙，而不是另一個涉及碰撞的鑰匙？

我意識到這是基礎理論，但如果任何人都可以在我的推理中指出錯誤或告訴我我錯過了什麼，我將非常感激。

來源

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

如何用鏈接實現哈希表？

回答

相關問題