当您在地图上操作时，Elixir 中是否保留键和值的顺序？

Question

假设我在 Elixir 中有一张地图：

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

如果我调用

Map.values(m)

，我是否保证返回值将始终按该顺序为

[1, 2, 3]

，而不是说，

[3, 1, 2]

？

这是我从文档中不清楚的一件事。经过一些初步测试，我认为是的。

Answer 1

Elixir 和 Erlang 中的 Map 实现有一些令人困惑的属性。对于较小的条目值，它是一个排序的键列表，因此似乎具有您在简单实验中看到的属性。

超过一定数量的条目（我认为是 32），实现会切换到哈希数组映射 Trie，并且您看到的所有属性都会消失。在一般情况下，您不能依赖于映射的键或值的顺序。参见

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

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

来自Elixir网站：

与关键字列表相比，我们已经可以看到两个区别：

• 地图允许任何值作为键。
• 地图的键不遵循任何顺序。

虽然 Elixir 网站明确指出 地图不遵循任何顺序，但它们在创建后确实遵循特定的顺序（但不保留其创建顺序）。看起来地图是根据它们的键按字母顺序组织的（但除了 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]

既然您询问是否保留原始订单，答案是否定的。

---

更好的选择：关键字列表

更好的选择是使用关键字列表（这是下面两个元素元组的链接列表）。因此，它们的创建顺序得以保持：

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

让我们检查一下Erlang的代码。

Elixir 使用 Erlang 的映射作为基础实现，它定义了一个 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

当您创建地图时，它将使用以下功能。

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

请注意，当地图大小小于

MAP_SMALL_MAP_LIMIT

时，它将调用

erts_validate_and_sort_flatmap

，它使用冒泡排序对地图进行排序。

否则，它将使用hashmap。

Answer 4

自 2023 年 5 月 OTP 26 起，具有原子键的映射将具有未定义的顺序。

在OTP 26中，作为某些地图操作的优化，例如 地图：from_list / 1，带有原子键的地图现在以不同的方式排序 命令。新的顺序是未定义的，并且可能会在不同的情况之间发生变化 Erlang VM 的调用

fly.io 有一篇博客文章，其中一些可能对排序地图有用。