[解決済み] C++ - ハッシュ値を結合するのにboost::hash_combineが最適なのはなぜですか？

質問

他の投稿で、ハッシュ値の組み合わせはこれがベストのようだと読みました。どなたかこれを分解して、なぜこれが最良の方法なのかを説明していただけませんか？

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

編集部：もう一つの質問はマジックナンバーを聞いているだけですが、この部分だけでなく、関数全体について知りたいのです。

どのように解決するのですか？

ベストであることは議論の余地がある。

少なくとも表面的には、「良い」、あるいは「とても良い」というのは、簡単なことです。

seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);

を想定しています。 seed は以前の結果である hasher またはこのアルゴリズムを使用します。

^= は、左のビットと右のビットがすべて結果のビットを変更することを意味します。

hasher(v) に対するまともなハッシュであると推定される。 v . しかし、残りはまともなハッシュでない場合の防御である。

0x9e3779b9 は32ビットの値です（もし size_t これは基本的に、特定の不合理な定数をbase-2の固定小数点値で近似することによって行われる0と1のランダムな系列である。 これは、ハッシャーが悪い値を返しても、出力に1と0が混じっていることを保証するのに役立ちます。

(seed<<6) + (seed>>2) は、入力されるシードのビットシャッフルである。

を想像してください。 0x 定数が欠落していた。 ハッシャーが定数を返すと想像してください 0x01000 に対して、ほぼすべての v が渡される。 さて、シードの各ビットは、ハッシュの次の繰り返しで、その間に再び拡散されます。

は、その seed ^= (seed<<6) + (seed>>2) 0x00001000 になります。 0x00041400 を1回繰り返した後。 次に 0x00859500 . この操作を繰り返すと、セットされたビットは出力ビットの上に "smeared out" されます。 最終的には、左右のビットが衝突し、キャリーによってセットビットが偶数位置から奇数位置に移動します。

入力された種の値に依存するビットは、コンバイン操作が種の操作に再帰するため、比較的速く、複雑な方法で成長する。 追加するとキャリーが発生し、さらに汚くなる。 そのため 0x 定数は擬似ランダムビットの束を追加し、結合後のハッシュ空間の数ビット以上を退屈なハッシュ値が占めるようにします。

加算のおかげで非対称である(ハッシュを結合するのは "dog" と "god" また、つまらないハッシュ値も扱える（文字をASCII値に対応させるが、これはほんの少しビットをいじるだけ）。 そして、それなりに速い。

暗号学的に強力な低速のハッシュ結合は、他の状況ではより良いことがあります。 私は素朴に、シフトを偶数と奇数の組み合わせにするのは良いアイデアかもしれないと推測しています（しかし、奇数ビットから偶数ビットを移動させる加算では問題が少ないかもしれません：3回繰り返した後、入ってくる単独の種ビットが衝突して加算しキャリーが発生するため）。

このような分析の欠点は、たった1つのミスでハッシュ関数が本当に悪いものになってしまうことです。 良いところばかりを指摘しても、それほど役には立ちません。 ですから、今現在のもう一つの良い点は、それなりに有名でオープンソースのレポジトリにあり、なぜそれが悪いのかという指摘を誰も聞いたことがないことです。