[解決済み] boost::hash_combine のマジックナンバー

質問

質問 boost::hash_combine テンプレート関数は、ハッシュへの参照( seed と呼ばれる)とオブジェクト v . によると ドキュメントによると によると、それは seed のハッシュと v によって

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

これが決定論的であることがわかります。XORが使われる理由もわかります。

足し算は似たような値を大きく離してマッピングするのに役立つので、ハッシュテーブルのプロービングが破綻しないのは確かですが、魔法の定数が何なのか、誰か説明してくれませんか？

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

マジックナンバーは32のランダムなビットで、それぞれが0か1である可能性が等しく、ビット間に単純な相関がないものとされています。このようなビットの文字列を見つける一般的な方法は、無理数の 2 進展開を使用することで、この場合、その数は黄金比の逆数となります。

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

つまり、この数字を含めると、シードの各ビットがランダムに変更されます。古い種をシフトしたものを含めることで、仮に hash_value() がかなり小さな値の範囲であったとしても、違いはすぐにすべてのビットに広がります。