Верно ли, что время поиска элемента в unordered_set является константным?

Да, в среднем время поиска элемента в std::unordered_set является константным — O(1).

Это достигается за счет использования хеш-таблицы. Ключ элемента хешируется, и хеш используется для определения позиции элемента в таблице. Если хеш-функция хорошая и количество коллизий минимально, доступ к элементу происходит напрямую.

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

Факторы, влияющие на производительность:

• Качество хеш-функции.
• Коэффициент загрузки (load factor) хеш-таблицы (отношение количества элементов к количеству бакетов). Высокий коэффициент загрузки увеличивает вероятность коллизий.

cpp