Performance of Dictionary(Of String, SomeReferenceType) in VB.NET

Question

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)

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?

Answer 1

Dictionary is implemented with Hastables - Thus O(1).

SortedDictionary is implemented with binary trees (red/black) - Thus O(log n)

SortedList is implemented with lists+binary search - Thus O(n)

All dictionaries increase their size automatically (performance is O(n) here but this doesn't happen often because the size is precomputed intelligently, so the approximate performance is O(1) anyway - See this)

Just google them and look in the microsoft documentation.

Answer 2

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.

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.

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.