有關散列表和字典的面試問題

最近我在一些關於散列表的訪談中鑽了一下，什麼時候需要重寫GetHashCode（）。討論不斷深入，直到我投入毛巾。有關散列表和字典的面試問題

我現在正在做一些研究，以涵蓋下一次準備的一切。

我發現這一點，我想優秀文章分享到： http://msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx#datastructures20_2_topic5

1）的東西，我不覺得很舒服是字典基於哈希的事實，但列表是顯然不是。這僅僅意味着在列表<>和數組[]中搜索是線性的，而在字典或散列表中搜索是恆定的，因此速度更快？這是全部嗎？

2）如果我在字典中使用類作爲鍵，我需要根據任何必需的標識字段來覆蓋該類的GetHashcode（）以使這些實例具有唯一性。但是它仍然可能發生這兩個ID字段是相等的，並且會生成相同的哈希碼？如果是這種情況，那麼在兩個實例發生碰撞時會發生什麼？

3）如何解決碰撞？我在文章中閱讀了關於哈希表和Chaining詞典碰撞情況下重新哈希方法的文章。但我仍然不確定它是如何工作的，因爲我不是數學天才。： - \有沒有人可以更好地解釋它是如何工作的？

非常感謝，卡瓦

來源

2011-02-07 Houman

如果生成相同的哈希碼，則在該對象上運行equals函數以確定是否相等。因此，不要忘記也要重寫該函數。 – Magnus 2011-02-07 15:28:59

我只是想感謝所有貢獻的人。我接受了一次採訪，他們要求HashSet哈哈。在我們討論的過程中，我一次性給了他所有的哈希/反對，並給他留下了深刻的印象。通過了面試。所以它一定是對的。 ;） – Houman 2011-02-17 11:04:17

1）通常，是的，Dictionary<T>或HashSet<T>具有恆定的時間訪問。在未排序的List<T>或數組中定位項目必須線性完成。排序的集合可讓您執行二進制搜索，從而提供O（log n）訪問時間。

2）如果在.NET中覆蓋GetHashCode，則還應該覆蓋Equals方法。在.NET Dictionary和HashSet中，不能插入相同的項目。在一般情況下，散列衝突是不可避免的（除非你計算出完美的散列）。有幾種方法可以解決衝突。

3）關於衝突解決的更多信息，請參見http://en.wikipedia.org/wiki/Hash_table。

來源

2011-02-07 15:25:53

哈希表是一個數據結構。更多的信息可以在when looking for more general information找到。

1）列表中的默認搜索是線性的（所有元素都需要遍歷）。完美的哈希（無衝突）允許在最壞的情況下進行持續時間查詢。更多的衝突會導致查找速度降低。

2）哈希碰撞實際上是不可避免的時，散列一大組可能的密鑰的隨機子集。因此，大多數散列表實現都有一些衝突解決策略來處理這些事件。 .NET的Hashtable實現似乎使用double hashing。

3）只要你提供適當的哈希碼，這是你不應該擔心的。感興趣時，請閱讀關於散列表的wiki文章，其中解釋了幾種技術。

更新：有a difference在執行碰撞處理中的散列表和字典。顯然Hashtable是過時的，並且Dictionary或HashSet是優選的。

正如Jim Mischel所提到的，您應該重寫GetHashCode以及Equals。插入相同的項目是不可能的，但具有相同哈希碼的項目由您選擇的集合類型處理。

來源

2011-02-07 15:19:05

非常感謝您的回答。實際上，如果我將我的GetHashCode（）基於從DB檢索的主鍵字段，我不會將碰撞的更改帶到零嗎？但是，如果散列可以被複制，是不是它在自動碰撞的情況下處理重複散列/雙重散列值？在採訪中，聽起來好像我自己有責任自己做點什麼。 :)也許他們只是想聽說內部使用雙重哈希，我沒有說。 – Houman 2011-02-07 15:38:06

有關散列表和字典的面試問題

回答

相關問題