Хеш-таблицы: unordered_map/unordered_set, коллизии, производительность

Введение

QSet для демонстрации линейной сложности поиска дубликатов — в этой статье разберём хеш-таблицы (std::unordered_map/unordered_set, QHash/QSet) подробнее: принцип работы через хеш-функцию, проблему коллизий, и практические последствия для производительности.

Концепция

Хеш-таблица вычисляет для каждого ключа числовое значение (хеш) через хеш-функцию, и использует это число для определения, в каком «сегменте» (bucket) внутреннего массива должен храниться этот ключ — при отсутствии коллизий (разные ключи попадают в разные сегменты) это даёт O(1) доступ, вставку и удаление в среднем случае, поскольку нужный сегмент вычисляется напрямую по хешу, без необходимости перебора остальных элементов. Коллизия (несколько разных ключей, дающих одинаковый хеш или попадающих в один и тот же сегмент) разрешается одним из нескольких способов (цепочки — каждый сегмент хранит список всех попавших в него элементов; открытая адресация — поиск следующего свободного сегмента) — при большом количестве коллизий (плохая хеш-функция или переполнение таблицы относительно её текущего размера) производительность операций деградирует от O(1) в сторону худшего случая O(n).

Пример кода

// unordered_map — типичное использование для быстрого поиска по ключу
#include <unordered_map>

std::unordered_map<QString, int> wordCounts;
QStringList words = {"qt", "c++", "qt", "cmake", "qt"};

for (const QString &word : words) {
    wordCounts[word]++; // O(1) в среднем случае — и поиск существующего ключа, и вставка нового
}

for (const auto &[word, count] : wordCounts) { // C++17 structured bindings
    qDebug() << word << ":" << count;
}

// Пользовательский тип как ключ требует собственной хеш-функции
struct Point { int x, y; bool operator==(const Point &other) const { return x == other.x && y == other.y; } };

struct PointHash {
    std::size_t operator()(const Point &p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
        // комбинирование хешей отдельных полей — типичный, хотя и не единственный возможный подход
    }
};

std::unordered_map<Point, QString, PointHash> pointLabels;
pointLabels[{0, 0}] = "Начало координат";

// Демонстрация деградации производительности при плохой хеш-функции (концептуально)
struct BadHash {
    std::size_t operator()(int value) const {
        return 0; // ВСЕ значения попадают в ОДИН и тот же сегмент — катастрофическая коллизия
    }
};
// С такой хеш-функцией unordered_map<int, ..., BadHash> вырождается в O(n) для каждой операции —
// фактически работает как простой связный список внутри единственного сегмента

Пояснения к коду

Цикл подсчёта wordCounts[word]++ показывает типичный, идиоматичный паттерн использования хеш-таблицы — оператор [] либо находит существующую запись для данного ключа, либо создаёт новую (со значением по умолчанию для типа значения, для int это 0), и оба случая выполняются в среднем за константное время, независимо от общего количества уже накопленных в таблице элементов. Пользовательская хеш-функция PointHash необходима, поскольку компилятор не может автоматически определить, как вычислять хеш для произвольного пользовательского типа — комбинирование хешей отдельных полей через XOR и битовый сдвиг — распространённый, хотя и не единственно возможный практический подход к построению такой функции. BadHash, всегда возвращающий 0, явно демонстрирует крайний, вырожденный случай — все элементы попадают в один и тот же сегмент, и хеш-таблица фактически вырождается в простой линейный поиск, теряя всю свою основную практическую ценность.

Подводные камни

Написание собственной, нетщательно продуманной хеш-функции для пользовательского типа, которая даёт слишком много коллизий для реальных, практических наборов данных — плохая хеш-функция (как утрированный пример BadHash, но и менее очевидные, более тонкие случаи плохого распределения) сводит на нет всю теоретическую выгоду хеш-таблицы, и для нестандартных типов стоит либо тщательно продумать собственную функцию (с учётом реального распределения вероятных значений), либо использовать готовые, проверенные библиотечные средства комбинирования хешей (boost::hash_combine или аналогичные).
Несогласованность между пользовательским operator== и хеш-функцией — если две сущности, считающиеся равными согласно operator==, дают разные хеши согласно хеш-функции, хеш-таблица не сможет корректно находить уже вставленные записи (внутренний механизм хеш-таблицы предполагает, что равные объекты ОБЯЗАНЫ иметь одинаковый хеш — это фундаментальный, обязательный контракт, нарушение которого приводит к трудноуловимым ошибкам, когда поиск существующего, фактически равного элемента неожиданно не находит его).
Изменение значений полей объекта, используемого как ключ хеш-таблицы, уже после его вставки в таблицу (если объект хранится не как значение по value, а как ссылка/указатель, доступный для изменения снаружи) — изменение полей, участвующих в вычислении хеша, после вставки делает объект «потерянным» для таблицы: его реальное текущее положение в массиве сегментов соответствует УЖЕ устаревшему хешу, вычисленному на момент вставки, и последующий поиск по новому, актуальному значению хеша не найдёт этот элемент в ожидаемом месте.
Предположение детерминированного порядка перебора элементов unordered_map/unordered_set — в отличие от обычного map/set (упорядоченных по ключу через сбалансированное дерево), порядок элементов в хеш-таблице определяется внутренней реализацией (распределением по сегментам) и явно не гарантирован стандартом — код, неявно полагающийся на конкретный, наблюдаемый на практике порядок перебора unordered_map, формально некорректен и может непредсказуемо измениться при изменении реализации стандартной библиотеки или версии компилятора.