0Pricing
C++ Academy · Урок

Пользовательские хеш-функции

Хешируйте собственные типы

«Пользовательские хеш-функции» — бесплатный урок C++ Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C++ Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C++ Academy содержит 4 уроков всего.

Зачем нужны пользовательские хеши

Неупорядоченным контейнерам нужен способ хешировать ключи. Для встроенных типов и std::string хеши уже определены, но у собственных типов их нет. Вы должны предоставить такой хеш.

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

Шаблон std::hash

std::hash — это функтор, преобразующий значение в size_t. Его вызывают как функцию.

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

Структура для хеширования

Предположим, у нас есть Point с двумя целыми числами. Чтобы хранить его в неупорядоченном множестве, нам нужны и оператор равенства, и хеш.

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

Написание функтора хеширования

Функтор хеширования — это структура с operator(), возвращающим size_t. Объединяйте хеши полей, часто используя XOR и сдвиг.

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

Использование функтора хеширования

Передайте функтор хеширования как второй аргумент шаблона неупорядоченного контейнера.

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

Равенство также необходимо

Два ключа попадают в одну корзину, если их хеши совпадают. Затем контейнер использует operator==, чтобы различить их, поэтому проверка равенства обязательна.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

Хеширование в качестве ключа отображения

Тот же пользовательский хеш позволяет использовать структуру как ключ в unordered_map.

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

Объединение нескольких полей

Распространённый вспомогательный объект объединяет хеши по одному полю за раз, используя схему с умножением и сложением, похожую на boost::hash_combine.

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

Good распределение хеша

Плохой хеш, возвращающий константу, помещает всё в одну корзину, что ухудшает сложность до O(n). Хорошо перемешивайте биты всех полей.

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

Специализация std::hash

Другой вариант — специализировать std::hash для своего типа, чтобы он работал без явной передачи функтора.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

Лямбда-выражение как хеш

В C++20 можно даже использовать лямбда-выражение без состояния как хеш, передав его тип.

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

Быстрая проверка

Проверьте, насколько хорошо Вы поняли пользовательское хеширование.

Повторение

Вы научились хешировать пользовательские типы:

  • предоставлять функтор хеширования (или специализировать std::hash), возвращающий size_t
  • также предоставлять operator==, чтобы различать ключи с совпавшими хешами
  • правильно объединять хеши полей для хорошего распределения

Далее Вы изучите корзины и производительность при разных коэффициентах заполнения.

Часто задаваемые вопросы

Урок «Пользовательские хеш-функции» бесплатный?

Да — полный текст урока «Пользовательские хеш-функции» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C++ Academy, подпишись на CoddyKit PRO. Курс C++ Academy содержит 4 уроков всего.

Чему я научусь в уроке «Пользовательские хеш-функции»?

Хешируйте собственные типы Ты практикуешь C++ Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C++ Academy?

Предыдущий опыт не требуется. C++ Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Пользовательские хеш-функции»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C++ Academy?

Да. Каждый урок C++ Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. std::unordered_map
  2. unordered_set
  3. Пользовательские хеш-функции
  4. Вопросы производительности
← Назад к C++ Academy