Какое время доступа к элементу хеш-таблицы (std::unordered_map)?

В стандартной библиотеке C++ хеш-таблица представлена контейнером std::unordered_map. Сложность доступа к элементу по ключу (оператор [] или метод find) зависит от состояния таблицы.

• Средний случай: O(1). Достигается при хорошей хеш-функции, равномерно распределяющей ключи по корзинам (buckets), и умеренном коэффициенте загрузки (load factor).
• Худший случай: O(n). Возникает при большом количестве коллизий, когда множество ключей попадает в одну корзину, и поиск превращается в линейный обход списка в этой корзине.

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

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> phonebook = {
    {"Alice", 12345},
    {"Bob", 67890}
};

// Средний случай ~O(1)
int number = phonebook["Alice"];

auto it = phonebook.find("Bob"); // Поиск, тоже ~O(1)

Ключевые параметры std::unordered_map:

1. Хеш-функция: Задается как параметр шаблона. Для пользовательских типов ее нужно определять.
2. Коэффициент загрузки (max_load_factor): Определяет, когда произойдет рехеширование (увеличение количества корзин). По умолчанию ~1.0.
3. Аллокатор и функция сравнения ключей на равенство.