Jaká je složitost kontroly přítomnosti prvku v množině v nejhorším případě, když mají všechny prvky stejný hash?

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

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

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