HashSet如何<T>。包含的速度比List <T> .Contains？

我有一個簡單的要求：我有數百萬個字符串，並且想要測試它們是否存在於一個小集合中。我對使用List<T> vs HashSet<T>這一套有疑問。HashSet如何<T>。包含的速度比List <T> .Contains？

當需求相反時，例如，你有100個字符串，需要檢查它們是否存在於一組數百萬字符串中，我完全理解HashSet<T>是最佳選擇。

但在我的情況下，似乎.NET對HashSet<T>調用Contains的時候，所以調用List<T>的Contains可能會更快，計算哈希值數百萬的（調用GetHashCode）？

任何人都可以解釋，如果這種假設是正確的？

2011-10-23 Muis

這些都不適合我 - 一個HashSet<string>聽起來像它可能是我最好的方法。

是的，.NET必須爲每個字符串計算哈希代碼 - 問題是隻要檢查候選集中數百個字符串中的每一個的相等性，這是否需要。

根據所有性能問題，你應該真的測試這個而不是猜測。例如，如果所有字符串的長度不同並且都很長，那麼Equals對每位候選人都很便宜，而GetHashCode可能需要很長時間。但是，如果所有字符串的長度均爲10，並且開頭的字符相同，那麼GetHashCode將相當便宜，但每個字符串相等性檢查都必須檢查所有這些常用前綴字符。這些更像你的實際情況？你的基準測試顯示了什麼？ 需要多快？這是爲什麼？

來源

2011-10-23 16:26:56

非常好的答案！我找到了HybridDictionary類，在這裏你可以將值存儲爲null，使它與我猜測的HashSet相同。 – Muis

@Joshua：如果沒有一些具體的性能數據，我不會使用非泛型的'HybridDictionary'類（用於將鍵映射到值，而不僅僅用於包含元素）。「List '和'HashSet '對你來說太慢了嗎？請注意，'HybridDictionary'不知道切換點的合理位置 - 這取決於實際的數據，以及Equals vs GetHashCode調用的代價。 –

我目前使用HashSet ，但有時它包含3個值，有時它包含數千個值，所以我在尋找類似於HybridHashset的東西，例如當item-count> 100時它會自動切換。我知道它不能準確計算'100'，但估計可能會足夠好。 – Muis

我認爲字典緩存鍵的哈希值，顯然只會計算一次您正在搜索的字符串的哈希值。我會補充一點，如果你的字符串是靜態的並且很少修改，你可以更快地對不可變列表進行排序並使用Array.BinarySearch，但是可能我不會這樣做，因爲它會使代碼太複雜（除非通過基準測試我證實它速度要快得多。）

來源

2011-10-23 16:31:26 xanatos

我想你誤解了這個問題。問題在於我搜索了數百萬個字符串，因此無法緩存任何內容。 – Muis

所以你的問題是：散列一個字符串，並通過散列搜索100個其他字符串或通過比較它直接搜索100次更快？那麼你必須對它進行基準測試。我不認爲突破點是固定的。 – xanatos

我想我找到了一個解決方案：HybridDictionary類，它在切點處自動切換。 – Muis

HashSet如何<T>。包含的速度比List <T> .Contains？

回答

相關問題