On 2008-02-17 09:03, Juha Nieminen wrote:
Jerry Coffin wrote:
>I don't know of an existing implementation, but the idea is pretty
simple. You create the hash map as a table of balanced trees (e.g. AVL
or R-B trees). In the worst case, if all your hashes collide, you're
working with a single balanced tree, which is exactly what you have with
std::set, std::map, std::multiset and std::multimap, so you get
precisely the same characteristics as they provide.
How is this different from simply using one single balanced tree?
Since you are having the overhead of a balanced tree anyways, adding
some properties of hashmaps to the mix probably won't cause a
significant increase in any performance.
If you have luck with your hash-algorithm and the values inserted you
will only have one element per tree/bucket giving you O(1) insertion,
removal, and retrieval. In a normal hash-map (where the buckets are
linked lists) you have O(M) for these operations, where M is the number
of elements in the buckets (again, if you are lucky M==1) but in the
worst case you have O(N) when all elements are in the same bucket. If
the buckets are trees you get O(log N).
--
Erik Wikström