[webkit-dev] New hash template structure API design proposal

[Maciej Stachowiak]

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