'適當'集合用於在C＃.NET中獲取O（1）時間中的項目？

我做的事情的時候，如果我存儲一串字符串值，我希望能夠找到它們在O（1）時間較晚：'適當'集合用於在C＃.NET中獲取O（1）時間中的項目？

foreach (String value in someStringCollection) 
{ 
    someDictionary.Add(value, String.Empty); 
}

這樣一來，我可以舒適地進行不變 - 時間上晚於這些字符串值查找，如：

if (someDictionary.containsKey(someKey)) 
{ 
    // etc 
}

不過，我覺得我是通過使值的String.Empty作弊。有沒有更適合我應該使用的.NET集合？

來源

2008-12-01 Pandincus

如果您使用.Net 3.5，請嘗試HashSet。如果您不使用.Net 3.5，請嘗試C5。否則，你當前的方法是可以的（bool，因爲@leppie表示更好，或者不像@JonSkeet所暗示的那樣，dun dun dun！）。

HashSet<string> stringSet = new HashSet<string>(someStringCollection); 

if (stringSet.Contains(someString)) 
{ 
    ... 
}

來源

2008-12-01 14:28:08 user7116

Arg，你打我！ – leppie 2008-12-01 14:29:03

這聽起來不錯，謝謝！我甚至沒有注意到HashSet。 – Pandincus 2008-12-01 15:11:24

可以在.NET 3.5使用HashSet<T>，否則我只想堅持到你當前的方法（其實我寧願Dictionary<string,bool>但一個並不總是那麼奢侈）。

來源

2008-12-01 14:28:33 leppie

你可能想要添加的東西是初始大小到你的散列。我不確定C＃是否以不同於Java的方式實現，但它通常具有一些默認大小，如果添加更多，則會擴展集合。然而，正確大小的散列對於儘可能接近O（1）很重要。目標是在每個桶中準確地獲得1個入口，而不會使其變得非常龐大。如果你做了一些搜索，我知道有一個建議的比例用於確定散列表的大小，假設你事先知道要添加多少元素。例如，「哈希值應該是1.8倍要添加的元素的大小」（不是真正的比例，只是一個例子）。

從Wikipedia：

憑藉良好的散列函數，散列表可以通常含有約 70％-80％一樣多的元素它表槽，並且仍然表現良好。根據碰撞分辨率機制，性能開始可能會逐漸受損或劇增，因爲更多元素被添加到。爲了解決這個問題，當加載因子超過某個閾值時，對於分配新的更大的表是必要的，並且將原表的所有內容添加到這個新表中。在 Java的HashMap類中，例如，默認的加載因子閾值爲0.75。

來源

2008-12-01 14:50:32 CodingWithSpike

我應該讓這個問題，因爲我經常看到這個問題。是什麼讓你覺得字典是O（1）？從技術上講，唯一可能是類似O（1）的東西是使用整數索引值訪問標準的整數索引固定邊界數組（在數組中沒有以這種方式實現查找）。

假設如果它看起來像一個數組引用它是O（1）當「索引」是一個值，必須以某種方式被查找，但是在幕後，意味着它不可能是O （1）計劃，除非你很幸運能夠獲得一個沒有衝突的數據（可能還有很多浪費的單元）。（1）[不是在這個特定的問題上，但我確實看起來在他們身邊]，沒有正當理由或解釋什麼是確保O（1）實際上已經實現。

嗯，我想這是一個體面的問題。在我發表這篇評論後，我會這樣做。

來源

2008-12-02 03:10:33 orcmid

'適當'集合用於在C＃.NET中獲取O（1）時間中的項目？

回答

相關問題