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