Even if you want ordered by default a red-black tree is a bad way to get it. JavaScript has ordered maps, but engines like V8 use things like this: https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tabl... instead.

It's not a question of ordered vs. unordered, it's a question of red-black trees vs. a hashed array of some sort.