On Jun 26, 2005, at 5:22 AM, David D. Kilzer wrote:
Google recently released a SparseHash project to SourceForge that's implemented in C++ with a BSD license.
"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."
Cool, I'm looking at it. Thanks for the pointer! It looks like their "dense_hash_map" uses the same design I was planning, storing the values inline and requiring distinguished values for empty and deleted buckets. Most C++ hashtable templates (including the gcc implementation of hash_map) use separately allocated nodes for the data. This makes it easier to put more of the implementation in non-template code without losing a lot of speed, but it is much slower, since you must allocate for every insertion. sparse_hash_map is very interesting and could be useful in places where saving memory is more important than access speed. I will add, however, that the included hash functions are pretty weak. Regards, Maciej