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

Question

我需要组织大约3000个不同的文件,并在游戏过程中的不同时间检索.

我创建了自己的变量结构.我正在考虑在我的应用程序开始时创建一个"Dictionary",并在游戏开始之前简单地加载我的所有文件.

我想知道性能:有这么多条目的字典会导致我的应用程序变慢吗？大字典是否会使"TryGetValue"和"ContainsKey"运行得更慢？

感谢您的建议!

Answer 1

只要密钥具有良好分布的哈希值,TryGetValue和ContainsKey就应该非常快.

字典具有可索引的"桶"数.当它通过键添加或查找值时,它将获取GetHashCode()返回的值,再次将其向下散列为小于桶的数量(通常像模数一样简单,但实现未定义),并查看相关的桶.

该桶目​​前将具有零个或多个项目.字典将使用.Equals()将每个项目与密钥进行比较.

找到正确的桶的第一位将是恒定时间O(1).将密钥与桶中的密钥进行比较的第二位将是在线性时间O(n),其中n仅涉及该桶中的项目数,而不是整个集合中的项目数.

通常每个桶中应该有非常少的项目(桶的数量将增长以试图保持这种情况)因此操作基本上是恒定的时间.

但是,如果您的哈希码执行得不好,那么同一个桶中会有很多键.时间复杂度将越来越接近O(n),可以通过试验具有故意错误的GetHashCode的对象来看到,每次只返回0.在更糟糕的情况下,它比List更糟糕,因为List也是O(n),但是Dictionary有更多的开销.

这有什么意思你应该担心吗？不,即使是相对天真的散列方法也应该给出相对好的结果.如果你正在使用字符串键,那么它可能已经足够好了.如果您使用的是简单的内置类型,那么更是如此.

如果您确实发现访问字典的速度很慢,那么您需要注意这一点并修复GetHashCode()方法或创建IEqualityComparer(它允许您为GetHashCode()和Equals()定义外部规则以供使用字典,哈希集等).

最有可能的是,3000不算什么,一切都会好的.

Answer 2

3000个条目正在为一个Dictionary<>.这不会成为经济放缓的根源.

另一方面,在启动时将3000个不同的文件读入内存将会很慢.只有在需要时才将文件读入内存会更好,但之后将它们保存在内存中以便后续访问.

Answer 3

不,不会.它会消耗内存,但TryGetValue并ContainKey应该是相当快的词典是一个哈希表,并获得通过的关键要素是恒定的,它不依赖于元素的数量.