Data is immutable in Erlang. How do you know the runtime does not optimize Maps with numeric keys into arrays?

Data is also immutable in Clojure but it still has vectors.

Yeah, but Clojure vectors are actually trees built to be persistent based on ideas from Bagwell's hash array mapped tries (what Clojure maps are), so they're not technically O(1).

Both maps and vectors in Clojure are trees, albeit very shallow trees (32-way branching). The difference lies in the interfaces and the lookup methods. (Maps hash keys and use bits to know which subtree to descend, while vectors use index bits.)

Another thing with numeric maps is how insert would work. Swapping elements is trivial, but inserting a new one would require rewriting every subsequent entry.