Akáto je zložitosť overenia prítomnosti prvku v set v najhoršom prípade, keď všetky prvky majú rovnaký hash?

V najhoršom prípade, keď všetky prvky v množine majú rovnaký hash, sa dátová štruktúra, zvyčajne implementovaná ako hash tabuľka, degraduje na spojený zoznam. To sa deje preto, lebo všetky prvky spadnú do jednej nádoby (bucket).

V takom prípade je overenie prítomnosti prvku potrebné prejsť všetky prvky v tejto nádobe, čo má zložitosť O(n), kde n je počet prvkov v množine.

Preto je v najhoršom prípade vyhľadávanie prvku v množine lineárne vyhľadávanie v zozname, a nie konštantný čas, ako v priemere.