読者です 読者をやめる 読者になる 読者になる

boost::hash_combine()のマジックナンバー

C++

クラスやコンテナのような、複数の値からハッシュ値が決定する場合に使用するboost::hash_combine()ですが、その効果を見てみると以下のように書いてあります:

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

この0x9e3779b9というマジックナンバーは何なのか。


StackOverflowに答えが書いてありました。
Magic numbers in boost::hash_combine

The magic number is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits. A common way to find a string of such bits is to use the binary expansion of an irrational number; in this case, that number is the reciprocal of the golden ratio:

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

要約すると、元となるハッシュ値が小さい範囲の値である場合でも、偏らない値を生成するための値だそうです。