google-sparsehash is an extremely memory-efficient hash_map implementation. 2 bits/entry overhead! The SparseHash library contains several hash-map implementations, including implementations that optimize for space or speed.
These hashtable implementations are similar in API to SGI’s hash_map class, but with different performance characteristics. It’s easy to replace hash_map by sparse_hash_map or dense_hash_map in C++ code.
It 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.