Under what circumstances will std::unordered_map behave very slow?

I've done some random tests but I couldn't come to a conclusion. If inserting 1000000 integers in to a map and an unordered_map, the time used by map is 3 times larger. If inserting 1000000 strings then the time used by map is 2 times larger. Under what circumstances will std::unordered_map behave very slow? Thanks in advance. UPD:: gcc version 4.8.4 (Ubuntu 4.8.4-2ubuntu1~14.04.3). All tests got without -O2. Code: a.cpp: std::map<int, int> M; b.cpp: std::unordered_map<int, int> M; g(i, 1, 1000000) { M[i] = rand() % i; } Results of my tests: yyhs@yyhs-Pro:~/Documents$ g++ a.cpp -o a -g --std=c++11 && time ./a real 0m0.659s user 0m0.653s sys 0m0.004s yyhs@yyhs-Pro:~/Documents$ g++ b.cpp -o b -g --std=c++11 && time ./b real 0m0.260s user 0m0.251s sys 0m0.008s yyhs@yyhs-Pro:~/Documents$ g++ a.cpp -o a -g --std=c++11 -O2 && time ./a real 0m0.290s user 0m0.282s sys 0m0.008s yyhs@yyhs-Pro:~/Documents$ g++ b.cpp -o b -g --std=c++11 -O2 && time ./b real 0m0.081s user 0m0.081s sys 0m0.000s My question here is what cases might cause std::unordered_map become slow.