https://github.com/sparsehash/sparsehash was for a decade+ hands down the most memory efficient map implementation, originally written by Craig Silverstein of Google. I am not sure how the more recent SIMD stuff impacts it.
sparsehash is still more memory efficient, but it is quite slow in comparison. Also, in practice it doesn't reach the ultra-low space overheads claimed by the documentation. It allocates memory blocks of many different sizes, so the dominant space overhead becomes internal fragmentation in the allocator. For sparsehash using JEMalloc's default allocation classes (spaced about a factor of 1.2 apart) the memory used relative to useful data varies from about 1.3 for small values to 1.1 for large values.
