std::hash

template< class Key >
struct hash;

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

Для типа Key каждая специализация std::hash<Key> либо включена, либо отключена :

• Если программа или пользователь не предоставляет std::hash<Key>, она отключена.
• В противном случае std::hash<Key> включена, если выполнены все следующие условия:
• Выполнены все следующие требования:
• Hash (с Key в качестве типа аргумента вызова функции)
• DefaultConstructible
• CopyAssignable
• Swappable
• При следующих значениях:

• h, объект типа std::hash<Key>.
• k1 и k2, объекты типа Key.

Выполнены все следующие требования:

• Если k1 == k2 равно true, то h(k1) == h(k2) также равно true.
• Если std::hash<Key> не является специализацией, определённой программой, h(k1) никогда не генерирует исключение.

• В противном случае 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

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

Функции-члены

Специализации стандартной библиотеки

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

• все арифметические типы без cv-квалификаторов
• все типы перечислений без cv-квалификаторов
• все типы указателей без cv-квалификаторов
• std::nullptr_t

Кроме того, некоторые заголовочные файлы предоставляют другие включённые специализации std::hash для библиотечных типов (см. ниже).

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

Примечания

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

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

Специализации для строк C отсутствуют. std::hash<constchar*> вычисляет хеш значения указателя (адреса в памяти), не проверяя содержимое массива символов.

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

Пример

#include <cstddef>
#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; // since C++20
};

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

// Custom hash can be a standalone function object.
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); // or use boost::hash_combine
    }
};

// Custom specialization of std::hash can be injected in namespace 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); // or use boost::hash_combine
    }
};

int main()
{
    std::string str = "Meet the new boss...";
    std::size_t str_hash = std::hash<std::string>{}(str);
    std::cout << "hash(" << std::quoted(str) << ") =\t" << str_hash << '\n';
    
    S obj = {"Hubert", "Farnsworth"};
    // Using the standalone function object.
    std::cout << "hash(" << std::quoted(obj.first_name) << ", "
              << std::quoted(obj.last_name) << ") =\t"
              << MyHash{}(obj) << " (using MyHash) or\n\t\t\t\t"
              << std::hash<S>{}(obj) << " (using injected specialization)\n";
    
    // Custom hash makes it possible to use custom types in unordered containers.
    // The example will use the injected std::hash<S> specialization above,
    // to use MyHash instead, pass it as a second template argument.
    std::unordered_set<S> names = {obj, {"Bender", "Rodriguez"}, {"Turanga", "Leela"}};
    for (auto const& s: names)
        std::cout << std::quoted(s.first_name) << ' '
                  << std::quoted(s.last_name) << '\n';
}

hash("Meet the new boss...") =  10656026664466977650
hash("Hubert", "Farnsworth") =  12922914235676820612 (using MyHash) or
                                12922914235676820612 (using injected specialization)
"Bender" "Rodriguez"
"Turanga" "Leela"
"Hubert" "Farnsworth"

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.