Jaka jest cecha szybkości wyszukiwania elementów w strukturze danych Dictionary?

W strukturze danych Dictionary (np. w C#) wyszukiwanie elementu po kluczu zazwyczaj ma złożoność amortyzowaną O(1), czyli jest bardzo szybkie i praktycznie stałe w czasie.

Osiąga się to dzięki użyciu tablicy haszującej, gdzie klucz jest przekształcany w kod hash, który pozwala na szybkie znalezienie indeksu w tablicy.

Jednak w najgorszym przypadku (np. przy dużej liczbie kolizji) czas wyszukiwania może się pogorszyć do O(n), gdzie n to liczba elementów, ale takie sytuacje są rzadkie przy dobrej dystrybucji funkcji hash.

Przykład wyszukiwania w Dictionary w C#:

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