¿Cuál es la característica de la velocidad de búsqueda de elementos en la estructura de datos Dictionary?

En la estructura de datos Dictionary (por ejemplo, en C#), la búsqueda de un elemento por clave generalmente tiene una complejidad amortizada de O(1), es decir, muy rápida y prácticamente constante en el tiempo.

Esto se logra mediante el uso de una tabla hash, donde la clave se transforma en un código hash, que permite encontrar rápidamente el índice en el array.

Sin embargo, en el peor de los casos (por ejemplo, con muchas colisiones), el tiempo de búsqueda puede degradarse a O(n), donde n es el número de elementos, pero tales situaciones son raras con una buena distribución de la función hash.

Ejemplo de búsqueda en Dictionary en C#:

var dict = new Dictionary<string, int>();
dict["apple"] = 5;
int value = dict["apple"]; // Búsqueda en O(1)