Java 7 changed its HashMap implementation to use TreeMap (red black search tree) instead of LinkedList for its buckets, if the key can be sorted. That puts the worst case lookup time from O(n) to O(log n) for sortable keys. Maybe that's worth considering for AAs?
I don't think that would pay off for most uses of builtin AAs. One day we'll probably get a fully customizable hash table in phobos that can do this kind of stuff.
