.net - 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

从 Dictionary 获取项目的性能受项目数量的影响很小。项目根据其哈希码被分成桶，因此每个桶中通常只有一个或很少的项目。该操作接近于 O(1) 操作。

添加项目也接近 O(1) 操作。如果必须增加容量，您的性能会受到影响，但平均而言，这种影响非常小。随着容量每次增加一倍，增加容量时移动的数据量真的没有那么多。数据平均移动了 1.3 倍，因此每次添加的平均额外工作归结为移动大约 16 个字节。

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