Когда возникает самый неблагоприятный случай поиска в unordered_set?

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