Google Sparsehash Package

The Google sparsehash package consists of two hashtable implementations: sparse, which is designed to be very space efficient, and dense, which is designed to be very time efficient. For each one, the package provides both a hash-map and a hash-set, to mirror the classes in the common STL implementation.

Documentation on how to use these classes:

• sparse_hash_map
• sparse_hash_set
• dense_hash_map
• dense_hash_set

In addition to the hash-map (and hash-set) classes, there's also a lower-level class that implements a "sparse" array. This class can be useful in its own right; consider using it when you'd normally use a sparse_hash_map, but your keys are all small-ish integers.

• sparsetable

There is also a doc explaining the implementation details of these classes, for those who are curious. And finally, you can see some performance comparisons, both between the various classes here, but also between these implementations and other standard hashtable implementations.