> 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';
Re:Hardening Perl's Hash Function
by ggchappell on Monday November 18, 2013 @10:09PM
(#6759012)
Wow, I had no idea. That's a nice feature.
I 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.
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.