VB.NET中Dictionary(Of String,SomeReferenceType)的性能

Question

从/到Dictionary(Of String,SomeReferenceType)读取/添加值的性能如何取决于已输入的记录数？我的意思是,当n变大时,O(1),O(log n),O(n)或其他方式的时间会增加吗？

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？

Answer 1

从a获取项目的性能Dictionary受项目数量的影响很小.这些项目根据其哈希码分为多个桶,因此每个桶中通常只有一个或几个项目.该操作接近O(1)操作.

添加项目也接近O(1)操作.如果必须增加容量,您将获得性能损失,但平均值非常小.由于每次容量增加一倍,增加容量时移动的数据量实际上并不多.数据平均移动了1.3倍,因此每次添加的平均额外工作量减少到大约16个字节.

如果您知道Dictionary将获得多大,或者只是有一个合理的估计,您应该在创建它时使用它,以减少或消除增加容量的需要.