boost::hashとsize_t/long long

C++ Boost Hash

昨日の遅すぎた乱数生成を改良して、そこそこのスピードで動くようにしました。

  • mt19937＆uniform_int＆variate_generatorを使うと浮動小数点演算になって遅すぎる→rand48で代用
  • CRC32も重い→boost::hashで代用
  • なぜかLinuxで時間系の関数が異様に遅い(VMwareのせい？)→i386のみRDTSCで代用


で、問題はboost::hashです。

template<typename T> 
struct hash : public std::unary_function<T, std::size_t> {
  std::size_t operator()(T const&) const;
};

見ての通り、ハッシュ値の型がsize_tです。size_tだとサイズが不明なので、精度のよいハッシュ関数の実装が難しくなります。
さらに悪いことに、(unsigned)long long用のハッシュ関数は現在のところ定義されていません。(CVS HEADのコメントによると1.35以降のサポート予定)
そのため、

などの問題が発生します。
要は、typedefされた型をハッシュする場合に、サイズを確認して場合分けしてやればよいのです。今後も使いそうなので別ファイルに用意しました。

// uint64_t用ハッシュ関数
inline std::size_t hash_value_ui64(boost::uint64_t val);

// int64_t用ハッシュ関数
inline std::size_t hash_value_i64(boost::int64_t val);

// 汎用(64ビット以下)整数用ハッシュ関数
template<class T>
inline std::size_t hash_value_integer(T val);

// ハッシュ値をuint32_tに変換
inline boost::uint32_t hash_value_to_ui32(std::size_t seed);

通常、boost::hashに新しい型を対応させる場合、その型の名前空間でhash_value()関数を実装してADL経由で見つけてもらうのですが、勝手にlong long用の実装を追加するわけにもいかないので、別の名前で用意しています。
当然boost::hashからは呼んでくれないので、上記の関数を直接呼ぶ必要があります。
面倒ですけどね。