1

unordered_mapC++ では、順不同の連想コンテナー ( 、unordered_set、 など)ごとunordered_multimapにハッシュ関数を定義する必要があります。ウィキペディアで指摘されているように、

struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};

struct hash_Xのカスタムハッシュ関数ですstruct X。しかし、この関数は何をするのでしょうか? なぜハッシュ関数が必要なのですか? 他のタイプのカスタム ハッシュ関数はありますか? もしそうなら、どのように2つのそのような機能間の効率を比較しますか.

4

2 に答える 2

3

ハッシュ関数の目的は、任意のデータ構造の内容を整数にマップして、遭遇する可能性が高いアイテムのほとんどが異なる整数にマップされ、アイテムの完全なセットが異なる整数にマップされるようにすることです。一緒に遭遇することは、整数のセット全体に均等に広がります。unordered_mapこのような関数があれば、任意のアイテムを非常に高速に検索するコンテナー ( など) を簡単に作成できます。

定義がやや抽象的であることに気づきました。より具体的には、上記のウィキペディアからの例を考えてみましょう。ハッシュ値を形成するために、構造体のi、jおよびフィールドをXOR します。kこれは有効なハッシュ関数です (構造を 1 つの整数にマージしました)。しかし、 と がすべて同様の範囲の値を持つ場合i、jそれkは非常に優れたハッシュ関数ではない可能性があります。たとえば、(1,2,3)両方(3,1,2)とも同じ値にハッシュされます。

理想的なハッシュ関数は通常、乱数ジェネレーターに似ています。予測可能な入力に対して、一見ランダムな出力が得られます。(ただし、同じ入力は常に同じ出力を与える必要があることに注意してください。) データ構造に最適なハッシュ関数は、ハッシュするデータの種類によって異なります。

この一連の講義ノートは、重要なポイントのほとんどをカバーしているように見えます: http://www.cs.cornell.edu/Courses/cs312/2008sp/lectures/lec21.html

グーグルで他の人を見つけることができます。

于 2013-12-07T02:38:42.033 に答える
1

簡単な答え: 要素を非常に高速に検索するため。

要素を何らかの形式red-black trees(または別の AVL ツリー) に格納する順序付きコンテナーとは対照的に、順序なしコンテナーindexed bucketsはノードを格納するために使用します。インデックスによるバケットの取得はO(1)複雑です。

Hash function要素を取り、それをそのような整数インデックスに変換する関数です。

その結果、インデックスのドメインがすべての要素のドメインよりも小さいため、collisionが発生する可能性があり、より多くの要素を 1 つのバケットに配置できるため、要素ルックアップの有効性が低下します。したがって、衝突の可能性が最も低いことは、間違いなく、努力すべきハッシュ関数の特性です。もう1つは、ハッシュ計算の有効性です。

さらなる分析については、完全ハッシュ関数を参照してください

于 2013-12-07T02:38:04.410 に答える