字典<>中的条目是否有限制? [英] Is there a limit to entries in a Dictionary<>?

问题描述

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

I have about 3000 different files I need to organize, and retrieve at different times during the game.

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

I created my own struct of variables. I was thinking about creating a "Dictionary " at the beginning of my application, and simply loading all my files before the game starts.

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

I'm wondering about performance: will a dictionary with this many entries cause my application to be slow? Would a large dictionary make "TryGetValue" and "ContainsKey" run slower?

感谢您的建议！

推荐答案

TryGetValue和ContainsKey在该大小下应该非常快，只要密钥具有良好分布的散列即可.

TryGetValue and ContainsKey should be pretty fast at that size, as long as the key has well distributed hashes.

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

A Dictionary has an indexable number of "buckets". When it adds or looks for a value by a key it will take the value returned by GetHashCode(), hash it down again to be less than the number of buckets (generally something simple like modulo, but the implementation isn't defined), and look in the relevant bucket.

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

The bucket will currently have zero or more items. The dictionary will compare each item with the key using .Equals().

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

The first bit of finding the right bucket is going to be in constant time O(1). The second bit of comparing the key with the keys in the bucket is going to be in lineary time O(n) where n relates only to the number of items in that bucket, not in the whole collection.

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

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.

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

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()定义外部规则)用于字典，哈希集等).

If you do find that accessing the dictionary is slow though, then you want to pay attention to this and either fix the GetHashCode() method or create an IEqualityComparer (which lets you define outside rules for GetHashCode() and Equals() for use with dictionaries, hashsets, etc).

虽然很可能3000都不是，这会没事的.

Most likely though, 3000 is nothing, it'll be fine.

这篇关于字典<>中的条目是否有限制?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！