字典<>中的條目是否有限制？

我需要組織大約3000個不同的文件，並在遊戲過程中的不同時間進行檢索。字典<>中的條目是否有限制？

我創建了我自己的變量結構。我正在考慮在應用程序開始時創建一個「字典」，並且在遊戲開始前簡單加載所有文件。

我想知道性能：會有這麼多條目的字典會導致我的應用程序變慢？大字典會使「TryGetValue」和「ContainsKey」運行速度變慢嗎？

感謝您的建議！

來源

2010-08-11 theoneawaited

嘗試一下，衡量一下，看看！ – Brian 2010-08-11 17:05:58

只要密鑰散佈得很好，TryGetValue和ContainsKey的大小應該相當快。

詞典具有可索引數量的「桶」。當它通過鍵添加或查找值時，它將採用由GetHashCode（）返回的值，再次將其哈希值降低到小於桶的數量（通常是一些簡單的模數，但實現未定義），並查看相關的存儲桶。

存儲桶當前有零個或多個項目。字典將使用.Equals（）將每個項目與鍵進行比較。

尋找合適的存儲桶的第一個位置將在恆定的時間O（1）。比較密鑰和桶中的密鑰的第二個比特將在線性時間O（n）中，其中n僅涉及該桶中的項目數量，而不是整個集合中的項目數量。

通常，每個桶中應該只有很少的項目（桶的數量將增長以試圖保持這種情況），因此操作本質上是恆定的。

但是，如果你的哈希代碼執行得不好，那麼在同一個桶中將會有很多密鑰。時間複雜度將越來越接近O（n），這可以通過試驗一個故意不好的GetHashCode（每次只返回0）的對象來看出。在最糟糕的情況下，它比List更糟糕，因爲List也是O（n），但Dictionary有更多的開銷。

這是否意味着你應該擔心？不，即使相對天真的哈希方法也應該給出相對較好的結果。如果你使用的是字符串鍵，那麼它可能已經不夠好了。如果您使用的是簡單的內置類型，那麼更是如此。

如果您發現訪問字典的速度很慢，那麼您需要注意這一點，並修復GetHashCode（）方法或創建一個IEqualityComparer（它允許您爲GetHashCode（）和Equals（）用於字典，哈希集等）。

雖然很可能，但3000沒什麼了，它會沒事的。

來源

2010-08-11 17:01:33

3000個條目爲Dictionary<>擺弄。這不會成爲經濟放緩的根源。

在啓動時將3000個不同的文件讀入內存，另一方面，將會變慢。只有在需要的時候才能將文件讀入內存，但之後將其保存在內存中供後續訪問使用會更好。

來源

2010-08-11 16:48:22

既然他提到了一個遊戲，那麼這個正常的規則可能就不適用了。根據他們在什麼時候加載以及他們有多大，最好在啓動啓動屏幕後面加載它們，而不是在Ashe試圖殺死一個Deadite時...... – AllenG 2010-08-11 16:54:35

@AllenG，好點。 – 2010-08-11 17:04:28

可以說，他們可以在啓動時產生一個後臺線程來執行這個過程。 – 2010-08-11 17:30:37

.NET中的字典使用散列表查找方案，因此添加條目對查找性能的影響很小（如果有的話）。您將遇到的唯一問題可能是內存使用情況。一個包含3000個項目的字典將大約消耗密鑰加上值類型使用的存儲的3000倍。如果它只是一個沒有巨大二進制斑點的簡單結構，那麼3000就是極小的。

來源

2010-08-11 16:49:14 recursive

不，它不會。它會消耗內存，但TryGetValue和ContainKey應該是相當快的，因爲字典是散列表，並且按鍵對元素的訪問是恆定的，並且不依賴於元素的數量。

來源

2010-08-11 16:49:35

+1 - 好的答案 – JonH 2010-08-11 16:53:29

爲字典密鑰類型提供散列碼算法可以在整個Int32空間中相對均勻地散佈散列碼，散列碼查找不受字典大小的影響。

查看http://en.wikipedia.org/wiki/Hashtable#Performance_analysis瞭解更多詳情。

來源

2010-08-11 16:49:45

+1指出這隻有在散列未被破壞時纔有效。 – 2010-08-11 16:51:35

您的瓶頸不會是字典的性能，而是3000個文件的讀取。

來源

2010-08-11 16:50:08 AndrewC

由於與計算機（和特別性能）大多數事情一樣，「這取決於（TM）」

這一切都取決於字典的FPGA實現。

它可以作爲一個二叉樹來完成，在這種情況下，查找應該是O（log2N），這意味着查找時間隨着字典大小的增長而緩慢增長。

它可以做成一個哈希表，理論上它是O（1），這意味着無論字典的大小，查找總是會花費相同的時間量，但這就是理論，並且取決於桶的數量和散列碼的質量。許多項目都在同一個桶中，需要線性搜索，隨着字典的增長，事情會顯着減慢。

但是，在你看到明顯的差異之前，字典必須增長超過3000個數量級。

來源

2010-08-11 16:53:49

字典<>被指定爲使用散列表。 – 2010-08-11 18:20:52

有一個限制，但3000遠遠沒有。 Dictionary<>使用Object.GetHashCode()來標記其密鑰，該密鑰返回int。因此，在碰撞之前，您最多可以存儲2^32（4,294,967,296）個鍵。但是，由於.Net的哈希碼通常會被計算出來，因此在接近這個幻數時可能會出現很多碰撞。

添加更多密鑰不會減慢TryGetValue和ContainsKey - 它們是O(1)操作。

來源

2010-08-11 16:55:19

你最後兩句話衝突。如果兩個鍵相互碰撞，查找一個比使用唯一散列碼的鍵花費的時間更長。 – 2010-08-11 16:58:48

與通常計算.NET的哈希代碼的方式無關，以及與基本數學有關的一切。第一，如果你有超過2^32個可能的值（大多數類型都是真的），那麼就不可能保證唯一性，除非你事先知道這些值並且可以創建一個完美的散列。另外，字典不會從佔用16GB的指針空間開始，因此它可以有2^32個插槽（如果不是ref類型存儲，它可以更多），但是會減少它，所以更多的衝突。儘管如此，通過分散位，碰撞通常很少。一些碰撞不會傷害太多。 – 2010-08-11 17:07:56

字典<>中的條目是否有限制？

回答

相關問題