Mi jellemzi a keresési sebesség a Dictionary adatstruktúrában?

A Dictionary adatszerkezetben (például C#-ban) az elem kulcs szerinti keresése általában amortizált O(1) komplexitással rendelkezik, azaz nagyon gyors és gyakorlatilag állandó időben történik.

Ez a hash-tábla használatával érhető el, ahol a kulcsot hash-kódra alakítják, ami lehetővé teszi a gyors index megtalálását a tömbben.

Azonban a legrosszabb esetben (például sok ütközés esetén) a keresési idő O(n)-re csökkenhet, ahol n az elemek száma, de ilyen helyzetek ritkák jó hash-függvény eloszlás esetén.

Példa a Dictionary keresésére C#-ban:

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