Qual è la complessità di verificare la presenza di un elemento in un set nel caso peggiore, quando tutti gli elementi hanno lo stesso hash?

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

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

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