24

現在、C++ でハッシュ テーブルを実装しており、フロートのハッシュ関数を作成しようとしています...

10 進数をパディングして float を整数として扱うつもりでしたが、大きな数値でオーバーフローする可能性があることに気付きました...

フロートをハッシュする良い方法はありますか?

関数を直接提供する必要はありませんが、さまざまな概念を見たり理解したりしたいのですが...

ノート：

  1. 可能であれば均等に分散するだけで、本当に高速である必要はありません。

  2. 計算速度のためにフロートをハッシュすべきではないことを読みましたが、誰かがこれを確認/説明し、フロートをハッシュすべきではない他の理由を教えてもらえますか? 理由はよくわかりません（速度以外）

4

7 に答える 7

17

アプリケーションによって異なりますが、ほとんどの場合、正確な一致を高速に検索するためにハッシュが使用され、ほとんどの浮動小数点数は正しい答えの近似値にすぎない浮動小数点数を生成する計算の結果であるため、浮動小数点数をハッシュする必要はありません。浮動等価性をチェックする通常の方法は、それが正しい答えのデルタ (絶対値) 内にあるかどうかをチェックすることです。このタイプのチェックは、ハッシュ化されたルックアップ テーブルには適していません。

編集：

通常、丸め誤差と浮動小数点演算の固有の制限により、浮動小数点数aとbが互いに等しいはずであると予想される場合は、数学がそうであるため、比較的小さいを選択する必要があり、次にとが等しいdelta > 0ことを宣言します。の場合、は絶対値関数です。詳細については、この記事を参照してください。ababs(a-b) < deltaabs

問題を示す小さな例を次に示します。

float x = 1.0f;
x = x / 41;
x = x * 41;
if (x != 1.0f)
{
    std::cout << "ooops...\n";
}

プラットフォーム、コンパイラ、および最適化のレベルによっては、これがooops...画面に出力される場合があります。つまり、数式x / y * y = xがコンピューターで保持されるとは限りません。

浮動小数点演算が正確な結果を生成する場合があります。たとえば、適切なサイズの整数と 2 の累乗の分母を持つ有理数です。

于 2010-11-21T13:49:49.663 に答える
11

ハッシュ関数が次のことを行った場合、ハッシュルックアップである程度のあいまいさが発生します

unsigned int Hash( float f )
{
    unsigned int ui;
    memcpy( &ui, &f, sizeof( float ) );
    return ui & 0xfffff000;
}

このようにして、12個の最下位ビットをマスクして、ある程度の不確実性を考慮に入れます...ただし、実際にはアプリケーションによって異なります。

于 2010-11-21T14:03:19.990 に答える
9

std ハッシュを使用できますが、悪くはありません。

 std::size_t myHash = std::cout << std::hash<float>{}(myFloat);
于 2016-09-30T11:04:10.950 に答える
6 
unsigned hash(float x)
{
    union
    {
        float f;
        unsigned u;
    };
    f = x;
    return u;
}

技術的に未定義の動作ですが、ほとんどのコンパイラはこれをサポートしています。代替ソリューション:

unsigned hash(float x)
{
    return (unsigned&)x;
}

どちらのソリューションもマシンのエンディアンに依存するため、たとえば x86 と SPARC では異なる結果が生成されます。それが問題にならない場合は、これらの解決策のいずれかを使用してください。

于 2010-11-21T13:45:52.137 に答える
4

もちろん、 aを同じサイズfloatの型として表現しintてハッシュすることもできますが、この素朴なアプローチには注意が必要な落とし穴がいくつかあります...

等しい値が必ずしも同じバイナリ表現を持つとは限らないため、単純にバイナリ表現に変換するとエラーが発生しやすくなります。

明白なケース:たとえば-0.0 一致しません。*0.0

さらに、単純にint同じサイズの に変換するだけでは、非常に均等な分散が得られません。これは、多くの場合重要です (たとえば、バケットを使用するハッシュ/セットの実装)。

推奨される実装手順:

  • 非有限ケース ( nan、inf) および ( 0.0、-0.0 これを明示的に行う必要があるかどうかは、使用する方法によって異なります) を除外します。
  • int同じサイズの に変換します
    (つまり、単に int にキャストするのではなく、たとえばユニオンを使用して をfloatとしてint表します) 。
  • ビットを再配布します(ここでは意図的にあいまいにしています!)。これは基本的に速度と品質のトレードオフです。しかし、狭い範囲に多くの値がある場合は、それらを同様の範囲にしたくないでしょう。

*nan : (と-nan) もチェックしたくないかもしれません。それらを正確に処理する方法は、ユース ケースによって異なります ( nanCPython のように、すべての の符号を無視することもできます)。

Python のは、実稼働コードで , を_Py_HashDoubleハッシュする方法の良いリファレンスです(これは Python の特別な値であるため、最後のチェックは無視してください) 。float-1

于 2015-02-16T21:12:54.747 に答える