std::hash

template< class Key >
struct hash;

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

Включённые специализации шаблона 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*> производит хеш значения указателя (адрес памяти), она не анализирует содержимое массива символов.

Члены-функции

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

template<> struct hash<bool>;
template<> struct hash<char>;
template<> struct hash<signed char>;
template<> struct hash<unsigned char>;
template<> struct hash<char8_t>;        // C++20
template<> struct hash<char16_t>;
template<> struct hash<char32_t>;
template<> struct hash<wchar_t>;
template<> struct hash<short>;
template<> struct hash<unsigned short>;
template<> struct hash<int>;
template<> struct hash<unsigned int>;
template<> struct hash<long>;
template<> struct hash<long long>;
template<> struct hash<unsigned long>;
template<> struct hash<unsigned long long>;
template<> struct hash<float>;
template<> struct hash<double>;
template<> struct hash<long double>;
template<> struct hash<std::nullptr_t>;
template< class T > struct hash<T*>;

Помимо вышеперечисленного, стандартная библиотека предоставляет специализации для всех (скопированных и нескопированных) типов перечислений. Они могут быть (но не обязаны быть) реализованы как 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 <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++.