Каква е сложността на проверката за наличие на елемент в set в най-лошия случай, когато всички елементи имат еднакъв хеш?

В най-лошия случай, когато всички елементи в множеството имат еднакъв хеш, структурата от данни, обикновено реализирана като хеш таблица, се деградира до свързан списък. Това се случва, защото всички елементи попадат в една и съща кошница (bucket).

В такъв случай проверката за наличие на елемент изисква обхождане на всички елементи в тази кошница, което води до сложност O(n), където n е броят на елементите в множеството.

Следователно, в най-лошия случай, търсенето на елемент в множеството е линейно търсене в списъка, а не константно време, както в средния случай.