词典中的条目是否有限制<>？

Question

我需要整理大约3000个不同的文件，并在游戏中的不同时间进行检索。

我创建了自己的变量结构。我当时正在考虑创建一个“词典”在我的应用程序开始时，只需在游戏开始之前加载我的所有文件即可。

我想知道性能：具有这么多条目的字典会导致我的应用程序运行缓慢吗？大型词典会使“ TryGetValue”和“ ContainsKey”的运行速度变慢吗？

感谢您的建议！

Answer 1

词典具有可索引数量的“存储桶”。当它通过键添加或查找值时，它将采用GetHashCode（）返回的值，再次对其进行哈希处理，使其小于存储桶的数量（通常是简单的模运算，但未定义实现），并查看相关的存储桶。

该存储桶当前将有零个或多个项目。字典将使用.Equals（）将每个项目与键进行比较。

找到正确存储桶的第一位将是在恒定时间O（1）中。将密钥与存储桶中的密钥进行比较的第二位将是线性时间O（n），其中n仅与该存储桶中的项目数有关，而与整个集合无关。

通常，每个存储桶中的物品很少（存储桶的数量会不断增加，以保持这种情况），因此操作基本上是恒定时间。

但是，如果您的哈希码实现不佳，则同一存储桶中将有很多键。时间复杂度将越来越接近O（n），这可以通过对一个故意具有错误GetHashCode的对象进行实验来看出，该对象每次仅返回0。在最坏的情况下，它比列表更差，因为列表也是O（n），但是字典的开销更大。

这是否意味着您应该担心？不，即使是相对幼稚的哈希方法也应能得出相对较好的结果。如果您使用的是字符串键，那么它可能已经足够好了。如果您使用的是简单的内置类型，则更多。

如果您确实发现访问字典的速度很慢，则需要注意这一点，并修复GetHashCode（）方法或创建IEqualityComparer（可让您为定义GetHashCode（）和Equals（）的外部规则与字典，哈希集等配合使用）。

尽管最有可能的是3000，但是它会没事的。

Answer 2

另一方面，在启动时将3000个不同的文件读取到内存中，

将很慢。仅在需要时才将文件读取到内存中会更好，但之后将它们保留在内存中以供后续访问。

Answer 3

Answer 4

请参见http://en.wikipedia.org/wiki/Hashtable#Performance_analysis以获取更多详细信息。

Answer 5

添加更多键不会降低TryGetValue和ContainsKey的速度-它们是O(1)操作。

Answer 6

Answer 7

Answer 8

全部取决于字典的实现。

可以作为二叉树来完成，在这种情况下，查找应该为O（log2 N），这意味着查找时间随着字典大小的增长而缓慢增长。

它可以作为哈希表来完成，从理论上讲，它是O（1），这意味着无论字典的大小如何，查找总会花费相同的时间，但这是理论，并且取决于关于存储桶的数量和哈希码的质量。如果许多项目都放在同一个存储桶中，需要进行线性搜索，则随着字典的增长，事情将会大大减慢。

但是，在您看到明显的差异之前，字典必须超过3000个数量级。