5

Account と Transaction の 2 つのオブジェクトがあります。ここで、Transaction は Account と増分 ID 番号の一意のペアです。boost::hash を使用してこれらの一意の値を取得し、指示に従って hash_value メソッドをオーバーロードしたい: http://www.boost.org/doc/libs/1_53_0/doc/html/hash/custom.html

class Account {
  ...
};

class Transaction
{
    Account account;
    unsigned int id;
};

アカウントの hash_value メソッドは正しく機能し、返される値は特定のアカウントに対して常に一意ですが、一意のペアを作成するには、トランザクションのメソッドで hash _combine を使用する必要があります (ブーストの指示に従って):

inline std::size_t hash_value( const Account& acct )
{
    boost::hash<int> hasher;
    size_t rval = hasher( acct.id() ); //just an int. guaranteed to be unique
    return rval;
}


inline std::size_t hash_value( const Transaction& t )
{
    std::size_t seed = 0;
    boost::hash_combine( seed, t.account );        
    boost::hash_combine( seed, t.id );

    return seed;
}

これにより、異なる入力に対して同じ値が返されることがあります。どうして？？私は数千のアカウントしか持っておらず、ID 番号は数十万しかありません。これは上限の問題ではないようです。

これがバグなのか、それともブーストハッシュをシードする必要があるのか​​ 誰か知っていますか?

ありがとう

4

2 に答える 2

1

Boost は、入力に関する仮定をまったくまたはほとんど行わず、高速化を試みるため、優れた一般的なハッシュ関数を提供します。ほとんどの場合、ブーストから得られるものよりもはるかに優れたハッシュ関数を作成するために、入力について特定の仮定を行うことができます。たとえば、文字列に英語のテキストが含まれていると仮定して、文字列ハッシュ関数を最適化できます。仮定を使用することで、はるかに優れたハッシュ関数を作成できます (たとえば、衝突がはるかに少なくなります)。たとえば、それぞれが 1 から 1000 までの整数である 2 つのハッシュ値をマージする必要がある場合、それらの 1 つに 1000 を掛けてからもう 1 つを追加すると、衝突が発生しないことは明らかです。

カスタム ハッシュ関数を作成するときは十分に注意してください。コードの堅牢性は常に損なわれます。

例 1: 英語の文字列の UTF-8 文字列ハッシュを最適化します。突然、アプリケーションは中国語の文字列を取得します。

例 2: ID は 1 から始まり、割り当てられるたびに 1 ずつ増加し、割り当てられる数が数千を超えることはないため、ID は常に小さいと想定します。誰かが ID をランダムな GUID に変更します。

于 2013-05-02T21:45:45.980 に答える