[ggchappell]

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

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

Wow, I had no idea. That's a nice feature.

[andreasvc]

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.