17

無限の数の文字列を 32b int にハッシュすると衝突が発生する必要があることはわかっていますが、ハッシュ関数には適切な分布が期待されます。

これら 2 つの文字列が同じハッシュを持つのは奇妙ではありませんか?

size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
//hash0 == hash1

やその他を使用できることはわかってboost::hash<std::string>いますが、 の何が問題なのか知りたいですstd::hash。私はそれを間違って使用していますか？どういうわけかそれを「シード」するべきではありませんか？

4

5 に答える 5

28

の使用法に問題はありませんstd::hash。問題は、std::hash<std::string>Visual Studio 2010にバンドルされている標準ライブラリの実装によって提供される特殊化は、ハッシュ値を決定するために文字列の文字のサブセットのみを使用することです（おそらくパフォーマンス上の理由から）。偶然にも、14文字の文字列の最後の文字はこのセットの一部ではありません。そのため、両方の文字列が同じハッシュ値を生成します。

私の知る限り、この動作は標準に準拠しており、同じ引数を使用したハッシュ関数への複数の呼び出しは常に同じ値を返す必要があることだけを要求しています。ただし、ハッシュ衝突の可能性は最小限に抑える必要があります。VS2010の実装は必須の部分を満たしていますが、オプションの部分を考慮していません。

詳細については、ヘッダーファイルの実装xfunctional（私のコピーの869行目から）およびC ++標準の§17.6.3.4（最新の公開ドラフト）を参照してください。

文字列に対してより優れたハッシュ関数がどうしても必要な場合は、自分で実装する必要があります。実際にはそれほど難しいことではありません。

于 2011-11-01T16:24:03.240 に答える
11

正確なハッシュ アルゴリズムは標準で指定されていないため、結果は異なります。VC10 で使用されるアルゴリズムは、文字列が 10 文字を超える場合、すべての文字を考慮していないようです。の増分で進みます1 + s.size() / 10。これは合法ですが、QoI の観点からはかなり残念です。このようなハッシュ コードは、一部の典型的なデータ セット (URL など) に対してはパフォーマンスが非常に悪いことが知られています。FNV ハッシュまたはメルセンヌ素数に基づくハッシュに置き換えることを強くお勧めします。

FNV ハッシュ:

struct hash
{
    size_t operator()( std::string const& s ) const
    {
        size_t result = 2166136261U ;
        std::string::const_iterator end = s.end() ;
        for ( std::string::const_iterator iter = s.begin() ;
              iter != end ;
              ++ iter ) {
            result = (16777619 * result)
                    ^ static_cast< unsigned char >( *iter ) ;
        }
        return result ;
    }
};

メルセンヌ素数ハッシュ:

struct hash
{
    size_t operator()( std::string const& s ) const
    {
        size_t result = 2166136261U ;
        std::string::const_iterator end = s.end() ;
        for ( std::string::const_iterator iter = s.begin() ;
              iter != end ;
              ++ iter ) {
            result = 127 * result
                   + static_cast< unsigned char >( *iter ) ;
        }
        return result ;
    }
};

(FNV ハッシュの方が優れていると思われますが、127 を掛けると 16777619 を掛けるよりも大幅に高速になることが多いため、多くのマシンでは Mersenne 素数ハッシュの方が高速になります。)

于 2011-11-01T16:44:03.050 に答える
3

おそらく異なるハッシュ値が得られるはずです。異なるハッシュ値を取得します (GCC 4.5):

ハッシュテスト.cpp

#include <string>
#include <iostream>
#include <functional>
int main(int argc, char** argv)
{
size_t hash0 = std::hash<std::string>()("generated_id_0");
size_t hash1 = std::hash<std::string>()("generated_id_1");
std::cout << hash0 << (hash0 == hash1 ? " == " : " != ") << hash1 << "\n";
return 0;
}

出力

# g++ hashtest.cpp -o hashtest -std=gnu++0x
# ./hashtest
16797002355621538189 != 16797001256109909978
于 2011-11-01T15:37:49.313 に答える
2

ハッシュ関数をシードするのではなく、せいぜい「それら」をソルトすることができます。

この関数は正しい方法で使用されており、この衝突は偶然の可能性があります。

ランダムキーを使用して大規模なテストを実行しない限り、ハッシュ関数が均等に分散されていないかどうかはわかりません。

于 2011-11-01T15:26:25.340 に答える
0

TR1ハッシュ関数と最新の標準は、文字列などの適切なオーバーロードを定義します。std :: tr1 :: hash（g ++ 4.1.2）を使用してこのコードを実行すると、これら2つの文字列に対して異なるハッシュ値を取得します。

于 2011-11-01T15:26:39.777 に答える