Est-ce vraiment le unordered_map UNORDERED?

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

  •  02-10-2019
  •  | 
  •  

Question

Je suis très confus par le nom « unordered_map ». Le nom suggère que les clés ne sont pas commandés du tout. Mais je pensais toujours qu'ils sont commandés par leur valeur de hachage. Ou est-ce mal (parce que le nom implique qu'ils ne sont pas ordonnés)?

Ou pour le dire différent: Est-ce 

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

avec 

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

la même chose que 

typedef unordered_map<K, V> HashMap;

? (OK, pas exactement, STL se plaindra ici parce qu'il peut y avoir des clés k1, k2 et ni k1 multimap et écraser l'égale vérification.)

Ou encore différemment: Quand je itérer à travers eux, je peux supposer que la liste des clés est ordonnée par leur valeur de hachage

Était-ce utile?

La solution

En réponse à votre question éditée, pas ces deux extraits ne sont pas équivalents du tout. nœuds stocke std::map dans une structure arborescente, stocke unordered_map-les dans un Hashtable *.

Les clés ne sont pas stockés dans l'ordre de leur « valeur de hachage », car ils ne sont pas stockés dans tout ordre du tout . Ils seront stockés dans « seaux » où chaque godet correspond à une plage de valeurs de hachage. En fait, la mise en œuvre va comme ceci: 

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;
       }
   }
}

Il est évident que c'est une simplification grave et la mise en œuvre réelle serait beaucoup plus avancé (par exemple, en soutenant le redimensionnement du tableau de buckets, en utilisant peut-être une structure arborescente au lieu de liste chaînée pour les seaux, etc.), mais cela devrait donner une idée de la façon dont vous ne pouvez pas récupérer les valeurs dans un ordre particulier. Voir wikipedia pour plus d'informations.

* Techniquement, la mise en œuvre interne de std::map et unordered_map sont définies la mise en œuvre, mais la norme exige certaine complexité Big-O pour les opérations que implique ces implémentations internes

Autres conseils

« Unordered » ne veut pas dire qu'il n'y a pas une part de séquence linéaire dans la mise en œuvre. Cela signifie que « vous ne pouvez pas assumer quoi que ce soit de l'ordre de ces éléments ».

Par exemple, les gens pensent souvent que les entrées sortiront d'une carte de hachage dans le même ordre dans lequel ils ont été mis en. Mais ils ne le font pas, parce que les entrées ne sont pas ordonnés.

Comme pour « commandés par leur valeur de hachage »: les valeurs de hachage sont généralement prises à partir de la gamme complète d'entiers, mais les cartes de hachage n'ont pas 2 ** 32 emplacements en eux. La gamme de la valeur de hachage sera réduit au nombre de créneaux horaires en prenant modulo le nombre de machines à sous. En outre, comme vous ajoutez des entrées à une carte de hachage, il pourrait changer la taille pour tenir compte des nouvelles valeurs. Cela peut causer toutes les entrées précédentes pour être placé re, changer leur ordre.

Dans une structure de données non triées, vous ne pouvez pas assumer quoi que ce soit de l'ordre des entrées.

Comme le unordered_map de nom l'indique, aucun ordre est spécifié par la norme C ++ 0x. commande apparente dépendra de ce qui est pratique pour la mise en œuvre effective d'un unordered_map.

Si vous voulez une analogie, regardez les SGBDR de votre choix.

Si vous ne spécifiez pas une clause ORDER BY lors de l'exécution d'une requête, les résultats sont renvoyés « non ordonnée » - qui est, dans l'ordre que la base de données se sent comme. L'ordre n'est pas spécifié, et le système est libre de les « ordre » mais il aime afin d'obtenir les meilleures performances.

Vous avez raison, unordered_map est effectivement hachage ordonné. Notez que la plupart des implémentations actuelles (pré TR1) appellent hash_map.

Le IBM C / C ++ compilateur

Non affilié à StackOverflow
scroll top