Mi a komplexitása annak, hogy ellenőrizzük egy elem jelenlétét egy halmazban a legrosszabb esetben, amikor minden elem ugyanazzal a hash-sel rendelkezik?

A legrosszabb esetben, amikor minden elem a halmazban ugyanazzal a hash értékkel rendelkezik, az adatstruktúra, amelyet általában hash-táblaként valósítanak meg, láncolt listává degradálódik. Ez akkor fordul elő, mert minden elem ugyanabba a kosárba (bucket) kerül.

Ebben az esetben az elem létezésének ellenőrzése az összes elem átvizsgálását igényli ebben a kosárban, ami O(n) komplexitást eredményez, ahol n a halmazban lévő elemek száma.

Így a legrosszabb esetben az elem keresése a halmazban egy lineáris keresés a listában, nem pedig konstans idő, mint az átlagos esetben.