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

Хеш-таблица — это структура данных, которая хранит пары ключ-значение и обеспечивает очень быстрый доступ к данным по ключу, обычно за время близкое к O(1).

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

• Ключ преобразуется в индекс массива с помощью хеш-функции.
• По этому индексу хранится значение или список значений (в случае коллизий).
• При коллизиях (когда разные ключи дают одинаковый индекс) используется метод разрешения коллизий, например, цепочки (linked list) или открытая адресация.

Отличия от других структур ключ-значение:

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

Пример на 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; // Выведет 5
    return 0;
}