10

私がstd::hash使用してlibstdc++から、次のC++11VS 2012ライブラリで使用した場合、それらは一致しますか?

ハッシュの実装は C++ 仕様の一部ではなく、ディストリビューションによって異なる可能性があると思いますか?

4

3 に答える 3

9

いいえ、これは保証されません。std::hash次の条件のみを尊重する必要があります。

  1. Key 型の 1 つのパラメーターを受け入れます。
  2. パラメータのハッシュ値を表す size_t 型の値を返します。
  3. 呼び出されたときに例外をスローしません。
  4. 等しい 2 つのパラメータ k1 と k2 の場合、std::hash()(k1) == std::hash()(k2)。
  5. 等しくない 2 つの異なるパラメーター k1 と k2 の場合、 std::hash()(k1) == std::hash()(k2) である確率は非常に小さくなり、1.0/std::numeric_limits::max に近づきます。 ().

http://en.cppreference.com/w/cpp/utility/hash

于 2012-08-16T15:47:22.397 に答える
9

標準はこれだけを言っています：

20.8.12 クラス テンプレート ハッシュ 23.5 で定義されている順不同の連想コンテナは、クラス テンプレート ハッシュの特殊化をデフォルトのハッシュ関数として使用します。特殊化ハッシュが存在するすべてのオブジェクト タイプ Key について、インスタンス化ハッシュは次のことを行う必要があります。

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

17.6.3.4 では、これが最も重要です (表 26)。

例外をスローしません。返される値は、引数 k のみに依存します。[ 注: したがって、k の値が同じである式 h(k) のすべての評価は、同じ結果をもたらします。— 終わりの注 ] [ 注: 2 つの異なる値 t1 と t2 の場合、h(t1) と h(t2) が等しい確率は非常に小さく、1.0 / numeric_- limits::max() に近づくはずです。— エンドノート]

したがって、一般的に、いいえ、計算自体は定義されておらず、結果は実装全体で一貫している必要はありません。さらに言えば、同じライブラリの 2 つの異なるバージョンでも、異なる結果が得られる場合があります。

于 2012-08-16T15:47:51.893 に答える
5

関数によって返される値の要件 ( 17.6.3.4 ハッシュ要件 [hash.requirements] ) は次のとおりです。Hash

表 26 — ハッシュ要件 [ハッシュ]

返される値は、引数のみに依存しますk。[ 注: したがってh(k)、同じ値を持つ式のすべての評価はk同じ結果をもたらします。—終わりの注] [ 注: 2 つの異なる値t1との場合、とが等しいt2確率は 非常に小さく、 に近づくはずです。—終わりのメモ]h(t1)h(t2)1.0 / numeric_limits<size_t>::max()

実際には、標準に準拠した最も単純な実装であるため、整数型std::hash(k)が equalになることは非常に一般的です。k他のタイプについては、何でも可能です。

于 2012-08-16T15:50:04.593 に答える