哈希集如何發生碰撞？

Question

如果散列集只包含任何不同元素的一個實例，那麼在這種情況下可能會發生什麼衝突？

因爲只有一個給定的元素，載荷因子如何成爲一個問題？

雖然這是作業，它不適合我。我正在輔導某人，我需要知道如何向他們解釋。

Answer 1

一個「哈希表」（其中「哈希集合」是多種）背後的總體思路是，你有許多包含要投入「鍵」值（例如，字符串）對象某種容器，然後能夠輕鬆地通過其「關鍵」值查找單個對象，而無需檢查容器中的每個項目。

有人可能，例如，把值到一個排序數組，然後做一個二進制搜索找到的值，但如果有大量的更新維護一個有序數組是昂貴的。

所以關鍵值是「散列」。例如，可以將所有字符的ASCII值加在一起以創建一個單一的數字，即字符串的「散列」。 （有更好的散列計算的算法，但是精確的算法並不重要，這是一個容易解釋。）

當你這樣做，你會得到一個數字，對於一個十字符串，將在600到1280的範圍內。現在，如果將它除以500並取其餘值，則將有一個介於0和499之間的值。（請注意，字符串不一定是十字符 - 較長的字符串會添加到較大的值，但是當您劃分剩餘部分時，您仍然會得到0到499之間的數字。）

現在創建一個包含500個條目的數組，並且每次獲得新對象，如上所述計算其哈希值，並使用該值來索引數組。將新對象放入與該索引對應的數組條目中。

但是（尤其是使用上面的樸素散列算法），您可能會有兩個不同的字符串具有相同的散列。例如，「ABC」和「CBA」將具有相同的散列，並且最終將進入陣列中的相同插槽。

爲了處理這種「衝突」有幾個策略，但最常見的是創建一個鏈表掉數組項，並把各種「散列同義詞」進入該名單。

你會一般都儘量有數組足夠大（和有更好的哈希計算算法），以儘量減少這種衝突，但是，使用散列方案，有沒有辦法完全避免碰撞。

請注意，同義詞列表中的多個條目不相同 - 它們具有不同的鍵值 - 但它們具有相同的散列值。

Answer 2

我們假設你有一個整數HashSet，你的Hash函數是mod 4.如果你嘗試插入它們，那麼整數0,4,8,12,16等都將變成colide。 （模4是一種可怕的散列函數，但它說明的概念），負載因子被關聯到具有碰撞的機會

假設一個適當的功能;請注意我說相關而不相等，因爲它取決於您用來處理衝突的策略。一般來說，高負載因數會增加碰撞的可能性。假設你有4個插槽，並且你使用mod 4作爲散列函數，當載入因子爲0（空表）時，你將不會碰撞。當你有一個元素時，碰撞的概率是0.25，這顯然會降低性能，因爲你必須解決碰撞。現在，假設您使用線性探測（即在碰撞時使用下一個可用條目），一旦您達到表中的3個條目，您就有0.75的碰撞概率，並且如果您有碰撞，在最好的情況下，你會去下一個入口，但最糟糕的是，你將不得不經過3個入口，所以碰撞意味着你不需要直接訪問，而是平均需要一次平均2次的線性搜索項目。

當然，你有更好的策略來處理衝突，一般情況下，在非病理情況下，可以接受0.7的負載，但在衝突爆發後性能下降。