Какова сложность проверки наличия элемента в set в худшем случае, когда все элементы имеют одинаковый хэш?

В худшем случае, когда все элементы в set имеют одинаковый хэш, структура данных, обычно реализованная как хеш-таблица, деградирует до связного списка. Это происходит потому, что все элементы попадают в одну корзину (bucket).

В таком случае проверка наличия элемента требует перебора всех элементов в этой корзине, что даёт сложность O(n), где n — количество элементов в set.

Таким образом, в худшем случае поиск элемента в set — это линейный поиск по списку, а не константное время, как в среднем случае.