std::hash

 

C++

Поддержка компилятором

Автономные и размещённые реализации

Язык

Стандартная библиотека

Заголовки стандартной библиотеки

Требования к именованию

Макросы тестирования функциональности (C++20)

Поддержка языка

Библиотека концептов (C++20)

Библиотека метапрограммирования (C++11)

Библиотека диагностики

Библиотека общих утилит

Библиотека строк

Библиотека контейнеров

Библиотека итераторов

Библиотека диапазонов (C++20)

Библиотека алгоритмов

Библиотека численных данных

Библиотека ввода/вывода

Библиотека локализаций

Регулярные выражения (C++11)

Атомарные операции (C++11)

Библиотека поддержки конкуренции (C++11)

Библиотека файловой системы (C++17)

Технические спецификации

Указатель символов

Внешние библиотеки

 

Библиотека утилит

Языковая поддержка Поддержка типов (базовые типы, RTTI) Макросы тестирования функциональности библиотеки (C++20)     Управление динамической памятью Программные утилиты Поддержка сопрограмм (C++20) Вариативные функции is_constant_evaluated (C++20) is_within_lifetime (C++26) initializer_list (C++11) source_location (C++20) Трёхстороннее сравнение (C++20) three_way_comparablethree_way_comparable_with (C++20)(C++20) strong_ordering (C++20) weak_ordering (C++20) partial_ordering (C++20) common_comparison_category (C++20) compare_three_way_result (C++20) compare_three_way (C++20) strong_order (C++20) weak_order (C++20) partial_order (C++20) compare_strong_order_fallback (C++20) compare_weak_order_fallback (C++20) compare_partial_order_fallback (C++20)     is_eqis_neqis_ltis_lteqis_gtis_gteq (C++20)(C++20)(C++20)(C++20)(C++20)(C++20)

Общие утилиты Дата и время Функциональные объекты Библиотека форматирования (C++20) bitset hash (C++11) Операторы отношения (устарело в C++20) rel_ops::operator!=rel_ops::operator> rel_ops::operator<=rel_ops::operator>= Целочисленные функции сравнения cmp_equalcmp_lesscmp_less_than (C++20)(C++20)(C++20)     cmp_not_equalcmp_greatercmp_greater_than (C++20)(C++20)(C++20) in_range (C++20) Операции обмена и типа swap ranges::swap (C++20) exchange (C++14) declval (C++11) to_underlying (C++23) forward (C++11) forward_like (C++23) move (C++11) move_if_noexcept (C++11) as_const (C++17) Общие лексические типы pair tuple (C++11) optional (C++17) any (C++17) variant (C++17) tuple_size (C++11) tuple_element (C++11) apply (C++17) make_from_tuple (C++17) expected (C++23) Элементарные преобразования строк to_chars (C++17) from_chars (C++17) chars_format (C++17) to_chars_result (C++17) from_chars_result (C++17)

 

std::hash

hash::hash

hash::operator()

 

<tbody> </tbody>

Определено в заголовочном файле <functional>
template< class Key > struct hash;		(начиная с C++11)

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

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

Типы элементы Тип элемент Определение argument_type(устарело в C++17) Key result_type(устарело в C++17) std::size_t

(до C++20)

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

(конструктор)	создаёт объект хэш-функции (public функция-элемент)
operator()	вычисляет хеш аргумента (public функция-элемент)

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

<tbody> </tbody>

Определено в заголовочном файле <functional>
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>

<optional> <string_view> <variant>	(начиная с C++17)
<coroutine>	(начиная с C++20)
<stacktrace>	(начиная с C++23)
<chrono>	(начиная с C++26)

Все функции-элементы всех специализаций стандартной библиотеки этого шаблона являются noexcept, за исключением функций-элементов: std::hash<std::optional> std::hash<std::variant> std::hash<std::unique_ptr> std::hash<std::chrono::duration> std::hash<std::chrono::time_point> std::hash<std::chrono::zoned_time> (начиная с C++26)

(начиная с C++17)

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

