字典與唯一性和性能

Question

列表以下是一個理論問題，但我想知道是否有拇指答案吧

的規則讓我們想象一下它實現了GetHashCode()和Equals()類方法。

因此它可以用作Dictionary<T>密鑰或HashSet<T>。

現在我要檢查針對的獨特的m個另一個列表N項的列表，如果所有的Ns的是對彼此以及對任何M.

因爲它們是字典的準備，我唯一隻需將所有Ms添加到字典中，然後遍歷N並檢查/添加它們，直到我做或不做失敗。

或者我可以將Ms放入List<T>，然後遍歷N，檢查是否相等並將它們添加到M列表中。

我從性能的角度來看待這個問題。取決於散列碼是如何精心選擇，一個ContainsKey()加上Add()將導致2（GetHashCode()，GetHashCode()）或4的函數調用（GetHashCode()，Equals()，GetHashCode()，Equals()）。

另一方面For循環，將只使用1個函數調用（如果使用IEquatable<T>接口，則可以使用Contains()），調用Equals()。

但是從寫作角度來看，Dictionary<T>或HashSet<T>似乎更直觀，因爲代碼會立即告訴您作者的目標（尋找唯一性）。

有沒有M和N的數量，你會選擇一個嗎？

獎金的問題：如果你的標準使用情況下，不希望的關鍵是已經存在，這將是更好的代碼只是嘗試將項添加到Dictionary<T>，趕上ArgumentException而不是使用ContainsKey()的？

Answer 1

假設您正在談論算法的漸近複雜性，這意味着N和M非常大。在這種情況下，調用Equals（）和GetHashCode（）函數的開銷（當然，假設它們是O（1））。如果你想比較一個算法與其他算法的漸近複雜度，那麼HashSet在一般情況下會給你最好的結果，因爲它對於像Contains這樣的函數具有O（1）複雜度。

但是，您首先需要將元素添加到哈希集。這可能會導致數組創建新數組和複製引用（如果我們在討論引用類型或值，如果我們正在討論值類型）。

List和Dictionary也是如此，當元素數小於某些內部容量時，它們在添加新項目時也具有O（1）複雜性，否則O（n）。因此，如果你有一個很好的散列函數，並且你不能對它們之間的輸入值進行比較的假設，那麼只需手動比較它們就可以降低複雜性，你應該使用HashSet。