time = 1253085626.187
time = 1253085626.661
time = 1253085629.317

This means finding 32000000 items took about 4 seconds. I would suggest you check your code again. Here is the source code, you may need to change the includes depending on your version of c++:
#include
#include

typedef __gnu_cxx::hash_map map_type;

int main(int argc, char** argv) {

typedef std::pair Int_Pair;

char buf [80];

map_type map;

struct timeb tp;
ftime(&tp);
printf(“time = %ld.%d\n”,tp.time,tp.millitm);

int i = 0;

for (i = 0; i<1000000; i++) {

map.insert(Int_Pair(i, i));

}

ftime(&tp);
printf("time = %ld.%d\n",tp.time,tp.millitm);

if (i != 1000000) {
printf ("Error!\n");
exit(1);
}

map_type::iterator j;

for (i = 0; i<32000000; i++) {
j = map.find(i%1000000);
}

ftime(&tp);
printf("time = %ld.%d\n",tp.time,tp.millitm);

if (i != 32000000) {
printf ("Error!\n");
exit(1);
}

return (EXIT_SUCCESS);
}

If you were using the default then that could be your problem. It mostly depends on your data…

http://www.ddj.com/architect/184405046?pgno=1

hash_map map;

// insertion
loop over millions of (k, v) pairs:
map.insert(k, v); // this will compute the hash value for k
// and *also* make a copy of v to put into
// the map.

// lookups
loop over millions of key values k:
ValType v = map[k]; // This copies the value v over
// from the container to the local variable v

So if the object which is being put into the table is largish (say c++ strings or any aggregate object) then it would be significantly faster to store pointers to the objects in the hashtable rather than the objects themselves. Alternatively, you could change the lookup to something like:

const ValType& v = map[k];

which will also get rid of the copies. Of course if you are storing integers or things of that scale only then this comment doesn’t really apply.

*@priyendra*: I’m not sure I follow. In our code we just have one or two instances of the hash table object. So why would the copy constructor be a problem? We’re not creating millions of instances of new objects. Am I missing something?

*@shashikant*: I’m not in a position to argue the statement “STL can’t be slower than Java” either way but I’ll take your word for it :-) I’m just as baffled by the results — maybe I’ll post the code shortly so that you guys can check it out yourself.

The only case when I think hash look-ups may take such times is load factor to be closer to 1.0, where look-up can degenerate into O(n).