std::hash — cppreference.com

<tbody> </tbody>

Каждая специализация этого шаблона либо доступна ("не испорчена") либо недоступна ("испорчена").

Доступные специализации шаблона hash определяют объект функцию, реализующий хэш-функцию. Экземпляры этого объекта функции соответствуют Hash. В частности, они определяют operator() const, который:

1. Принимает единственный параметр типа Key.
2. Возвращает значение типа std::size_t, которое представляет хеш-значение параметра.
3. Не вызывает исключений при вызове.
4. Для двух параметров k1 и k2, которые равны, std::hash<Key>()(k1) == std::hash<Key>()(k2).
5. Для двух разных параметров k1 и k2, которые не равны, вероятность того, что std::hash<Key>()(k1) == std::hash<Key>()(k2) должна быть очень маленькой, близкой к 1.0/std::numeric_limits<std::size_t>::max().

Все явные и частичные специализации std::hash, предоставляемые стандартной библиотекой, соответствуют: DefaultConstructible, CopyAssignable, Swappable и Destructible. Предоставляемые пользователем специализации hash также должны соответствовать этим требованиям.

Неупорядоченные ассоциативные контейнеры std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap используют специализации шаблона std::hash в качестве хэш-функции по умолчанию.

Для каждого типа Key, для которого ни библиотека, ни пользователь не предоставили доступную специализацию std::hash<Key>, специализация существует и недоступна. Недоступные специализации не соответствуют Hash, не соответствуют FunctionObject, и все следующие значения равны false:

• std::is_default_constructible<std::hash<Key>>::value
• std::is_copy_constructible<std::hash<Key>>::value
• std::is_move_constructible<std::hash<Key>>::value
• std::is_copy_assignable<std::hash<Key>>::value
• std::is_move_assignable<std::hash<Key>>::value

Другими словами, они существуют, но их нельзя использовать.

Примечание

Фактические хэш-функции зависят от реализации и не должны соответствовать каким-либо другим критериям качества, кроме указанных выше. Примечательно, что в некоторых реализациях используются тривиальные (идентификационные) хэш-функции, которые отображают целое число само на себя. Другими словами, эти хеш-функции предназначены для работы с неупорядоченными ассоциативными контейнерами, но не как, например, криптографические хеши.

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

Для строк C нет специализации. std::hash<const char*> производит хэш значения указателя (адреса памяти), он не проверяет содержимое какого-либо массива символов.

Функции-элементы

Стандартные специализации для основных типов

<tbody> </tbody>

В дополнение к вышесказанному стандартная библиотека предоставляет специализации для всех перечислимых типов (с ограниченными областями видимости и нет). Они могут быть (но не обязательно) реализованы как std::hash<std::underlying_type<Enum>::type>)

Стандартная библиотека предоставляет доступные специализации std::hash для std::nullptr_t и всех cv-неквалифицированных арифметических типов (включая любые расширенные целочисленные типы), всех типов перечислений и всех типов указателей.

Каждый заголовок стандартной библиотеки, объявляющий шаблон std::hash, предоставляет все доступные специализации, описанные выше:

• <bitset>
• <memory>
• <string>
• <system_error>
• <thread>
• <typeindex>
• <vector>

Стандартные специализации для библиотечных типов

Примечание: дополнительные специализации для std::pair и стандартных типов контейнеров, а также служебные функции для составления хэшей доступны в boost::hash.

Пример

#include <functional>
#include <iomanip>
#include <iostream>
#include <string>
#include <unordered_set>

struct S {
    std::string first_name;
    std::string last_name;
    bool operator==(const S&) const = default; // начиная с C++20
};

// Перед C++20
// bool operator==(const S& lhs, const S& rhs)
// {
//     return lhs.first_name == rhs.first_name && lhs.last_name == rhs.last_name;
// }

// пользовательский хеш может быть отдельным объектом функцией:
struct MyHash
{
    std::size_t operator()(const S& s) const noexcept
    {
        std::size_t h1 = std::hash<std::string>{}(s.first_name);
        std::size_t h2 = std::hash<std::string>{}(s.last_name);
        return h1 ^ (h2 << 1); // или используйте boost::hash_combine
                               // (смотрите Обсуждение)
    }
};

// пользовательская специализация std::hash может быть введена в пространство имён std
template<> struct std::hash<S>
{
    std::size_t operator()(const S& s) const noexcept
    {
        std::size_t h1 = std::hash<std::string>{}(s.first_name);
        std::size_t h2 = std::hash<std::string>{}(s.last_name);
        return h1 ^ (h2 << 1); // или используйте boost::hash_combine
    }
};

int main()
{
    std::string str = "Встречайте нового босса ...";
    std::size_t str_hash = std::hash<std::string>{}(str);
    std::cout << "hash(" << std::quoted(str) << ") = \n\t" << str_hash << '\n';

    S obj = { "Хьюберт", "Фарнсворт" };
    // использование автономного объекта функции
    std::cout << "hash(" << std::quoted(obj.first_name) << ", "
              << std::quoted(obj.last_name) << ") =\n\t"
              << MyHash{}(obj) << " (используется MyHash) или\n\t\t\t\t"
              << std::hash<S>{}(obj)
              << " (используется введённая в std специализация std::hash<S>)\n";

    // Пользовательский хеш позволяет использовать пользовательские типы в неупорядоченных
    // контейнерах
    // В этом примере будет использоваться введённая выше специализация std::hash<S>.
    // Чтобы вместо неё использовать MyHash, передайте его вторым аргументом шаблона.
    std::unordered_set<S> names = {obj, {"Бендер", "Родригес"}, {"Туранга", "Лила"}};
    for(auto const& s: names)
        std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n';
}

hash("Встречайте нового босса ...") = 10656026664466977650
hash("Хьюберт", "Фарнсворт") =
      12922914235676820612 (используется MyHash) или
      12922914235676820612 (используется введённая в std специализация std::hash<S>) 
"Бендер" "Родригес"
"Туранга" "Лила"
"Хьюберт" "Фарнсворт"

Отчёты о дефектах

Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++: