Expectedly, per Clojure documentation, "Vectors support access to items by index in log32N hops". This means that a Clojure vector is essentially a tree-based map; a "true" array (as in C or Java) would have O(1) time for access by index.

I suspect that Elixir's maps are not different in this regard, as are Erlang's arrays, or maps in Haskell or OCaml. This is the canonical way to make an immutable map (see picture here: http://programmers.stackexchange.com/questions/195718/functi...).