Что такое хеш-таблица (hash map) и как она реализована в C++?

Хеш-таблица (ассоциативный массив) — это структура данных, обеспечивающая быстрый доступ к значению по ключу в среднем за O(1). В стандартной библиотеке C++ представлена контейнерами std::unordered_map, std::unordered_set, std::unordered_multimap, std::unordered_multiset.

Принцип работы:

1. Хеш-функция: Ключ передается в хеш-функцию (std::hash<T> по умолчанию или пользовательская), которая возвращает числовой хеш-код.
2. Индексирование: Хеш-код отображается на индекс в массиве «корзин» (buckets), обычно с помощью операции hash % bucket_count.
3. Разрешение коллизий: Если разные ключи попали в одну корзину (коллизия), элементы хранятся в виде связного списка (метод цепочек) внутри этой корзины.

Пример использования std::unordered_map:

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Объявление хеш-таблицы (ключ - std::string, значение - int)
    std::unordered_map<std::string, int> phonebook;

    // Вставка элементов. Средняя сложность O(1).
    phonebook["Alice"] = 12345;
    phonebook.insert({"Bob", 67890});
    phonebook.emplace("Charlie", 11111);

    // Поиск по ключу. Средняя сложность O(1).
    auto it = phonebook.find("Alice");
    if (it != phonebook.end()) {
        std::cout << "Alice's number: " << it->second << 'n'; // 12345
    }

    // Прямой доступ через operator[]. Если ключа нет, он будет создан.
    std::cout << phonebook["Bob"]; // 67890

    // Итерация по всем элементам (порядок не гарантирован!)
    for (const auto& [name, number] : phonebook) {
        std::cout << name << ": " << number << 'n';
    }
}

Важные особенности и настройка в C++:

• Производительность зависит от качества хеш-функции (минимизация коллизий) и коэффициента загрузки (load factor).
• Коэффициент загрузки — это size() / bucket_count(). При превышении max_load_factor() происходит рехеширование — увеличение числа корзин и перераспределение всех элементов, что операция дорогая O(n).
• Пользовательская хеш-функция и компаратор:

  struct MyKey { std::string a, b; };
  struct MyKeyHash {
      std::size_t operator()(const MyKey& k) const {
          return std::hash<std::string>()(k.a) ^
                 (std::hash<std::string>()(k.b) << 1);
      }
  };
  struct MyKeyEqual {
      bool operator()(const MyKey& lhs, const MyKey& rhs) const {
          return lhs.a == rhs.a && lhs.b == rhs.b;
      }
  };
  std::unordered_map<MyKey, int, MyKeyHash, MyKeyEqual> my_map;

• В худшем случае (все ключи попали в одну корзину) сложность деградирует до O(n).