Объясните принцип работы хэш-таблицы и зачем она используется в программировании

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

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

1. Для заданного ключа вычисляется хэш-код.
2. Хэш-код преобразуется в индекс массива (обычно по модулю размера массива).
3. По этому индексу хранится значение или список значений (в случае коллизий).

Зачем используется:

• Быстрый поиск, вставка и удаление элементов — в среднем за O(1).
• Эффективное хранение пар ключ-значение.

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

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;
    map["apple"] = 5;
    map["banana"] = 3;

    std::cout << "apple: " << map["apple"] << std::endl;
    return 0;
}