ホーム>source

整数の決定論的な(複数実行、複数マシン)ハッシュを探している間、私は boost::hash_combine(size_t & seed, T const& v) につまずいた 。残念ながら、ドキュメンテーション それは述べられている

This hash function is not intended for general use, and isn't guaranteed to be equal during separate runs of a program - so please don't use it for any persistent storage or communication.

ただし、実装を見てみると、別々の実行で発散する動作を引き起こす可能性のある疑わしいコードは見られませんでした-いくつかの乗算と加算(オーバーフローが発生する可能性があります)、ビットシフトとxor操作、すべて定数を使用しています。さらに、hasherは複数回実行されたときに一貫して動作しました。

それでは、実行全体にわたって決定論を保証することを禁じている実際の問題はどこにあるのでしょうか?

最も興味深い部分の下に貼り付けます:

template <class T>
inline void hash_combine(std::size_t& seed, T const& v)
{
    boost::hash<T> hasher;
    return boost::hash_detail::hash_combine_impl(seed, hasher(v));
}
template <typename T>
typename boost::hash_detail::basic_numbers<T>::type hash_value(T v)
{
    return static_cast<std::size_t>(v);
}
inline void hash_combine_impl(boost::uint64_t& h,
        boost::uint64_t k)
{
    const boost::uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
    const int r = 47;
    k *= m;
    k ^= k >> r;
    k *= m;
    h ^= k;
    h *= m;
    // Completely arbitrary number, to prevent 0's
    // from hashing to 0.
    h += 0xe6546b64;
}

あなたの答え
  • 解決した方法 # 1

    ハッシュはハッシュテーブルで頻繁に使用されるためです。 (ハッシュテーブルを含むC ++コードを使用する)サービスを攻撃しようとする悪意のあるユーザーは、ハッシュテーブルに挿入されたアイテムのハッシュ衝突を強制することでパフォーマンスを大幅に低下させる可能性があります(O(1)からO(N)に移行する一般的な操作のパフォーマンス)。実行ごとに異なるハッシュ関数を使用することにより、これは非常に困難になります。

    std::hash  そのように標準化されています。 https://en.cppreference.com/w/cpp/utility/hashを引用するには:

    Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision DoS attacks.(since C++ 14)

  • 前へ java - JPAクエリ:サブクエリをグループ化条件に結合する
  • 次へ pandas - マルチインデックスデータフレームをXarrayデータセットに変換すると、年間シーケンスが失われるか、エラーが発生します。