Перейти на PRO

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 25% Категория: C/C++ Разработчик

Ответ

Поиск в хеш-таблице, такой как 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 некоторых реализаций стандартной библиотеки.

Ответ 18+ 🔞

А, ну это же классика, ёпта! Сидишь такой, пишешь код, и тут тебе надо найти что-то в unordered_map. А как он там, этот поиск, внутри работает? Сейчас разложу по полочкам, чтобы даже кот, сука собака, понял.

Представь себе, что у тебя есть куча ящиков (это бакеты, bucket). Ты хочешь найти свою залупу конскую, то есть, прости, свой ключ k. Алгоритм простой, как три копейки:

  1. Считаем хеш. Берёшь ключ и суёшь его в хеш-функцию (по умолчанию std::hash<Key>). Она тебе выдаёт какое-то число, типа отпечаток пальца для ключа. Это типа как посмотреть на человека и сказать: «Ага, у этого чувака волосы рыжие, нос картошкой — запомнил».
  2. Ищем нужный ящик. Берёшь это число-отпечаток и вычисляешь, в какой именно ящик оно указывает. Обычно просто hash % количество_ящиков. Получил номер — побежал к нему. Если хеш-функция говно и все ключи дают один и тот же хеш, то все твои элементы свалятся в один ящик, и будет тебе O(n), то есть полный пиздец и линейный поиск по всему списку. А если функция хорошая, то элементы размажутся равномерно, и в каждом ящике будет по одному-два элемента — вот тогда сложность O(1), красота!
  3. Копаемся в ящике. Нашёл ящик. А там, блядь, не один элемент, а цепочка (список) тех, у кого хеш совпал (коллизии, ёбана!). Берёшь и начинаешь тупо, лоб в лоб, сравнивать искомый ключ k с ключами каждого элемента в этом списке. Как только нашёл совпадение — ура, вот он, твой элемент! Для сравнения используется функция std::equal_to<Key> (по умолчанию просто ==).

И вся эта магия упакована в метод .find(). Выглядит это в коде проще, чем звучит, вот смотри:

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

int main() {
    // Создали map, где по названию фрукта лежит его количество
    std::unordered_map<std::string, int> fruitMap = {{"apple", 5}, {"banana", 3}, {"orange", 8}};

    // Ищем "apple". Внутри find() происходит весь тот цирк с хешами и бакетами
    auto it = fruitMap.find("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 так и делают. Но в unordered_map из стандартной библиотеки C++ — почти всегда цепочки.

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

© ХакСобесов, 2026
support@hacksobesov.com