Производительность словаря (Of String, SomeReferenceType) в VB.NET

Question

Как производительность чтения / добавления значений из / в словарь (Of String, SomeReferenceType) зависит от количества уже введенных записей? Я имею в виду, увеличивается ли время как O (1), O (log n), O (n), когда 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, или просто имеете приличную оценку, вы должны использовать ее при создании, чтобы уменьшить или устранить необходимость увеличения емкости.

Answer 2

Dictionary реализовано с помощью Hastables - таким образом O (1).

SortedDictionary реализовано с помощью двоичных деревьев (красный / черный) - Таким образом, O (log n)

SortedList реализовано с помощью списков + бинарный поиск - таким образом O (n)

Все словари автоматически увеличивают свой размер (здесь производительность равна O (n), но это случается не часто, поскольку размер предварительно вычисляется интеллектуально, поэтому приблизительная производительность в любом случае равна O (1) - см. this )

Просто погуглите их и посмотрите в документации Microsoft.