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.
[...]