🤔 Как устроена хеш таблица в unordered_map?

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

🚩Основные компоненты хеш-таблицы

🟠Массив "бакетов" (buckets)
Хеш-таблица состоит из массива бакетов, где каждый бакет содержит список элементов с одинаковым хеш-кодом.
🟠Функция хеширования (`std::hash<T>`)
Для определения, в какой бакет попадёт ключ, используется функция хеширования (std::hash<T>).
🟠Проверка коллизий
Если два разных ключа попадают в один бакет (коллизия), элементы сохраняются в связанном списке (чаще всего).
🟠Рехеширование
При переполнении таблицы (load_factor > порогового значения) количество бакетов увеличивается, и все элементы перераспределяются.

🚩Как работает поиск и вставка в `unordered_map`

Хеш-функция вычисляет хеш-код ключа

   std::hash<int> hash_fn;
   size_t hash_value = hash_fn(42); // Например, 23145123

Определяется индекс бакета

   size_t bucket_index = hash_value % bucket_count;

🚩Разрешение коллизий

Когда два ключа попадают в один бакет, возникают коллизии. std::unordered_map использует метод цепочек (separate chaining):
В каждом бакете хранится связанный список (или другой контейнер).
Если несколько элементов имеют одинаковый хеш, они добавляются в этот список.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap;

    myMap[1] = "One";  // Хеш-функция определит бакет
    myMap[2] = "Two";  // Если попадает в тот же бакет, создаётся список

    for (const auto& [key, value] : myMap) {
        std::cout << "Key: " << key << ", Value: " << value << '\n';
    }

    return 0;
}

🚩Рехеширование (увеличение количества бакетов)

Когда таблица заполняется, выполняется rehash (увеличение массива бакетов в 2 раза).
Load factor (load_factor()) показывает, насколько заполнена таблица:

std::unordered_map<int, std::string> myMap;
std::cout << "Load factor: " << myMap.load_factor() << '\n';

Ставь 👍 и забирай 📚 Базу знаний