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

[David D. Kilzer]

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/

It's still in beta, though, at version 0.2.

Dave


On Jun 26, 2005, at 1:06 AM, Maciej Stachowiak wrote:

> I've been planning for a while to make really good, high- 
> performance generic HashSet and HashMap templates for WebCore, to  
> replace the mix of QDict, QMap and hand-coded hashtables we have now.
>
> Problems with the current situation are:
>
> * QMap is too slow (algorithmically inefficient by design)
> * The WebCore implementation of QDict is too slow, and non-portable
> * QDict/QPtrDict is not nearly flexible enough
> * Sprinkling the code with hand-coded hashtables sucks
> * Even the forthcoming Qt 4.0 QHash will not cut it - it does not  
> allow making multiple hashtables keyed by the same type but with  
> different hash and equality functions (important for things like  
> case insensitive string tables, or having pointer hashes with some  
> other concept of equality than identity), and it seems likely to be  
> inefficient for pointer types.
>
> [...]