Как работает поиск элемента в хеш-таблице (например, в std::unordered_map)?

Поиск в хеш-таблице, такой как std::unordered_map, основан на вычислении хеш-кода ключа. Алгоритм поиска по ключу k:

1. Вычисление хеша: Ключ k передаётся в объект хеш-функции (по умолчанию std::hash<Key>). Функция возвращает значение типа std::size_t.
2. Определение бакета: Полученный хеш преобразуется в индекс массива бакетов (обычно через операцию hash % bucket_count). Этот индекс указывает на конкретный бакет (bucket) — контейнер (чаще всего односвязный список), в котором хранятся элементы.
3. Линейный поиск в бакете: В найденном бакете выполняется последовательное сравнение ключей всех элементов с искомым ключом k с помощью функции сравнения на равенство (по умолчанию std::equal_to<Key>). Поиск прекращается при первом совпадении.

Сложность: При хорошей, равномерно распределяющей хеш-функции и низком коэффициенте нагрузки (load factor) средняя сложность поиска — O(1). В худшем случае (все ключи попадают в один бакет из-за коллизий или плохой хеш-функции) сложность вырождается до O(n), где n — количество элементов в этом бакете.

Пример на C++:

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

int main() {
    std::unordered_map<std::string, int> fruitMap = {{"apple", 5}, {"banana", 3}, {"orange", 8}};

    // Поиск элемента по ключу "apple"
    auto it = fruitMap.find("apple");
    // Внутри find:
    // 1. Вычисляется std::hash<std::string>("apple").
    // 2. Определяется номер бакета.
    // 3. В этом бакете ищется пара с ключом "apple".

    if (it != fruitMap.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << 'n'; // Found: apple -> 5
    }
    return 0;
}

Методы разрешения коллизий:

• Метод цепочек (Separate Chaining): Используется в std::unordered_map. Элементы с одинаковым хешем помещаются в один бакет (список).
• Открытая адресация (Open Addressing): При коллизии элемент помещается в следующий свободный слот таблицы согласно определённому алгоритму (линейное/квадратичное пробирование, двойное хеширование). Используется, например, в std::unordered_set некоторых реализаций стандартной библиотеки.