UNORDERED_MAPは本当に順序付けられていませんか？

StackOverflow https://stackoverflow.com/questions/3176621

  •  02-10-2019
  •  | 
  •  

質問

私は「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はここで文句を言います。使用する必要があります。 multimap そして、等チェックを上書きします。）

繰り返しますが、それらを繰り返すと、キーリストがハッシュ値によって順序付けられると仮定できますか？

役に立ちましたか？

解決

編集された質問に答えて、これらの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 実装が定義されていますが、標準では、操作には特定のBIGOの複雑さが必要です 示す これらの内部実装

他のヒント

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

たとえば、多くの場合、エントリはハッシュマップから出てくるのと同じ順序で出てくると想定しています。

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

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

名前が順序付けられていないという名前が示唆しているように、C ++ 0x標準では順序付けは指定されていません。 UNORDERED_MAPの明らかな注文は、実際の実装に便利なものに依存します。

アナロジーが必要な場合は、選択したRDBMSをご覧ください。

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

あなたが正しいです、 unordered_map 実際には順序付けられています。現在のほとんどの実装（Pre TR1）がそれを呼ぶことに注意してください hash_map.

IBM C/C ++コンパイラ ドキュメンテーション それを紹介します 最適なハッシュ関数がある場合、任意の要素の検索、挿入、および除去中に実行される操作の数は、シーケンス内の要素の数に依存しません, 、したがって、これは順序がそれほど順序付けられていないことを意味します...

さて、それが何を意味するのか ハッシュ注文？ハッシュは予測不可能である必要があるため、定義上、マップ内の要素の順序について仮定することはできません。これがTR1で名前が変更された理由です。古い名前が順序を提案しました。これで、注文が実際に使用されていることがわかりましたが、予測不可能であるため、それを無視できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top