[webkit-dev] New hash template structure API design proposal
David D. Kilzer
ddkilzer at kilzer.net
Sun Jun 26 05:22:21 PDT 2005
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."
It's still in beta, though, at version 0.2.
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.
More information about the webkit-dev