我有大约 3000 个不同的文件需要整理，并在游戏期间的不同时间检索。
我创建了自己的变量结构。我正在考虑在我的应用程序开始时创建一个“字典”，并在游戏开始之前加载我的所有文件。
我想知道性能：包含这么多条目的字典会导致我的应用程序变慢吗？大字典会使“TryGetValue”和“ContainsKey”运行得更慢吗？
感谢您的建议！
问问题
27877 次
7 回答
18
TryGetValue 和 ContainsKey 在该大小下应该非常快，只要密钥具有良好分布的哈希值。
字典具有可索引数量的“桶”。当它通过键添加或查找值时，它将获取 GetHashCode() 返回的值，再次对其进行哈希处理以小于存储桶的数量（通常像模一样简单，但未定义实现），并查看相关的存储桶。
存储桶当前将有零个或多个项目。字典将使用 .Equals() 将每个项目与键进行比较。
找到正确存储桶的第一步将是常数时间 O(1)。将键与桶中的键进行比较的第二位将在线性时间 O(n) 中进行，其中 n 仅与该桶中的项目数相关，而不与整个集合相关。
Generally there should be very few items in each bucket (the number of buckets will grow to try to keep this the case) so the operation is essentially constant time.
If however your hash codes are poorly implemented, there will be lots of keys in the same bucket. The time complexity will get closer and closer to O(n), as can be seen by experimenting with an object with a deliberately bad GetHashCode that just returns 0 every time. In its worse case it is worse than a List, since a List is also O(n), but Dictionary has more overhead.
Does any of this mean you should worry? No, even relatively naïve hashing methods should give relatively good results. If you're using a string key, then it's probably already going to be more than good enough. If you're using a simple built-in type, then even more so.
如果您确实发现访问字典很慢，那么您需要注意这一点并修复 GetHashCode() 方法或创建一个 IEqualityComparer（它允许您定义 GetHashCode() 和 Equals() 的外部规则以用于字典、哈希集等）。
不过，很可能，3000 不算什么，它会没事的。
于 2010-08-11T17:01:33.397 回答
14
3000 个条目对Dictionary<>. 这不会是放缓的根源。
另一方面，在启动时将 3000 个不同的文件读入内存会很慢。最好只在需要时将文件读入内存，然后将它们保存在内存中以供后续访问。
于 2010-08-11T16:48:22.423 回答
8
不，不会的。它会消耗内存，但TryGetValue应该ContainKey非常快，因为字典是一个哈希表，并且通过键访问元素是恒定的，它不依赖于元素的数量。
于 2010-08-11T16:49:35.570 回答
4
为字典键类型提供哈希码算法可以将哈希码相对均匀地分布在 Int32 空间中，哈希码查找不受字典大小的影响。
有关详细信息，请参阅http://en.wikipedia.org/wiki/Hashtable#Performance_analysis 。
于 2010-08-11T16:49:45.790 回答
1
.NET 中的字典使用哈希表查找方案，因此添加条目对查找性能的影响很小（如果有的话）。您将遇到的唯一问题可能是内存使用情况。包含 3000 个项目的字典将消耗大约 3000 倍于键和值类型所使用的存储空间。如果它只是一个没有巨大二进制 blob 的简单结构，那么 3000 是非常小的。
于 2010-08-11T16:49:14.027 回答
1
您的瓶颈将不是字典的性能，而是读取 3000 个文件。
于 2010-08-11T16:50:08.397 回答
1
与计算机的大多数事情（尤其是性能）一样，“It Depends (tm)”
这一切都取决于字典的实现。
它可以作为二叉树来完成，在这种情况下查找应该是 O(log2 N)，这意味着查找时间随着字典大小的增长而缓慢增长。
它可以作为一个哈希表来完成，理论上它是 O(1)，这意味着无论字典的大小如何，查找总是需要相同的时间，但这就是理论，并且取决于桶的数量和哈希码的质量。如果许多项目最终在同一个存储桶中，需要线性搜索，那么随着字典的增长，事情会大大减慢。
但是，字典必须增长超过 3000 几个数量级才能看到明显的差异。
于 2010-08-11T16:53:49.117 回答