Est-ce que hash_map trie automatiquement [C++]?

Question

Dans le code ci-dessous, hash_map trie ou insère automatiquement les éléments dans un ordre trié. Des idées pourquoi ça fait ça ?? Suggestions S'il vous plait ?? Ce n'est pas un problème de devoirs, en essayant de résoudre une question d'entrevue publiée sur glassdoor dot com.

#include <iostream> 
#include <vector> 
#include <ext/hash_map> 
#include <map> 
#include <string.h> 
#include <sstream> 

using namespace __gnu_cxx; 
using namespace std; 

struct eqstr 
{ 
    bool operator()(int i, int j) const 
    { 
    return i==j; 
    } 
}; 
typedef hash_map<int, int, hash<int>, eqstr> myHash; 
int main() 
{ 
    myHash array; 
    int inputArr[20] = {1,43,4,5,6,17,12,163,15,16,7,18,19,20,122,124,125,126,128,100}; 

    for(int i=0;i<20;i++){ 
     array[inputArr[i]] = inputArr[i]; //save value 
    } 
    myHash::iterator it = array.begin(); 
    int data; 
    for (; it != array.end(); ++it) { 
     data = it->first; 
     cout << ":: " << data; 
    } 
} 

//!Output ::: 1:: 4:: 5:: 6:: 7:: 12:: 15:: 16:: 17:: 18:: 19:: 20:: 43:: 100:: 122:: 124:: 125:: 126:: 128:: 163 

Answer 1

carte Hash sera pas automatiquement tri vos données. En fait, la commande n'est pas spécifiée, en fonction de votre fonction de hachage et de l'ordre de saisie. C'est juste que dans votre cas, les chiffres sont triés.

Vous voudrez peut-être lire environ hash table pour savoir comment ce conteneur stocke les données.

Un exemple de compteur d'effacement peuvent être créées par le remplacement, que 100 avec 999999999. Le résultat est

:: 1:: 4:: 5:: 6:: 7:: 12:: 15:: 16:: 17:: 18:: 19:: 20:: 999999999:: 43:: 122:: 124:: 125:: 126:: 128:: 163 

---

(La raison réelle est bucket_count de l'hash_map est 193 et ​​la fonction de hachage de int est une identité fonction, de sorte que les numéros ci-dessous 193 apparaîtront triés)

Answer 2

Une carte de hachage peut apparaître être triés en fonction de quelques facteurs.

• La fonction de hachage renvoie des valeurs qui sont dans le même ordre que l'entrée, pour la plage d'entrée que vous fournissez.
• Il n'y a pas de collisions de hachage.

Il n'y a aucune garantie que les résultats seront triés, ce n'est qu'une coïncidence s'ils sortent de cette façon.

Answer 3

Pensez à la manière dont fonctionne la fonction de hachage. Un hachage est toujours une fonction f: entrée-> sortie qui mappe l'ensemble d'entrée I dans un ensemble de sortie O (généralement plus petit) afin que l'ensemble d'entrée soit réparti approximativement uniformément sur l'ensemble de sortie.

Il n'y a aucune exigence que l'ordre doit être préservé; en fait, il est inhabituel qu'il soit conservé, car (puisque l'ensemble de sortie est plus petit) il y aura des valeurs * i, j * qui ont le même hachage. C'est ce qu'on appelle une collision .

D'un autre côté, il n'y a aucune raison que cela ne soit pas le cas. En fait, il peut être prouvé qu'il existera toujours au moins une séquence que va conserver préserver la commande.

Mais il y a une autre possibilité: si TOUTES les valeurs entrent en collision, elles sont stockées dans un autre type de structure de données, comme une liste. Il se peut que ceux-ci collent tous, et l'autre structure impose l'ordre. Trois possibilités: hash_map arrive à trier cette séquence particulière, ou hash_map est réellement implanté en tant que tableau, ou les valeurs collidge et l'implémentation stocke les collisions d'une manière qui donne un ordre trié.