3

ローカルオブジェクトには、照合ファセットがあります。

照合ファセットには、longを返すハッシュメソッドがあります。
http://www.cplusplus.com/reference/std/locale/collat​​e/hash/

2つの質問：

  • 誰もがどのハッシュ方法が使用されているか知っていますか。
  • 32ビット値が必要です。
    私のlongが32ビットより長い場合、ハッシュを短いバージョンに折りたたむ方法を知っている人はいますか。誤って折りたたむと多くの衝突が発生する可能性があることがわかります（とにかくそれを考慮する必要があるので衝突に対処できますが、最小化したほうがいいと思います）。

注：C++0x機能を使用できません。Boost
で問題ない場合があります。

4

2 に答える 2

4

いいえ、実際のところは誰にもわかりません。実装ごとに異なる可能性があります。主な要件は次のとおりです (N3092、§20.8.15):

特殊化ハッシュが存在するすべてのオブジェクト タイプ キーの場合、インスタンス化ハッシュは次のようになります。

  1. ハッシュ要件 (20.2.4) を満たし、Key を関数呼び出しの引数の型として使用し、DefaultConstructible 要件 (33)、CopyAssignable 要件 (37)、
  2. 左辺値のスワップ可能 (20.2.2)、
  3. それぞれ size_t と Key の同義語となる 2 つのネストされた型 result_type と argument_type を提供します。
  4. k1 == k2 が true の場合、h(k1) == h(k2) も true であるという要件を満たします。ここで、h は hash 型のオブジェクトであり、k1 と k2 は Key 型のオブジェクトです。

および (N3092、§20.2.4):

タイプ H は、次の場合にハッシュ要件を満たします。

  1. 関数オブジェクト型 (20.8) です。
  2. CopyConstructible および Destructible (20.2.1) の要件を満たします。
  3. 次の表に示す式が有効であり、示されたセマンティクスを持っている。
  4. それは、この節の他のすべての要件を満たしています。

§20.8.15 はハッシュの結果に関する要件をカバーし、§20.2.4 はハッシュ自体に関する要件をカバーしています。ただし、ご覧のとおり、どちらもかなり一般的です。言及されている表は、基本的にさらに 3 つの要件をカバーしています。

  1. ハッシュ関数は「純粋」でなければなりません (つまり、結果は入力のみに依存し、コンテキストや履歴などには依存しません)。
  2. 関数は、渡された引数を変更してはなりません。
  3. 例外をスローしてはなりません。

ただし、正確なアルゴリズムは明確に指定されていません。長さにもかかわらず、上記の要件のほとんどは、(少なくとも私には) かなり明白に見える要件を述べているだけです。要するに、実装は、ほぼどのような方法でもハッシュを自由に実装できます。

于 2010-10-12T01:14:10.817 に答える
0

実装が妥当なハッシュ関数を使用する場合、ハッシュ値には、入力と特別な相関関係を持つビットがあってはなりません。したがって、ハッシュ関数が 64 の「ランダム」ビットを与えるが、そのうちの 32 ビットだけが必要な場合は、値の最初/最後/... 32 ビットを好きなように取ることができます。すべてのビットが次のビットと同じくらいランダムであるため、どれを取るかは問題ではありません (これが優れたハッシュ関数を作る理由です)。

したがって、32 ビットのハッシュ値を取得する最も簡単で完全に合理的な方法は次のようになります。

int32_t value = hash(...);

(もちろん、これは 40 億の値のグループを 1 つにまとめます。これは多くのように見えますが、ターゲット値の 40 億倍のソース値がある場合、これは避けられません。)

于 2010-10-12T01:25:58.737 に答える