classement des éléments en hachage de l'ensemble non ordonné

Question

Je suis confus au sujet de la table de hachage dans des conteneurs non ordonnés ... ou au moins dans des ensembles.

Alors, je pensais que cela fonctionnerait comme ceci:

Je hacher mon objet. Je calcule le modulo des longueurs d'objet et de vecteur (hash% vectorlength) et l'utilise comme index pour le pointeur vers mon objet dans la table de hachage .. qui est un vecteur autant que je sache ...

ainsi pour une fonction de hachage naïve qui retourne pour une enveloppe int juste la valeur de membre int il ressemblerait à ceci:

hash table: 

vector index:   [0, 1, 2, 3, 4] 
         | | | | | 
object with value...: 0 1 2 3 4 

j'ai écrit un programme pour vérifier que:

#include <iostream> 
#include <unordered_set> 

struct Obj 
{ 

public: 

    Obj(int i) 
    { 
     mem = i; 
    } 

    friend bool operator==(const Obj& o1, const Obj& o2) 
    { 
     return (o1.mem == o2.mem); 
    } 

    friend std::ostream& operator<<(std::ostream& o, const Obj& obj) 
    { 
     o << obj.mem; 
     return o; 
    } 

    int mem; 

}; 

namespace std 
{ 
    template<> 
    struct hash<Obj> 
    { 
     size_t operator()(const Obj& r) const 
     { 
      size_t hash = r.mem; 
      return hash; 
     } 
    }; 
} 


int main() 
{ 
    std::unordered_set<Obj> map; 
    for (int i = 0; i < 5; ++i) 
    { 
     map.insert(Obj(i)); 
    } 

    for(auto it = map.begin(); it != map.end(); ++it) 
    { 
     std::cout << (*it) << std::endl; 
    } 
} 

J'attendais la sortie

0 
1 
2 
3 
4 

mais je suis:

4 
3 
2 
1 
0 

Pourquoi?

Answer 1

S'il est vrai que les implémentations de la bibliothèque standard peuvent faire ce qu'elles veulent, il est également intéressant de voir où vos hypothèses - et celles exprimées dans plusieurs commentaires - correspondent à une implémentation réelle.

Je pourrais reproduire votre résultat non "0 1 2 3 4" avec GCC, mais seulement en ajoutant un map.reserve(6) ou plus (bizarrement, 5 produit "4 0 1 2 3").

Les détails ci-dessous simplement expliquer le comportement de la version GCC je regardais ....

Creuser pour une explication, je suis arrivé-sanity si les seaux logiques contenaient le hachage Fonction- contenu implicite:

for (size_t i = 0; i < map.bucket_count(); ++i) 
{ 
    std::cout << '[' << i << ']'; 
    for (auto it = map.begin(i); it != map.end(i); ++it) 
     std::cout << ' ' << *it; 
    std::cout << '\n'; 
} 

Et, en effet ils l'ont fait:

[0] 0 
[1] 1 
[2] 2 
[3] 3 
[4] 4 
[5] 
[6] 

Ainsi, le commentaire suggérant que "la bibliothèque standard est libre d'appliquer n'importe quelle fonction inversible à votre fonction de hachage, et aucune garantie sur la commande n'est donné" - tant que vrai - n'est pas ce qui se passe ici.

Creuser dans les en-têtes bibliothèque standard, je trouve la cause dans la documentation de bits/hashtable.h:

* Here's _Hashtable data structure, each _Hashtable has: 
* - _Bucket[]  _M_buckets 
* - _Hash_node_base _M_before_begin 
* - size_type  _M_bucket_count 
* - size_type  _M_element_count 
* 
* with _Bucket being _Hash_node* and _Hash_node constaining: 
* - _Hash_node* _M_next 
* - Tp   _M_value 
* - size_t  _M_code if cache_hash_code is true 
* 
* In terms of Standard containers the hastable is like the aggregation of: 
* - std::forward_list<_Node> containing the elements 
* - std::vector<std::forward_list<_Node>::iterator> representing the buckets 
* 
* The non-empty buckets contain the node before the first bucket node. This 
* design allow to implement something like a std::forward_list::insert_after 
* on container insertion and std::forward_list::erase_after on container 
* erase calls. _M_before_begin is equivalent to 
* std::foward_list::before_begin. Empty buckets are containing nullptr. 
* Note that one of the non-empty bucket contains &_M_before_begin which is 
* not a derefenrenceable node so the node pointers in buckets shall never be 
* derefenrenced, only its next node can be. 
* 
* Walk through a bucket nodes require a check on the hash code to see if the 
* node is still in the bucket. Such a design impose a quite efficient hash 
* functor and is one of the reasons it is highly advise to set 
* __cache_hash_code to true. 
* 
* The container iterators are simply built from nodes. This way incrementing 
* the iterator is perfectly efficient independent of how many empty buckets 
* there are in the container. 
* 
* On insert we compute element hash code and thanks to it find the bucket 
* index. If the element must be inserted on an empty bucket we add it at the 
* beginning of the singly linked list and make the bucket point to 
* _M_before_begin. The bucket that used to point to _M_before_begin, if any, 
* is updated to point to its new before begin node. 

Ainsi, la table de hachage qui sous-tend unordered_set est organisée avec valeurs dans une liste simplement chaînée, et seaux un vecteur d'itérateurs dans cette liste, plutôt que le communément prévu vector<forward_list<>>.

Lorsque vous insérez des éléments, ils vont dans la liste avant à l'avant, et il est cette liste que vous itérer en allant begin()-end(), sans aucune intervention de l'vector de itérateurs dont les correspond la commande aux valeurs de hachage.

code here illustre comment itération renvoie les valeurs dans l'ordre inverse de l'insertion, indépendamment de hachages/collisions - aussi longtemps que suffisamment d'espace est reserve() d à l'avance pour éviter rehashing.

Answer 2

Vous pensez que le conteneur unordered passera une commande. Il n'a aucune commande spécifiée ou garantie. Comme vous l'avez découvert, votre implémentation a profité de sa liberté et implémenté autre chose que la conception de table de hachage naïve que vous avez décrite. Une autre implémentation pourrait faire autre chose. Vous ne pouvez pas compter dessus du tout.