🗂

C++でハッシュ関数を定義する際の注意点

2023/12/20に公開

unordered系のコンテナを使う際には、キーとなる型からハッシュ値を計算できるようにハッシュ関数を定義する必要があります。基本型に対する定義は<functional>ヘッダに、std::stringなどの標準ライブラリで定義される型については、それぞれのヘッダファイルで定義されています。

ここで「size_t型に変換可能な型はすべてそのままハッシュ値として扱えるようにしよう」などと考えて、次のようなHasherを定義しました。

template<typename T, typename = void>
struct Hasher;

template<typename T>
struct Hasher<T, std::enable_if_t<std::is_convertible<T, size_t>::value>> {
  size_t operator()(const T& v) const {
    return v;
  }
};

この時点で「いやダメだろそれ」と言われそうですが、まぁこれはこれで動いていました。
で、次のようなハンドル型があったとします。

struct Handle {
  size_t id;
  operator bool() const { return id != 0; }
};

idが0の場合は無効値、それ以外は有効値を持つ何かしらのハンドル型です。これをさっき定義したHasherに通すと……

  Handle h0{256}, h1{100}, h2{1}, h3{0};

  std::cout << Hasher<Handle>()(h0) << std::endl;
  std::cout << Hasher<Handle>()(h1) << std::endl;
  std::cout << Hasher<Handle>()(h2) << std::endl;
  std::cout << Hasher<Handle>()(h3) << std::endl;

こうなってしまいます。operator bool()が定義されている型は、size_tに対してconvertibleだと判断されるからです。

これを避けるには、Handle型に対する明示的な特殊化を定義します。

template<>
struct Hasher<Handle> {
  size_t operator()(const Handle& v) const {
    return v.id;
  }
};

そもそもsize_tにconvertibleならOK！みたいなハッシュ関数を定義するべきではなさそうです。標準ライブラリでstd::hashがデフォルト実装を持たないのは、こういう事象を避けるためなのかも知れません。

というわけで、type_traitsで便利な型が作れた～と喜んでいると、落とし穴を掘っている可能性があるよ、という事例でした。テンプレートメタプログラミングは、用法用量を守って正しくお使いください。

検証環境です。

追記(2023-12-21)

Twitter(X)でこんなご指摘をいただきました。

なるほど？

ふむふむ、bool値との比較演算は無理でも、条件式や三項演算子でそのまま評価する場合は「明示的な型変換」の範疇にしてくれるみたいですね。それなら良さそうです。

struct Handle {
  size_t id;
  explicit operator bool() const { return id != 0; }
};

こうすると

prog.cc:35:16: error: implicit instantiation of undefined template 'Hasher<Handle>'
   35 |   std::cout << Hasher<Handle>()(h0) << std::endl;
      |                ^
prog.cc:11:8: note: template is declared here
   11 | struct Hasher;
      |        ^

コンパイルエラーになってくれました！ありがたい……。
というわけで、今回学んだことは次のようになります。

ハッシュ関数のデフォルト実装を定義すると、非explicitな数値型へのキャスト演算子が定義されている型において、意図しない挙動を引き起こす可能性がある
これを避けるには、キャスト演算子には可能な限りexplicitを付けるか、ハッシュ関数の特殊化を明示的に実装する必要がある

記事を書いたら新たな学びが得られました。やっぱり記事を書くのはいいことですね！

ちなみにちょいちょいリンクさせていただいているcpprefjpは、スポンサーシップを募集しております。
https://opencollective.com/cpprefjp
私もささやかながらスポンサーしてます。
C++で日頃お世話になっている方は、是非ご検討ください。

追記(2023-12-21)

Discussion