CODEWITHSUNDEEP
elixir
Nona
Nona

Reputation: 5472

Is ordering of keys and values preserved in Elixir when you operate on a map?

Suppose I have a map in Elixir:

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

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

This is one thing I am not clear on from the docs. After some preliminary testing, I think it is.

Upvotes: 25

Views: 13264

Answers (5)

Jonathan Chan
Jonathan Chan

Reputation: 2399

The iteration order for maps is not just "undefined" in the sense that:

  1. there is some order at runtime which you don't know, but
  2. if you treat the Map as an Enumerable and iterate over it, you'll observe the entries of the Map as being in the same order every time

The second property is true for lists:

Enum.zip_with(1..32, 1..32, fn a, b -> {a, b} end)
# [{1, 1}, {2, 2}, {3, 3}, ...]

... but is not true for Maps with more than 32 entries:

range = 1..33
map = Enum.map(range, &{&1, true}) |> Enum.into(%{})
IO.inspect(Enum.map(map, fn {k, _v} -> k end))
IO.inspect(Enum.zip_with(range, map, fn _, {k, _v} -> k end))
# [4, 25, 8, 1, 23, 10, 7, 9, 11, 12, 28, 24, 13, 3, 18, 29, 26, 22, 19, 2, 33, 21, 32, 20, 17, 30, 14, 5, 6, 27, 16, 31, 15]
# [15, 31, 16, 27, 6, 5, 14, 30, 17, 20, 32, 21, 33, 2, 19, 22, 26, 29, 18, 3, 13, 24, 28, 12, 11, 9, 7, 10, 23, 1, 8, 25, 4]

It looks like Enum.zip_with enumerates over the entries of a Map in the opposite order from Enum.map.

Upvotes: 0

sbaildon
sbaildon

Reputation: 248

As of OTP 26, May 2023, maps with atom keys will have an undefined order.

In OTP 26, as an optimization for certain map operations, such as maps:from_list/1, maps with atom keys are now sorted in a different order. The new order is undefined and may change between different invocations of the Erlang VM

fly.io have a blog post that some might be useful for sorting maps.

Upvotes: 1

Sheharyar
Sheharyar

Reputation: 75840

From the Elixir website:

Compared to keyword lists, we can already see two differences:

  • Maps allow any value as a key.
  • Maps’ keys do not follow any ordering.

While the Elixir website clearly states that Maps do not follow any ordering, they do follow a specific order after they've created (but do not preserve their order of creation). It seems that the Maps are organized alphabetically according to their keys (but I have nothing to back this up except 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 about preserving the original order, The answer is NO.

Better Option: Keyword Lists

A better alternative would be to use Keyword lists (which are a linked-list of two element tuples underneath). Because of this, the order of their creation is maintained:

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]

Upvotes: 14

chris
chris

Reputation: 2863

Let's check the Erlang's code.

Elixir use Erlang's map as base implementation，it defines a MAP_SMALL_MAP_LIMIT macro.

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 function below.

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;
}

Notice that when the size of the map is less than MAP_SMALL_MAP_LIMIT, it will call erts_validate_and_sort_flatmap, which use bubble sort to sort your map.

Otherwise, it will use hashmap.

Upvotes: 4

Fred the Magic Wonder Dog
Fred the Magic Wonder Dog

Reputation: 9109

The implementation of Maps in Elixir and Erlang has some confusing properties. For small values of entries it is a sorted key list, and thus appears to have the properties you see in simple experiments.

Above a certain number of entries (32 I think), the implementation switches to Hash Array Mapped Trie and all the properties you see disappear. You can not depend on the order of either the keys or the values of a map in the general case. See

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

for an explaination of the underlying structure of 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]

Upvotes: 42

Related Questions