8

std::hash（たとえば、doublesまたはsの）浮動小数点の特殊化は、ほぼ等式floatに関して信頼できますか？つまり、2つの値（となど）が等しいと比較する必要があるが、演算子ではそうしない場合、どのように動作しますか？(1./std::sqrt(5.)/std::sqrt(5.)).2==std::hash

それで、私は期待どおりに機能するための鍵doubleとしてに頼ることができますか？std::unordered_map

「浮動小数点値のハッシュ」を見たことがありますが、それはブーストについて尋ねます。C++11の保証について質問しています。

4

4 に答える 4

11

std::hashインスタンス化できるすべてのタイプに対して同じ保証があります。2つのオブジェクトが等しい場合、それらのハッシュコードは等しくなります。そうでなければ、彼らがそうしない可能性が非常に高くなります。doubleしたがって、aをキーとして 信頼して、unordered_map期待どおりに機能させることができます。2つのdoubleが等しくない場合（で定義されて==いるように）、ハッシュは異なる可能性があります（そうでない場合でも、異なるキーです。同等性 unordered_mapもチェックするため）。

明らかに、値が不正確な計算の結果である場合、それらはunordered_map （またはおそらくどのマップにとっても）適切なキーではありません。

于 2013-02-18T19:42:10.477 に答える
8

この質問に関する複数の問題：

  • 2つの式が等しく比較されない理由は、0.2の2進式が2つあるからではなく、、0.2またはsqrt(5)！の正確な（有限の）2進表現がないためです。したがって、実際には、(1./std::sqrt(5.)/std::sqrt(5.))と.2は代数的に同じである必要がありますが、コンピューター精度の算術では同じではない可能性があります。（それらは有限の精度での紙にペンで計算することさえできません。小数点以下10桁で作業しているとしましょう。10桁で書きsqrt(5)、最初の式を計算します。そうではありません.2。）

  • もちろん、2つの数値が近いという賢明な概念があります。実際には、少なくとも2つあります。1つは絶対（|a-b| < eps）、もう1つは相対です。しかし、それは賢明なハッシュにはなりません。eps相互に存在するすべての数値に同じハッシュを持たせたい場合は1, 1+eps, 1+2*eps, ...、すべて同じハッシュを持つため、すべての数値に同じハッシュが割り当てられます。これは有効ですが、役に立たないハッシュ関数です。ただし、近くの値を同じハッシュにマッピングするという要件を満たすのはこれだけです。

于 2013-02-18T19:43:19.993 に答える
3

のデフォルトのハッシュの背後にはunordered_map、指定された値のハッシュを計算するためのstd::hash構造体があります。operator()

std::hash<float>およびを含む、このテンプレートのデフォルトの特殊化のセットを使用できますstd::hash<double>。

私のマシン（LLVM + clang）では、これらは次のように定義されています

template <>
struct hash<float> : public __scalar_hash<float>
{
    size_t operator()(float __v) const _NOEXCEPT
    {
        // -0.0 and 0.0 should return same hash
       if (__v == 0)
           return 0;
        return __scalar_hash<float>::operator()(__v);
    }
};

ここで、__scalar_hashは次のように定義されます。

template <class _Tp>
struct __scalar_hash<_Tp, 0> : public unary_function<_Tp, size_t>
{
    size_t operator()(_Tp __v) const _NOEXCEPT
    {
        union
        {
            _Tp    __t;
            size_t __a;
        } __u;
        __u.__a = 0;
        __u.__t = __v;
        return __u.__a;
    }
};

基本的にハッシュは、和集合の値をソース値に設定し、次に、として大きい部分だけを取得することによって構築されますsize_t。

したがって、パディングを取得するか、値を切り捨てますが、数値の生のビットがハッシュの計算に使用されることがわかるため、これは==演算子として正確に機能することを意味するため、実際には問題ではありません。同じハッシュ（切り捨てによって与えられる衝突を除く）を持つ2つの浮動小数点数は、同じ値でなければなりません。

于 2014-12-12T04:52:32.947 に答える
2

「ほぼ平等」という厳密な概念はありません。そのため、原則として動作を保証することはできません。「ほぼ等しい」という独自の概念を定義し、2つの「ほぼ等しい」フロートが同じハッシュを持つようにハッシュ関数を作成する場合は、次のことができます。しかし、それは「ほぼ等しい」フロートの特定の概念にのみ当てはまります。

于 2013-02-18T19:29:39.593 に答える