Boost::Hash_Combine がハッシュ値を結合するための最適な方法とみなされるのはなぜですか?

Boost::Hash_Combine: 効率的なハッシュ値の結合方法

概要:
レルム内プログラミングの観点から、ハッシュ値を効率的に組み合わせることが、ハッシュ テーブルやそれに依存するその他のデータ構造を実装するために重要です。ハッシュ関数。 Boost C ライブラリは、このタスクのために特別に設計された boost::hash_combine と呼ばれる関数を提供します。この記事では、boost::hash_combine の内部の仕組みを詳しく掘り下げ、これがハッシュ値を結合するための最適な方法であると考えられる理由を説明します。

関数の詳細:

boost::hash_combine は、シード値 (参照による) とハッシュされる値 (値による) の 2 つの引数を取ります。シード値は最初は空のハッシュ値であり、新しい値がハッシュされるたびにシードと結合されて、結合ハッシュ値が作成されます。この関数は次のように動作します。

1. std::hash を使用して新しい値のハッシュ値を作成します。
2. マジックナンバー 0x9e3779b9 を使用して新しいハッシュ値を XOR します。
3. シード値を6ビット左にシフトし、ステップの結果とXOR演算します。 2.
4. シード値を 2 ビット右にシフトし、ステップ 3 の結果と XOR 演算します。

分布およびエントロピー分析:

boost::hash_combine が最適であると考えられる主な理由の 1 つは、その優れた分散特性です。広範囲の入力から一意のハッシュ値を生成し、衝突を最小限に抑え、ハッシュ テーブルの効果を最大限に高めます。

ただし、boost::hash_combine の元の実装では、エントロピーの保存が理想的とは言えなかったことに注意することが重要です。これにより、シード値に大量のエントロピーが含まれている場合、エントロピーの損失が発生する可能性があります。

改善された代替案:

この制限に対処するために、hash_combine の修正バージョンが導入されました。 2 つの乗算と 3 つの XOR シフト演算。このバージョンでは、優れたミキシングが提供され、エントロピーがより効果的に保存されます。

実装:

変更された hash_combine 関数の実装例:

#include <cstdint>

template<typename T>
inline size_t hash_combine(std::size_t& seed, const T& v)
{
    const uint64_t c = 17316035218449499591ull; // random uneven integer constant
    const uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
    const uint64_t n = std::hash<T>{}(v);

    uint64_t x = p * xorshift(n, 32);
    uint64_t y = c * xorshift(x, 32);

    seed ^= y ^ (seed << 6);
    seed ^= (seed >> 2);

    return seed;
}

この実装は、効率的かつ非可換である非対称バイナリ回転を利用します。また、別の定数を使用し、XOR 演算を使用してシードとハッシュ値を結合します。

結論:

元の boost::hash_combine にはいくつかの欠点がありましたが、変更されたものはこのバージョンでは、エントロピーの保存と配布のプロパティが大幅に向上しました。複数の操作と慎重に選択された定数を使用することで、ハッシュ値を効果的に結合し、衝突を最小限に抑え、効率的なパフォーマンスを保証します。最適な結果を得るには、ハッシュ値を結合するときにこの修正バージョンの使用を検討してください。

以上がBoost::Hash_Combine がハッシュ値を結合するための最適な方法とみなされるのはなぜですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。