Hashes, on the other hand, are intrinsically not ordered internally. In fact, this feature is what allows for (relatively) inexpensive insertion and deletion. (Two items with keys very close to each other are likely to end up in different areas of the hash table.)
That's not correct. Hash keys
are ordered, otherwise you wouldn't be able to quickly search for them (and hence, no quick deletion either). However, the order internally isn't the same order people want (this thread seems to consider "ordered hashes" as "keys are sorted" - it's not uncommon for people to mean "keys returned in insertion order" when they talk about "ordered hashes"). I've always understood that
keys (and its friends) return the keys in the way they are laid out internally - so certainly "ordered", but only after applying a hash function.