Is the order of keys and values ​​stored in Elixir when working on the map?

Question

Suppose I have a map in Elixir:

m = %{"a"=>1, "b"=>2, "c" => 3} 

If I call Map.values(m) , I guarantee that the return value will always be [1, 2, 3] in that order and not say [3, 1, 2] ?

This is one thing that I don't understand about in the docs. After some preliminary testing, I think so.

Answer 1

The implementation of maps in Elixir and Erlang has some confusing properties. For small record values, this is a sorted list of keys and appears to have the properties that you see in simple experiments.

Over a certain number of entries (32, I think), the implementation switches to a Hash Array Mapped Trie, and all the properties that you see disappear. You cannot depend on the order of the keys or values ​​of the card in the general case. Cm.

https://en.wikipedia.org/wiki/Hash_array_mapped_trie

to explain the basic structure of the Map.

  iex(7)> 1..33 |> Enum.reduce(%{}, fn(x, acc) -> Map.put(acc,x,x) end ) %{11 => 11, 26 => 26, 15 => 15, 20 => 20, 17 => 17, 25 => 25, 13 => 13, 8 => 8, 7 => 7, 1 => 1, 32 => 32, 3 => 3, 6 => 6, 2 => 2, 33 => 33, 10 => 10, 9 => 9, 19 => 19, 14 => 14, 5 => 5, 18 => 18, 31 => 31, 22 => 22, 29 => 29, 21 => 21, 27 => 27, 24 => 24, 30 => 30, 23 => 23, 28 => 28, 16 => 16, 4 => 4, 12 => 12} iex(8)> Map.keys(v(7)) [11, 26, 15, 20, 17, 25, 13, 8, 7, 1, 32, 3, 6, 2, 33, 10, 9, 19, 14, 5, 18, 31, 22, 29, 21, 27, 24, 30, 23, 28, 16, 4, 12] iex(9)> Map.values(v(7)) [11, 26, 15, 20, 17, 25, 13, 8, 7, 1, 32, 3, 6, 2, 33, 10, 9, 19, 14, 5, 18, 31, 22, 29, 21, 27, 24, 30, 23, 28, 16, 4, 12] 

Answer 2

From the Elixir website :

Compared to keyword lists, we already see two differences:

• Maps allow you to use any value as a key.
• The map keys do not correspond to any order.

While the Elixir website clearly states that Maps do not correspond to any order , they follow a specific order after they are created (but do not preserve their order of creation >). It seems that the Maps are organized in alphabetical order according to their keys (but I have nothing to support this, with the exception of a few experiments in IEx):

 map = %{c: 3, a: 1, b: 2} map # => %{a: 1, b: 2, c: 3} Map.keys(map) # => [:a, :b, :c] Map.values(map) # => [1, 2, 3] 

Since you asked to keep the original order, the answer is NO.

---

Best Option: Keyword Lists

A better alternative would be to use keyword lists (which are a linked list of two element tuples at the bottom). Because of this, the order in which they are created is preserved:

 kw = [c: 3, a: 1, b: 2] kw # => [c: 3, a: 1, b: 2] Keyword.keys(kw) # => [:c, :a, :b] Keyword.values(kw) # => [3, 1, 2] 

Answer 3

Check out the Erlang code.

The elixir uses the Erlang map as the base implementation; it defines the macro MAP_SMALL_MAP_LIMIT.

 erts/emulator/beam/erl_map.h-#ifdef DEBUG erts/emulator/beam/erl_map.h:#define MAP_SMALL_MAP_LIMIT (3) erts/emulator/beam/erl_map.h-#else erts/emulator/beam/erl_map.h:#define MAP_SMALL_MAP_LIMIT (32) erts/emulator/beam/erl_map.h-#endif 

When you create a map, it will use the following function.

 Eterm erts_map_from_ks_and_vs(ErtsHeapFactory *factory, Eterm *ks0, Eterm *vs0, Uint n) { if (n < MAP_SMALL_MAP_LIMIT) { Eterm *ks, *vs, *hp; flatmap_t *mp; Eterm keys; hp = erts_produce_heap(factory, 3 + 1 + (2 * n), 0); keys = make_tuple(hp); *hp++ = make_arityval(n); ks = hp; hp += n; mp = (flatmap_t*)hp; hp += MAP_HEADER_FLATMAP_SZ; vs = hp; mp->thing_word = MAP_HEADER_FLATMAP; mp->size = n; mp->keys = keys; sys_memcpy(ks, ks0, n * sizeof(Eterm)); sys_memcpy(vs, vs0, n * sizeof(Eterm)); erts_validate_and_sort_flatmap(mp); return make_flatmap(mp); } else { return erts_hashmap_from_ks_and_vs(factory, ks0, vs0, n); } return THE_NON_VALUE; } 

Note that when the map size is smaller than MAP_SMALL_MAP_LIMIT , it calls erts_validate_and_sort_flatmap , which use bubble sorting to sort your map.

Otherwise, it will use hashmap.