Sparsehash Package (formerly Google Sparsehash)

The 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:

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.

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.

Craig Silverstein
Last modified: Thu Jan 25 17:58:02 PST 2007