Does hash_map automatically sort [C++]?

Question

In the below code, hash_map is automatically sorting or maybe inserting elements in a sorted order. Any ideas why it does this?? Suggestions Please?? This is NOT a homework problem, trying to solve an interview question posted on 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

Hash map will not automatically sort your data. In fact the order is unspecified, depending on your hash function and input order. It is just that in your case the numbers turns out are sorted.

You may want to read about hash table for how this container stores the data.

A clear counter example can be created by replacing that 100 with 999999999. The result is

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

---

(The actual reason is the hash_map's bucket_count is 193 and the hash function of int is an identity function, so any numbers below 193 will appear sorted.)