[webkit-dev] New hash template structure API design proposal
mjs at apple.com
Mon Jun 27 01:49:14 PDT 2005
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.
More information about the webkit-dev