スポンサーリンク

| キーワード:

C++の64bit版のhash_combine

Boostのhash_combineの64bit版

https://github.com/HowardHinnant/hash_append/issues/7

最新のC++にはBoostから正式に仕様に含められたhashが「unordered_map」という名前で入っているが、hash_combineは取り入れられていないらしい。なので自分で作る必要がある。

この時、多くはBoostを参考にすると思うのだが、Boostの中のマジックナンバーがどうやら32bitのもので、64bit版の場合、この数字はどうなるんだ?というのが上記サイトの議論の内容となっている。

そもそもこの数字はTEAアルゴリズムというものが根拠らしく、64bitの場合と、さらに128bitの場合の値が上げられている。

ビット数16進数表記の値
80x9e
160x9e37
320x9e3779b9
640x9e3779b97f4a7c15
1280x9e3779b97f4a7c15f39cc0605d396154

そして64bitは32bitの二倍なので、シフト量も二倍にする。

seed ^= std::hash<T>{}(val) + 0x9e3779b9U + (seed<<6) + (seed>>2);

seed ^= std::hash<T>{}(val) + 0x9e3779b97f4a7c15LLU + (seed<<12) + (seed>>4);

なおこの(Boostの)HashCombineはさして優れているわけでは無いと言うことで、別の方法があるならそれを使うべきと言うような主張をちらほら見かける。

CityHashからの借用

https://stackoverflow.com/questions/8513911/how-to-create-a-good-hash-combine-with-64-bit-output-inspired-by-boosthash-co

CityHashはGoogleが考案したハッシュアルゴリズムで、MITライセンス(らしい)。そこから転用したコードが紹介されている。

template <class T> inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    const std::size_t kMul = 0x9ddfea08eb382d69ULL;
    std::size_t a = (hasher(v) ^ seed) * kMul;
    a ^= (a >> 47);
    std::size_t b = (seed ^ a) * kMul;
    b ^= (b >> 47);
    seed = b * kMul;
}

(このスニペットは、CityHashコードの「実質的な部分」を構成するものではないため、ここや他の場所に複製しても問題ないと思いますが、CityHashのソースとライセンス契約を確認して、自分で決めてください)

(Google翻訳)

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)


この記事のトラックバックURL: