名前空間
変種
操作

std::hash

提供: cppreference.com
< cpp‎ | utility
 
 
 
 
ヘッダ <functional> で定義
template< class Key >
struct hash;
(C++11およびそれ以降)

このテンプレートの各々の特殊化は有効 (「汚染されていない」) または無効 (「毒入り」) のいずれかです。 ライブラリもユーザも有効な std::hash<Key> の特殊化を提供していないすべての Key 型に対して、その特殊化は存在しており、無効化されています。 無効化された特殊化は Hash を満たさず、 std::is_default_constructible_v, std::is_copy_constructible_v, std::is_move_constructible_v, std::is_copy_assignable_v, std::is_move_assignable_v はすべて false です。 別の言い方をすると、存在はしていますが、使うことはできません。

(C++17およびそれ以降)

hash テンプレート有効化された特殊化 (C++17およびそれ以降)ハッシュ関数を実装する関数オブジェクトを定義します。 この関数オブジェクトのインスタンスは Hash を満たします。 この型は以下のような operator() const を定義します。

1. Key 型の引数を1つ取ります。

2. 引数のハッシュ値を表す size_t 型の値を返します。

3. 呼ばれた時に例外を投げることはありません。

4. 2つの等しい値 k1 および k2 に対して、 std::hash<Key>()(k1) == std::hash<Key>()(k2) です。

5. 2つの等しくない異なる値 k1 および k2 に対して、 std::hash<Key>()(k1) == std::hash<Key>()(k2) である確率が非常に小さい、具体的には 1.0/std::numeric_limits<size_t>::max() に近いことが期待されます。

標準ライブラリによって提供される hash の明示的および部分的なすべての特殊化は DefaultConstructible, CopyAssignable, Swappable, Destructible を満たします。 ユーザが提供する hash の特殊化もこれらの要件を満たさなければなりません。

非順序連想コンテナ std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap はデフォルトのハッシュ関数として std::hash テンプレートの特殊化を使用します。

目次

[編集] ノート

実際のハッシュ関数は処理系依存であり、上で規定されている以外のいかなる品質基準も満たすことは要求されません。 例えば、整数をそれ自身に対応付ける自明な (恒等な) ハッシュ関数を使っている処理系もあります。 言い方を変えると、これらのハッシュ関数は非順序連想コンテナで使えるようには設計されていますが、例えば、暗号学的なハッシュではありません。

ハッシュ関数は、単一のプログラム実行中でしか、同じ入力に対して同じ結果を返すことが要求されません。 これにより、衝突 DoS 攻撃を防ぐソルト付きのハッシュを使うことができます。 (C++14およびそれ以降)

C の文字列に対する特殊化はありません。 std::hash<const char*> はポインタの値 (メモリアドレス) のハッシュを返し、文字配列の内容は考慮されません。

メンバ型

メンバ型 定義
argument_type(C++17で非推奨) Key
result_type(C++17で非推奨) std::size_t
(C++20以前)

[編集] メンバ関数

ハッシュ関数オブジェクトを構築します
(パブリックメンバ関数)
引数のハッシュを計算します
(パブリックメンバ関数)

[編集] 基本型に対する標準の特殊化

ヘッダ <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*>;

上記に加え、すべての (スコープ付きおよびスコープなしの) 列挙型に対する特殊化も標準ライブラリによって提供されます。 これらは std::hash<std::underlying_type<Enum>::type> として実装されるかもしれません (が、要求されているわけではありません)。

(C++14およびそれ以降)

テンプレート std::hash を宣言する標準ライブラリの各々のヘッダは std::nullptr t、すべての cv 修飾された算術型 (あらゆる拡張整数型を含む)、すべての列挙型およびすべてのポインタ型に対する std::hash の有効な特殊化を提供します。

このテンプレートの標準ライブラリによるすべての特殊化のすべてのメンバ関数は noexcept です。 ただし std::hash<std::optional>, std::hash<std::variant>, std::hash<std::unique_ptr> は除きます。

(C++17およびそれ以降)

[編集] ライブラリ型に対する標準の特殊化

文字列に対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::error_code に対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::bitset に対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::unique_ptr に対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::shared_ptr に対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::type_index に対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::vector<bool> に対するハッシュサポート
(クラステンプレートの特殊化)
std::thread::id に対するハッシュサポート
(クラステンプレートの特殊化)
std::hash アルゴリズムの特殊化
(クラステンプレートの特殊化) [edit]
std::hash アルゴリズムの特殊化
(クラステンプレートの特殊化) [edit]
文字列ビューに対するハッシュサポート
(クラステンプレートの特殊化) [edit]
std::error_condition に対するハッシュサポート
(クラステンプレートの特殊化) [edit]

ノート: std::pair および標準のコンテナ型に対する追加の特殊化やハッシュを合成するユーティリティ関数が boost.hash で利用可能です。


[編集]

#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:
struct MyHash
{
    std::size_t operator()(S const& 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 (see Discussion)
    }
};
 
// 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 noexcept
        {
            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 (see Discussion)
        }
    };
}
 
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{}(obj) << " (using MyHash)\n                           or "
               << std::hash<S>{}(obj) << " (using injected std::hash<S> 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"}, {"Leela", "Turanga"} };
    for(auto& s: names)
        std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n';
}

出力例:

hash("Meet the new boss...") = 1861821886482076440
hash("Hubert","Farnsworth") = 17622465712001802105 (using MyHash)
                           or 17622465712001802105 (using injected std::hash<S> specialization) 
"Leela" "Turanga"
"Bender" "Rodriguez"
"Hubert" "Farnsworth"