词典（串，SomeReferenceType）在VB.NET性能 [英] Performance of Dictionary(Of String, SomeReferenceType) in VB.NET

问题描述

如何已经进入从/阅读/添加值词典（串，SomeReferenceType）依靠的记录数的表现？我的意思是，时间的增加为O（1），O（log n）的，为O（n）当n去大，或以其他方式？

How does performance for reading/adding values from/to Dictionary(Of String, SomeReferenceType) depend on the number of records already entered? I mean, does time increase as O(1), O(log n), O(n) when n goes to be large, or in some other way?

Dim index As New Dictionary(Of String, SomeReferenceType)

' N entries added in a loop
' ...

Dim id As Integer = 123456789 ' 9-digit number
Dim key As String = id.ToString()
Dim value As New SomeReferenceType

index(key) = value ' Need to estimate this
value = index.TryGetValue(key) ' and this operations depending on N (for large N)

如果出现内存不足

此外，会发生什么？我们是否应该设置字典的能力进入的元素，以避免在复制它没有足够的内存空间过吗？多久这个操作（复制字典，如果需要一个新的地方）采取取决于n？

Also, what happens if there is lack of memory? Should we set capacity of dictionary before entering elements to avoid copying it in case there is not enough memory space? How long does this operation (copy dictionary to a new place if needed) take depending on N?

推荐答案

获取从字典项性能受项目的数量非常少。该项目共分为水桶accoding其散列code，所以一般都是在每个桶只有一个或很少的项目。该操作是接近O（1）操作。

The performance for getting an item from a Dictionary is affected very little by the number of items. The items are divided into buckets accoding to their hash code, so there are generally only a single or very few items in each bucket. The operation is close to a O(1) operation.

添加项目还靠近一个O（1）操作。如果容量必须增加，你会得到一个性能损失，但平均，这是非常小的。随着生产能力的每一次双打，数据时提高了容量移动量实在不算多。该数据是由平均移动1.3倍的额外，因此对于每一个的平均额外工作添加归结为移动约16个字节。

Adding items is also close to an O(1) operation. If the capacity has to be increased you will get a performance hit, but by average that is very small. As the capacity doubles each time, the amount of data that is moved when increasing the capacity is really not that much. The data is by average moved 1.3 times extra, so the average extra work for each add comes down to moving about 16 bytes.

如果你知道如何大词典将得到，或者只是有一个体面的估计，你应该使用，当你创建它，以减少或elliminate需要增加的能力。

If you know how large the Dictionary will get, or just have a decent estimate, you should use that when you create it, to reduce or elliminate the need to increase the capacity.

这篇关于词典（串，SomeReferenceType）在VB.NET性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！