3

より高速なアクセスのために unordered_map と map のどちらを使用すべきかという質問がよく寄せられます。この質問に対する最も一般的な (かなり古い) 回答は次のとおりです。

そのような選択を行う際に、キーのデータ型を考慮する必要はありませんか? 1 つの dataType (int など) のハッシュ アルゴリズムは、他のもの (string など) よりも衝突しやすい可能性があるためです。

その場合（ハッシュアルゴリズムは非常に衝突しやすい）、unordered_mapマップのO（1）定数時間（おそらく多数の入力で平均化される）のように、直接アクセスでもマップを使用する可能性がありますN の値がかなり大きい場合でも、lg(N) を超えます。

4

3 に答える 3

3

あなたは良い点を挙げています...しかし、あなたは間違った部分に焦点を合わせています。

問題はキーのタイプ自体ではなく、そのキーのハッシュ値を導出するために使用されるハッシュ関数にあります。

辞書式順序付けは簡単です: 3 つのフィールドに従って構造体を順序付けしたい場合 (そして、それらは既に順序付けをサポートしています)、次のように記述します。

bool operator<(Struct const& left, Struct const& right) {
    return boost::tie(left._1,  left._2,  left._3)
         < boost::tie(right._1, right._2, right._3);
}

そして、私は終わりました！

しかし、ハッシュ関数を書くのは難しいです。データ (統計) の分布に関する知識が必要であり、特別に細工された攻撃を防ぐ必要があるかもしれません。正直なところ、多くの人が適切なハッシュ関数を作成できるとは思っていません。しかし、最悪の部分は、構成も難しいことです! 2 つの独立したフィールドが与えられた場合、それらのハッシュ値を正しく組み合わせるのは困難です (ヒント: boost::hash_combine)。

実際、自分が何をしているのかわからず、ユーザーが作成したデータを扱っている場合は、map. 遅くなるかもしれませんが（確かではありません）、より安全です。

于 2012-11-10T16:43:36.663 に答える
2

これは使用するハッシュ関数に依存するため、衝突しやすいオブジェクトなどは実際にはありません。オブジェクトが同一ではないと仮定すると、使用される有益なハッシュ関数を作成するために利用できるいくつかの機能があります。

データについてある程度の知識があり、一部のハッシュ関数に対して多くの衝突が発生する可能性があることを知っていると仮定すると、このタスクにより適しh1()た別のハッシュ関数を見つけて使用する必要があります。h2()

そうは言っても、ハッシュベースよりもツリーベースのデータ構造を優先する理由は他にもあります (レイテンシーやセットのサイズなど)。一部は、このスレッドの私の回答でカバーされています。

于 2012-11-10T16:21:11.890 に答える
1

これについて賢くなりすぎても意味がありません。いつものように、プロファイルを作成し、比較し、役立つ場合は最適化します。関連する要因は多数ありますが、そのうちのかなりの数は標準で指定されておらず、コンパイラによって異なります。特定のハードウェアでは、一部のプロファイルが良くなったり悪くなったりする場合があります。このようなことに興味がある (またはそのふりをしてお金を払っている) 場合は、これらのことについてもう少し体系的に学ぶ必要があります。実際のハッシュ関数とその特性について少し学ぶことから始めるかもしれません。すべての実用的な目的のために、ランダムだが反復可能な値よりも衝突しやすいハッシュ関数を見つけることができないことは非常にまれです.

于 2012-11-10T17:07:58.463 に答える