Wat is de eigenschap van de zoeksnelheid van elementen in de gegevensstructuur Dictionary?

In de datastructuur Dictionary (bijvoorbeeld in C#) heeft het zoeken van een element op sleutel meestal een geamortiseerde complexiteit van O(1), dat wil zeggen, zeer snel en praktisch constant in de tijd.

Dit wordt bereikt door gebruik te maken van een hashtabel, waarbij de sleutel wordt omgezet in een hash-code, waarmee snel de index in de array kan worden gevonden.

In het ergste geval (bijvoorbeeld bij veel collisions) kan de zoektijd afnemen tot O(n), waarbij n het aantal elementen is, maar dergelijke situaties zijn zeldzaam bij een goede verdeling van de hashfunctie.

Voorbeeld van zoeken in Dictionary in C#:

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