std:: hash

Включенные специализации шаблона 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-неквалифицированные arithmetic types
• все cv-неквалифицированные enumeration types
• все cv-неквалифицированные pointer types
• std::nullptr_t

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

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

Примечания

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

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

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

Дополнительные специализации для 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; // начиная с 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 = "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"};
    // Использование автономного функционального объекта.
    std::cout << "hash(" << std::quoted(obj.first_name) << ", "
              << std::quoted(obj.last_name) << ") =\t"
              << MyHash{}(obj) << " (используя MyHash) или\n\t\t\t\t"
              << std::hash<S>{}(obj) << " (используя внедренную специализацию)\n";
    // Пользовательский хэш позволяет использовать пользовательские типы в неупорядоченных контейнерах.
    // Пример будет использовать внедренную специализацию std::hash<S> выше,
    // чтобы использовать MyHash вместо этого, передайте его вторым аргументом шаблона.
    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) или
                                12922914235676820612 (using injected specialization)
"Bender" "Rodriguez"
"Turanga" "Leela"
"Hubert" "Farnsworth"

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

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