Kolika je složenost provere prisustva elementa u skupu u najgorem slučaju, kada svi elementi imaju isti hash?

У најгорем случају, када сви елементи у скупу имају исти хеш, структура података, обично реализована као хеш табела, деградира у повезану листу. Ово се дешава јер сви елементи падају у исту корпу (bucket).

У таквом случају, провера постојања елемента захтева преглед свих елемената у тој корпи, што даје сложеност O(n), где n представља број елемената у скупу.

Стога, у најгорем случају, претрага елемента у скупу је линеарна претрага по листи, а не константно време као у просечном случају.