Как хранятся объекты в std::unordered_map

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

std::unordered_map — это контейнер из стандартной библиотеки C++, который реализует ассоциативный массив на основе хеш-таблицы. В отличие от std::map, который хранит элементы в отсортированном порядке, std::unordered_map не гарантирует порядок элементов, но обеспечивает более быстрый доступ к данным.

Структура хранения

1. Хеш-таблица: Основой std::unordered_map является хеш-таблица. Это структура данных, которая использует хеш-функцию для вычисления индекса, по которому будет храниться элемент.

2. Корзины (buckets): Хеш-таблица состоит из множества корзин. Каждая корзина может содержать один или несколько элементов. Элементы, которые имеют одинаковый хеш-код, попадают в одну и ту же корзину.

3. Хеш-функция: Это функция, которая принимает ключ и возвращает целое число (хеш-код). Хеш-код используется для определения, в какую корзину поместить элемент. В std::unordered_map по умолчанию используется стандартная хеш-функция, но её можно переопределить.

4. Разрешение коллизий: Коллизия возникает, когда два разных ключа имеют одинаковый хеш-код. std::unordered_map использует метод цепочек для разрешения коллизий, где элементы с одинаковым хеш-кодом хранятся в виде связного списка в одной корзине.

Пример кода

#include <iostream>
#include <unordered_map>
#include <string>
​
int main() {
    // Создаем unordered_map с ключами типа std::string и значениями типа int
    std::unordered_map<std::string, int> umap;
​
    // Вставляем элементы в unordered_map
    umap["apple"] = 1;
    umap["banana"] = 2;
    umap["orange"] = 3;
​
    // Доступ к элементам по ключу
    std::cout << "apple: " << umap["apple"] << std::endl; // Выводит значение, связанное с ключом "apple"
​
    // Перебор всех элементов в unordered_map
    for (const auto& pair : umap) {
        std::cout << pair.first << ": " << pair.second << std::endl; // Выводит ключ и значение
    }
​
    return 0;
}

Комментарии к коду

• #include <unordered_map>: Подключает заголовочный файл, необходимый для использования std::unordered_map.
• std::unordered_map<std::string, int> umap;: Создает объект unordered_map, где ключи — строки, а значения — целые числа.
• umap["apple"] = 1;: Вставляет элемент с ключом "apple" и значением 1. Хеш-функция вычисляет хеш-код для строки "apple", чтобы определить, в какую корзину поместить элемент.
• std::cout << "apple: " << umap["apple"] << std::endl;: Получает значение, связанное с ключом "apple". Это операция поиска, которая выполняется за амортизированное время O(1).
• for (const auto& pair : umap): Перебирает все элементы в unordered_map. Порядок элементов не гарантируется.

Применение

std::unordered_map используется, когда требуется быстрый доступ к элементам по ключу, и порядок элементов не имеет значения. Это делает его идеальным для задач, где важна производительность операций поиска, вставки и удаления.