Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/utility/hash"

From cppreference.com
< cpp‎ | utility
m (+variant in the list)
m (Clarify wording around C++14 hash enum specifications)
Line 73: Line 73:
 
{{rev begin}}
 
{{rev begin}}
 
{{rev|since=c++14|
 
{{rev|since=c++14|
−
In addition to the above, standard library provides specializations for all (scoped and unscoped) enumeration types (which are not required, but usually are implemented as {{c|std::hash<std::underlying_type<Enum>::type>}})
+
In addition to the above, the standard library provides specializations for all (scoped and unscoped) enumeration types. These may be (but are not required to be) implemented as {{c|std::hash<std::underlying_type<Enum>::type>}})
 
}}
 
}}
 
{{rev|since=c++17|
 
{{rev|since=c++17|

Revision as of 15:55, 18 July 2016

 
C++
 
Utilities library
General utilities
Relational operators (deprecated in C++20)
 
std::hash
 
Defined in header <functional>
template< class Key >
struct hash;
 (since C++11)

The hash template defines a function object that implements a hash function. Instances of this function object satisfy Template:concept. In particular, they define an operator() that:

1. Accepts a single parameter of type Key.

2. Returns a value of type size_t that represents the hash value of the parameter.

3. Does not throw exceptions when called.

4. For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2).

5. For two different parameters k1 and k2 that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().

The hash template is Template:concept, Template:concept, Template:concept and Template:concept.

The unordered associative containers std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap use specializations of the template std::hash as the default hash function.

Contents

Notes

The actual hash functions are implementation-dependent and are not required to fulfill any other quality criteria except those specified above. Notably, some implementations use trivial (identity) hash functions which map an integer to itself. In other words, these hash functions are designed to work with unordered associative containers, but not as cryptographic hashes, for example.

Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision DoS attacks. (since C++14)

There is no specialization for C strings. std::hash<const char*> produces a hash of the value of the pointer (the memory address), it does not examine the contents of any character array.

Member types

Member type Definition
argument_type(deprecated in C++17) Key
result_type(deprecated in C++17) std::size_t

Member functions

 constructs a hash function object
(public member function)
calculate the hash of the argument
(public member function)

Standard specializations for basic types

Defined in header <functional>
template<> struct hash<bool>;

template<> struct hash<char>;
template<> struct hash<signed char>;
template<> struct hash<unsigned char>;
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< class T > struct hash<T*>;

In addition to the above, the standard library provides specializations for all (scoped and unscoped) enumeration types. These may be (but are not required to be) implemented as std::hash<std::underlying_type<Enum>::type>)

(since C++14)

In addition to the above, the standard library provides specializations for all integral types, including any extended integer types that the implementation supports.

(since C++17)

Standard specializations for library types

(C++11)
 hash support for strings
(class template specialization) [edit]
(C++11)
 hash support for std::error_code
(class template specialization) [edit]
(C++11)
 hash support for std::bitset
(class template specialization) [edit]
(C++11)
 hash support for std::unique_ptr
(class template specialization) [edit]
(C++11)
 hash support for std::shared_ptr
(class template specialization) [edit]
(C++11)
 hash support for std::type_index
(class template specialization) [edit]
(C++11)
 hash support for std::vector<bool>
(class template specialization)
(C++11)
 hash support for std::thread::id
(class template specialization)
(C++17)
 hash support for std::optional
(class template specialization) [edit]
(C++17)
 hash support for std::variant
(class template specialization) [edit]
(C++17)(C++17)(C++20)(C++17)(C++17)
 hash support for string views
(class template specialization) [edit]

Note: additional specializations for std::pair and the standard container types, as well as utility functions to compose hashes are available in boost.hash


Example

Run this code
#include <iostream>
#include <iomanip>
#include <functional>
#include <string>
#include <unordered_set>
 
struct S {
    std::string first_name;
    std::string last_name;
};
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:
template <class T> struct MyHash;
template<> struct MyHash<S>
{
    std::size_t operator()(S const& s) const 
    {
        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
namespace std
{
    template<> struct hash<S>
    {
        typedef S argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& s) const
        {
            result_type const h1 ( std::hash<std::string>()(s.first_name) );
            result_type const 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) << ") = " << 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) << ") = "
               << MyHash<S>{}(obj) << " (using MyHash)\n                           or "
               << std::hash<S>{}(obj) << " (using std::hash) " << '\n';
 
    // custom hash makes it possible to use custom types in unordered containers
    std::unordered_set<S> names = {obj, {"Bender", "Rodriguez"}, {"Leela", "Turanga"} };
    for(auto& s: names)
        std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n';
}

Possible output: 

hash("Meet the new boss...") = 1861821886482076440
hash("Hubert","Farnsworth") = 17622465712001802105 (using MyHash)
                           or 17622465712001802105 (using std::hash) 
"Leela" "Turanga"
"Bender" "Rodriguez"
"Hubert" "Farnsworth"
Retrieved from "https://en.cppreference.com/mwiki/index.php?title=cpp/utility/hash&oldid=86953"