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."
http://sourceforge.net/projects/goog-sparsehash/
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
_______________________________________________
webkit-dev mailing list
[email protected]
http://www.opendarwin.org/mailman/listinfo/webkit-dev
