Skip to content

Latest commit

 

History

History
214 lines (177 loc) · 9.36 KB

hash.md

File metadata and controls

214 lines (177 loc) · 9.36 KB
Raw

hash

  • functional[meta header]
  • std[meta namespace]
  • class template[meta id-type]
  • cpp11[meta cpp]
namespace std {
  template <class T> struct hash;

  // ハッシュ関数の特殊化
  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<nullptr_t>;  // C++17
  template<class T> struct hash<T*>;
}

概要

クラステンプレートhashは、非順序連想コンテナ（unordered_map/unordered_multimap/unordered_set/unordered_multiset）のキーとなる型のためのハッシュ値を計算する関数オブジェクトである。

このクラスはそのものにデフォルトの定義は存在せず、ユーザーが任意の型で特殊化する際の要件を定義する。hashクラステンプレートを特殊化する場合、後述するメンバ関数を持たせる必要がある。

基本型のハッシュサポート

<functional>ヘッダでは、基本型に対する特殊化を提供する。 std::stringなどC++標準ライブラリ定義の型に対する特殊化は、対象型を定義する各種ヘッダファイルにて提供される。

型 対応バージョン
bool C++11
char C++11
signed char C++11
unsigned char C++11
char8_t C++20
char16_t C++11
char32_t C++11
wchar_t C++11
short C++11
unsigned short C++11
int C++11
unsigned int C++11
long C++11
long long C++11
unsigned long C++11
unsigned long long C++11
float C++11
double C++11
long double C++11
全ての型へのポインタ C++11
全ての列挙型 C++14
nullptr_t C++17

メンバ関数

名前 説明
(constructor) デフォルトコンストラクタ、コピーコンストラクタ、ムーブコンストラクタを持つ
(destructor) デストラクタを持つ
operator= コピー代入演算子とムーブ代入演算子を持つ
operator() 関数呼び出し演算子によって、キー値kに対応するsize_t型のハッシュ値を返す。const修飾メンバ関数。

関数呼び出し演算子に関する制約は次の通り :

  • 引数に指定するキー値kを変更してはならない。
  • ハッシュ計算は引数で指定したキー値以外に依存してはいけない（状態をもってはいけない）。
  • 式k1 == k2を満たす2個のキー値に対しては、同一ハッシュ値を返すこと。
    • 異なる2個のキーに対して同一ハッシュ値を返すこと（collision; 衝突）は許容されるが、入力に対する出力ハッシュ値はsize_t型の値域において均等分布することが好ましい。

メンバ型

名前 説明 対応バージョン
is_transparent 省略可。ハッシュ計算を行う関数オブジェクトがこの型を持っている場合、非順序連想コンテナの透過的な検索関数が有効になる。
この型は、例えば関数オブジェクトがstring型／string_view型／ヌル終端文字列(const char*)に対して等価なハッシュ値を生成できる場合に定義される。		 C++20

例

基本的な使い方

#include <iostream>
#include <functional>

enum class E { A = 1, B = 42, C = 100 };

int main()
{
  int x;

  // char型の値'C'に対するハッシュ値を求める
  std::cout << std::hash<char>()('C') << std::endl;

  // int型の値100に対するハッシュ値を求める
  std::cout << std::hash<int>()(100) << std::endl;

  // double型の値3.14に対するハッシュ値を求める
  std::cout << std::hash<double>()(3.14) << std::endl;

  // int*型のアドレス値(&x)に対するハッシュ値を求める
  std::cout << std::hash<int*>()(&x) << std::endl;

  // 列挙型の値E::Bに対するハッシュ値を求める（C++14から）
  E e = E::B;
  std::cout << std::hash<E>()(e) << std::endl;
}
  • std::hash[color ff0000]

出力例

67
100
1427109137
3219530756
42

透過的にハッシュ値を計算できる場合 (C++20)

メンバ型is_transparentが定義される場合、以下のようなコードにおいて、findメンバ関数に文字列リテラルを指定しても、一時的なstringオブジェクトが作成されず、パフォーマンス向上が期待できる。

#include <iostream>
#include <unordered_map>
#include <string>
#include <string_view>

struct string_hash {
  using is_transparent = void;
  // string/string_view/const char*共用ハッシュ計算
  size_t operator()(std::string_view sv) const {
    return std::hash<std::string_view>{}(sv);
  }
};

int main()
{
  // キー型=std::string, 値型=int
  std::unordered_map<std::string, int, string_hash, std::equal_to<>> um = {
    {"Alice", 3},
    {"Bob", 1},
    {"Carol", 4}
  };

  // string_hashおよびstd::equal_to<>はいずれもメンバ型にis_transparentを持つため、
  // find()などの検索関数に値を渡す場合に、キー型(std::string)一時オブジェクトが作られない
  auto it = um.find("Alice");
  if (it != um.end()) {
    std::cout << "found : " << it->second << std::endl;
  }
}
  • um.find[link /reference/unordered_map/unordered_map/find.md]
  • um.end()[link /reference/unordered_map/unordered_map/end.md]

出力

found : 3

バージョン

言語

  • C++11

処理系

関連項目

ヘッダ 特殊化対象
<coroutine> std::coroutine_handle
<bitset> std::bitset
<filesystem> std::filesystem::path
<optional> std::optional
<memory> std::shared_ptr, std::unique_ptr
<stacktrace> std::basic_backtrace, std::stacktrace_entry
<string> std::stringなど
<string_view> std::string_viewなど
<system_error> std::error_code, std::error_condition
<thread> std::thread:id
<typeindex> std::type_index
<variant> std::variant, std::monostate
<vector> std::vector<bool>

参照