Boost の hash_combine 関数が「マジック定数」を使用するのはなぜですか?

Boost の hash_combine: 魔法の定数によるハッシュ品質の向上

boost::hash_combine 関数は、ハッシュ テーブルで使用すると重要な役割を果たします値を効率的に分配し、衝突シナリオを軽減します。その決定論的な性質により一貫性が保証されますが、「魔法の定数」を含めることでその重要性について疑問が生じます。

魔法の定数の公開

魔法の定数、0x9e3779b9 で示されます。 、固有のプロパティを保持します。これは 32 個のランダム ビットで構成され、各ビットは等しい確率で次のいずれかになります。 0 または 1。直感的な仮定に反して、この定数は無計画に選択されたものではなく、黄金比の逆数である無理数から導出されます。

具体的には、この定数は、 2^32 / phi のバイナリ展開。phi は黄金比を表します。これにより、定数と組み合わせたときにシードの各ビットがランダムに変換されるようになります。

ビット操作の利点

定数を組み込むことで、関数は 2 つの重要な機能を実現します。目標:

1. 広範囲分布: 定数がランダムに変化するためシードのすべてのビットにおいて、同様の値は大幅に離れてマッピングされます。これにより、隣接するハッシュ テーブル インデックスに連続したキーが存在する可能性が減り、プローブ操作の効率が向上します。
2. 分散の強化: 古いシードのシフトされたバージョンの追加により、相違点を分散させることができます。 hash_value() が限定された範囲の値を生成する状況のすべてのビット。このステップでは、シードにデルタを導入することで、入力値の小さな偏差が、結合されたハッシュの大きな偏差につながるようにします。

以上がBoost の hash_combine 関数が「マジック定数」を使用するのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。