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

從/向 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？

從 a 獲取項目的性能Dictionary受項目數量的影響很小。項目根據其雜湊碼分為桶，因此每個桶中通常只有一個或很少的項目。該操作接近於 O(1) 操作。

添加項目也接近於 O(1) 操作。如果必須增加容量，您將受到性能影響，但平均而言，這是非常小的。由於容量每次翻倍，增加容量時移動的數據量實際上並沒有那麼多。數據平均額外移動了 1.3 倍，因此每次添加的平均額外工作歸結為移動大約 16 個字節。

如果您知道將獲得多大Dictionary，或者只是有一個不錯的估計，您應該在創建它時使用它，以減少或消除增加容量的需要。

引用自：https://stackoverflow.com/questions/875222