Qual é a característica da velocidade de busca de elementos na estrutura de dados Dictionary?

Na estrutura de dados Dictionary (por exemplo, em C#), a busca de um elemento por chave geralmente tem uma complexidade amortizada de O(1), ou seja, muito rápida e praticamente constante no tempo.

Isto é alcançado através do uso de uma tabela de hash, onde a chave é transformada num código hash, que permite encontrar rapidamente o índice no array.

No entanto, no pior caso (por exemplo, com muitas colisões), o tempo de busca pode degradar-se para O(n), onde n é o número de elementos, mas tais situações são raras com uma boa distribuição da função hash.

Exemplo de busca em Dictionary em C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Busca em O(1)