4 ms·
> But if I was looking for guarantees for worst-case performance, I'd (pretty much) never use a HashMap. I wonder why none[1] of the major dynamic languages of
by ggchappell 13y ago
> But if I was looking for guarantees for worst-case performance, I'd (pretty much) never use a HashMap.
I wonder why none[1] of the major dynamic languages offer the option of running with the built-in associative-data structures implemented using a Red-Black Tree. Seems like an obvious thing to do.
There are interface issues, of course. In particular, for a new type to be usable as a key, it would need to provide an ordering rather than a hash function.
But if only built-in types are used as keys, then there might be no reason to change the interface at all. Just re-run the same program with a different option and you've traded some average-case performance for a guarantee on worst-case performance. And the Red-Black Tree is already written (somewhere out there ...). So why not?
[1] To my knowledge.
- _delirium 13y ago> I wonder why none[1] of the major dynamic languages offer the option of running with the built-in associative-data structures implemented using a Red-Black Tree. Seems like an obvious thing to do. It's not a command-line option, but Perl lets you "tie" a hash to a different backing implementation, and there are some tree-based ones: use Tree::RB; tie my %hash, 'Tree::RB';
- ggchappell 13y agoWow, I had no idea. That's a nice feature.
- andreasvc 13y agoI reckon because pointer-based trees are very slow compared to array-based data structures; these are constant factors due to memory accesses so they have nothing to do with the average and worst case performance you mention. For databases b-trees are appropriate, but for most uses of associative data structures hash tables are just very hard to beat.