13

「unordered_map」という名前に非常に混乱しています。名前は、キーがまったく順序付けられていないことを示唆しています。しかし、私はいつもハッシュ値で並べられていると思っていました。それとも間違っていますか (名前が順序付けられていないことを意味するため)?

または別の言い方をすると、これですか

typedef map<K, V, HashComp<K> > HashMap;

と

template<typename T>
struct HashComp {
    bool operator<(const T& v1, const T& v2) const {
        return hash<T>()(v1) < hash<T>()(v2);
    }
};

と同じ

typedef unordered_map<K, V> HashMap;

? （OK、正確ではありません。キー k1、k2 があり、k1 < k2 でも k2 < k1 でもない可能性があるため、STL はここで文句を言います。equal multimap-check を使用して上書きする必要があります。）

または、別の方法で: それらを反復するとき、キーリストがハッシュ値で順序付けられていると想定できますか?

4

5 に答える 5

23

編集した質問への回答として、これら 2 つのスニペットはまったく同等ではありません。std::mapノードをツリー構造にunordered_map格納し、ハッシュテーブル*に格納します。

キーは「ハッシュ値」の順序で保存されるわけではありません。代わりに、各バケットがハッシュ値の範囲に対応する「バケット」に格納されます。基本的に、実装は次のようになります。

function add_value(object key, object value) {
   int hash = key.getHash();

   int bucket_index = hash % NUM_BUCKETS;
   if (buckets[bucket_index] == null) {
       buckets[bucket_index] = new linked_list();
   }
   buckets[bucket_index].add(new key_value(key, value));
}

function get_value(object key) {
   int hash = key.getHash();

   int bucket_index = hash % NUM_BUCKETS;
   if (buckets[bucket_index] == null) {
       return null;
   }

   foreach(key_value kv in buckets[bucket_index]) {
       if (kv.key == key) {
           return kv.value;
       }
   }
}

明らかに、これは非常に単純化されたものであり、実際の実装ははるかに高度です (たとえば、buckets配列のサイズ変更のサポート、バケットのリンク リストの代わりにツリー構造の使用など)。特定の順序で値を取得しないでください。詳細については、ウィキペディアを参照してください。


* 技術的には、 と の内部実装std::mapは実装定義ですが、標準では、これらの内部実装を意味unordered_mapする操作に特定の Big-O の複雑さが必要です。

于 2010-07-05T00:12:22.603 に答える
6

「順序付けされていない」とは、実装のどこかに線形シーケンスがないことを意味するものではありません。これは、「これらの要素の順序について何も想定できない」ことを意味します。

たとえば、ハッシュ マップからエントリが入力された順序で出力されると想定する人がよくいます。しかし、エントリは順不同であるため、そうではありません。

「ハッシュ値による順序付け」について: ハッシュ値は通常、整数の全範囲から取得されますが、ハッシュ マップには 2**32 スロットがありません。ハッシュ値の範囲は、スロットの数を法として取ることにより、スロットの数に縮小されます。さらに、ハッシュ マップにエントリを追加すると、新しい値に対応するためにサイズが変わる場合があります。これにより、以前のすべてのエントリが再配置され、順序が変更される可能性があります。

順序付けられていないデータ構造では、エントリの順序について何も想定できません。

于 2010-07-05T00:04:36.343 に答える
2

unordered_map という名前が示すように、C++0x 標準では順序が指定されていません。unordered_map の見かけの順序は、実際の実装にとって便利なものに依存します。

于 2010-07-05T00:06:41.303 に答える
1

類推が必要な場合は、選択した RDBMS を見てください。

クエリを実行するときに ORDER BY 句を指定しない場合、結果は「順不同」で返されます。つまり、データベースが感じる順序で返されます。順序は指定されておらず、システムは、最高のパフォーマンスを得るために好きなように自由に「順序付け」できます。

于 2010-07-04T23:58:31.770 に答える
1

そうです、unordered_map実際にはハッシュが順序付けられています。現在のほとんどの実装 (TR1 より前) では、 と呼ばれることに注意してくださいhash_map。

IBM C/C++ コンパイラのドキュメントでは、最適なハッシュ関数がある場合、任意の要素のルックアップ、挿入、および削除中に実行される操作の数は、シーケンス内の要素の数に依存しないと述べているため、これは、順序はそれほど順不同ではありません...

では、ハッシュ順であるとはどういう意味でしょうか? ハッシュは予測できないはずなので、定義上、マップ内の要素の順序について仮定することはできません。これが TR1 で名前が変更された理由です。古い名前は順序を示唆しています。これで、注文が実際に使用されていることがわかりましたが、予測できないため無視できます。

于 2010-07-04T23:59:15.170 に答える