The Google SparseHash project contains several C++ template hash-map implementations with different performance characteristics, including an implementation that optimizes for space and one that optimizes for speed.