¿Cuál es la complejidad de verificar la presencia de un elemento en un conjunto en el peor caso, cuando todos los elementos tienen el mismo hash?

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

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

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