std::hash<std::coroutine_handle> (C++20)	поддержка хэширования для std::coroutine_handle (специализация шаблона класса)
std::hash<std::error_code> (C++11)	поддержка хэширования для std::error_code (специализация шаблона класса)
std::hash<std::error_condition> (C++17)	поддержка хэширования для std::error_condition (специализация шаблона класса)
std::hash<std::stacktrace_entry> (C++23)	поддержка хэширования для std::stacktrace_entry (специализация шаблона класса)
std::hash<std::basic_stacktrace> (C++23)	поддержка хэширования для std::basic_stacktrace (специализация шаблона класса)
std::hash<std::optional> (C++17)	поддержка хэширования для std::optional (специализация шаблона класса)
std::hash<std::variant> (C++17)	поддержка хэширования для std::variant (специализация шаблона класса)
std::hash<std::monostate> (C++17)	поддержка хэширования для std::monostate (специализация шаблона класса)
std::hash<std::bitset> (C++11)	поддержка хэширования для std::bitset (специализация шаблона класса)
std::hash<std::unique_ptr> (C++11)	поддержка хэширования для std::unique_ptr (специализация шаблона класса)
std::hash<std::shared_ptr> (C++11)	поддержка хэширования для std::shared_ptr (специализация шаблона класса)
std::hash<std::type_index> (C++11)	поддержка хэширования для std::type_index (специализация шаблона класса)
std::hash<std::string>std::hash<std::u8string>std::hash<std::u16string>std::hash<std::u32string>std::hash<std::wstring>std::hash<std::pmr::string>std::hash<std::pmr::u8string>std::hash<std::pmr::u16string>std::hash<std::pmr::u32string>std::hash<std::pmr::wstring> (C++11)(C++20)(C++11)(C++11)(C++11)(C++17)(C++20)(C++17)(C++17)(C++17)	поддержка хэширования для строк (специализация шаблона класса)
std::hash<std::string_view>std::hash<std::wstring_view>std::hash<std::u8string_view>std::hash<std::u16string_view>std::hash<std::u32string_view> (C++17)(C++17)(C++20)(C++17)(C++17)	поддержка хэширования для строковых представлений (специализация шаблона класса)
std::hash<std::vector<bool>> (C++11)	поддержка хэширования для std::vector<bool> (специализация шаблона класса)
std::hash<std::filesystem::path> (C++17)	поддержка хэширования для std::filesystem::path (специализация шаблона класса)
std::hash<std::thread::id> (C++11)	поддержка хэширования для std::thread::id (специализация шаблона класса)
std::hash<std::chrono::duration> (C++26)	поддержка хэширования для std::chrono::duration (специализация шаблона класса)
std::hash<std::chrono::time_point> (C++26)	поддержка хэширования для std::chrono::time_point (специализация шаблона класса)
std::hash<std::chrono::day> (C++26)	поддержка хэширования для std::chrono::day (специализация шаблона класса)
std::hash<std::chrono::month> (C++26)	поддержка хэширования для std::chrono::month (специализация шаблона класса)
std::hash<std::chrono::year> (C++26)	поддержка хэширования для std::chrono::year (специализация шаблона класса)
std::hash<std::chrono::weekday> (C++26)	поддержка хэширования для std::chrono::weekday (специализация шаблона класса)
std::hash<std::chrono::weekday_indexed> (C++26)	поддержка хэширования для std::chrono::weekday_indexed (специализация шаблона класса)
std::hash<std::chrono::weekday_last> (C++26)	поддержка хэширования для std::chrono::weekday_last (специализация шаблона класса)
std::hash<std::chrono::month_day> (C++26)	поддержка хэширования для std::chrono::month_day (специализация шаблона класса)
std::hash<std::chrono::month_day_last> (C++26)	поддержка хэширования для std::chrono::month_day_last (специализация шаблона класса)
std::hash<std::chrono::month_weekday> (C++26)	поддержка хэширования для std::chrono::month_weekday (специализация шаблона класса)
std::hash<std::chrono::month_weekday_last> (C++26)	поддержка хэширования для std::chrono::month_weekday_last (специализация шаблона класса)
std::hash<std::chrono::year_month> (C++26)	поддержка хэширования для std::chrono::year_month (специализация шаблона класса)
std::hash<std::chrono::year_month_day> (C++26)	поддержка хэширования для std::chrono::year_month_day (специализация шаблона класса)
std::hash<std::chrono::year_month_day_last> (C++26)	поддержка хэширования для std::chrono::year_month_day_last (специализация шаблона класса)
std::hash<std::chrono::year_month_weekday> (C++26)	поддержка хэширования для std::chrono::year_month_weekday (специализация шаблона класса)
std::hash<std::chrono::year_month_weekday_last> (C++26)	поддержка хэширования для std::chrono::year_month_weekday_last (специализация шаблона класса)
std::hash<std::chrono::zoned_time> (C++26)	поддержка хэширования для std::chrono::zoned_time (специализация шаблона класса)
std::hash<std::chrono::leap_second> (C++26)	поддержка хэширования для std::chrono::leap_second (специализация шаблона класса)

Примечание: дополнительные специализации для 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++:

Номер	Применён	Поведение в стандарте	Корректное поведение
LWG 2148	C++11	специализации для перечислений отсутствовали	предоставлены
LWG 2543	C++11	std::hash может не подходить для SFINAE	сделано дружественным SFINAE через недоступные специализации
LWG 2817	C++11	специализация для std::nullptr_t отсутствовала	предоставлена