0

unordered_map<>（c ++ 11）は、ハッシュ関数を使用して、そのキー値を内部的に編成します。衝突確率は非常に小さい(1.f/std:numeric_limits<size_t>::max()です）。

unordered_map<>ヒープメモリ管理のストレージコンテナとして使用しても大丈夫ですか？つまり、2つの要素が（衝突によって）混同されると、プログラムの安定性が失われます。free()私の場合、同じポインタを繰り返し呼び出すことになります。（SIGSEGV）。

または、衝突の確率は、キーを検索するときにのみ重要です。そして、2つの異なるキーが常に異なる値を参照することが保証されていますか？

フォローアップの質問：unordered_map標準のハッシュ関数を使用すると、私のアプリケーションでは問題がないと言います。衝突が発生しないことを確認したい場合、および要素の最大数に制限できる場合size_tは、引数自体を返す独自のハッシュ関数を提供できます。何かのようなもの：

template<class T>
struct Hash
{
  size_t operator()(T t) {
    return (size_t)t;
  }
}

衝突がないことを確認しますか？

4

1 に答える 1

5

衝突はパフォーマンスにのみ影響し、コンテナの内容には影響しません。unordered_mapハッシュ関数と等式関数を取ります。2つの要素は安全に同じハッシュを持つことができ、それらが等しくない場合、それらは等しくないものとして扱われます。それらは常に同じハッシュバケットにあります。大きなバケットは、そのバケットを調べる操作のパフォーマンスを低下させます。

于 2012-05-25T09:20:22.523 に答える