I was re-watching the LL4 Lua talk on Lua's table implementation and chatting with Mikael Sundstrom about using lists as strings and both reminded me about dynamic data structures - data structures that can switch on-the-fly between internal representations to fit they are being used.

For example, let's say you're using a key/value table. If all the keys are ordered numbers, it might internally use a list. If not, and it's small, it might use a perfect hash table. If it's medium size, it might use a normal hash table. If it gets large, it would switch to a skip list (or a b-tree) to avoid rehashing overhead.

Such an object could unify all the standard collection objects (Lists, ByteArrays, Strings, Dictionaries, Objects).

Update: Jean Claude Wippler pointed me to this link.