В каких случаях время поиска элемента в std::unordered_set может превысить константную сложность?

The search time for an element in std::unordered_set is usually considered amortized constant time (O(1)), but in some cases, it can significantly deteriorate:

• Hash function collisions: If the hash function poorly distributes elements, many keys will end up in the same bucket, and the search will turn into a linear search.
• Hash function attacks: An attacker can deliberately choose data that causes collisions, leading to performance degradation.
• Container implementation: In rare cases, if the container is unbalanced or does not perform timely rehashing, performance drops.

To minimize risks, it is recommended to use high-quality hash functions and, if necessary, adjust container parameters (such as table size and load factor).