Here are some performance numbers from an example desktop machine, taken from a version of time_hash_map that was instrumented to also report memory allocation information (this modification is not included by default because it required a big hack to do, including modifying the STL code to not try to do its own freelist management).
Note there are lots of caveats on these numbers: they may differ from machine to machine and compiler to compiler, and they only test a very particular usage pattern that may not match how you use hashtables -- for instance, they test hashtables with very small keys. However, they're still useful for a baseline comparison of the various hashtable implementations.
These figures are from a 2.80GHz Pentium 4 with 2G of memory. The 'standard' hash_map and map implementations are the SGI STL code included with gcc2. Compiled with gcc2.95.3 -g -O2
====== Average over 10000000 iterations Wed Dec 8 14:56:38 PST 2004 SPARSE_HASH_MAP: map_grow 665 ns map_predict/grow 303 ns map_replace 177 ns map_fetch 117 ns map_remove 192 ns memory used in map_grow 84.3956 Mbytes DENSE_HASH_MAP: map_grow 84 ns map_predict/grow 22 ns map_replace 18 ns map_fetch 13 ns map_remove 23 ns memory used in map_grow 256.0000 Mbytes STANDARD HASH_MAP: map_grow 162 ns map_predict/grow 107 ns map_replace 44 ns map_fetch 22 ns map_remove 124 ns memory used in map_grow 204.1643 Mbytes STANDARD MAP: map_grow 297 ns map_predict/grow 282 ns map_replace 113 ns map_fetch 113 ns map_remove 238 ns memory used in map_grow 236.8081 Mbytes
For good performance, the Google hash routines depend on a good hash function: one that distributes data evenly. Many hashtable implementations come with sub-optimal hash functions that can degrade performance. For instance, the hash function given in Knuth's _Art of Computer Programming_, and the default string hash function in SGI's STL implementation, both distribute certain data sets unevenly, leading to poor performance.
As an example, in one test of the default SGI STL string hash function against the Hsieh hash function (see below), for a particular set of string keys, the Hsieh function resulted in hashtable lookups that were 20 times as fast as the STLPort hash function. The string keys were chosen to be "hard" to hash well, so these results may not be typical, but they are suggestive.
There has been much research over the years into good hash functions. Here are some hash functions of note.