Как работает хеш-таблица?

Хеш-таблица (hash table) — это структура данных, реализующая ассоциативный массив.

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

1. Хеширование. Для каждого ключа (key) вычисляется хеш-код (hash code) с помощью хеш-функции (hash function). Хеш-код — это целое число.
2. Индексирование. Хеш-код используется для определения индекса (index) в массиве (или векторе) внутренней структуры хеш-таблицы. Обычно индекс вычисляется как hash_code % array_size, где array_size — размер массива.
3. Хранение. По найденному индексу в массиве хранится связанное с ключом значение (value).

Проблемы и их решения:

• Коллизии. Различные ключи могут давать одинаковый хеш-код, и, следовательно, один и тот же индекс в массиве. Это называется коллизией.
  • Методы разрешения коллизий:
    • Метод цепочек (Separate Chaining): В каждой ячейке массива хранится список (список, вектор и т.п.) пар "ключ-значение". При коллизии новая пара добавляется в этот список. При поиске по индексу просматривается соответствующий список для нахождения нужного ключа.
    • Метод открытой адресации (Open Addressing): При коллизии ищется другая свободная ячейка в массиве по определенному правилу (пробирование).
      • Линейное пробирование (Linear Probing): Последовательно проверяются ячейки index + 1, index + 2, и т.д. по модулю размера массива.
      • Квадратичное пробирование (Quadratic Probing): Проверяются ячейки index + 1^2, index + 2^2, и т.д. по модулю размера массива.
      • Двойное хеширование (Double Hashing): Используется вторая хеш-функция для определения шага пробирования.

Преимущества:

• В среднем, операции вставки, удаления и поиска выполняются со сложностью O(1).

Недостатки:

• В худшем случае (например, при большом количестве коллизий или плохой хеш-функции) сложность операций может достигать O(n), где n — количество элементов.
• Требует дополнительной памяти (например, для списков при методе цепочек или для пробирования при открытой адресации).

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

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

int main() {
    // Создание хеш-таблицы (unordered_map)
    std::unordered_map<std::string, int> ages;

    // Вставка элементов
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    // Получение значения по ключу
    std::cout << "Alice's age: " << ages["Alice"] << std::endl;

    // Поиск элемента
    if (ages.count("Bob")) {
        std::cout << "Bob is in the map." << std::endl;
    }

    // Удаление элемента
    ages.erase("Charlie");

    return 0;
}