Como é determinada a complexidade da operação de busca de um elemento por chave em um dicionário?

A complexidade de procurar um elemento por chave num dicionário é geralmente considerada próxima de O(1), graças ao uso de tabelas de dispersão. Isso significa que o tempo de busca não depende do número de elementos no dicionário.

No entanto, no pior caso (por exemplo, em colisões de hash), a complexidade pode aumentar até O(n), onde n é o número de elementos. Mas as implementações modernas de dicionários usam métodos eficientes para resolver colisões, portanto, na prática, a busca é muito rápida.

Exemplo em C#:

var dict = new Dictionary<int, string>();
dict[1] = "one";
string value = dict[1]; // Busca por chave — aproximadamente O(1)