查看源码 映射

本高效使用映射指南首先简要介绍了记录和映射之间的选择，然后分三部分就如何使用映射替代记录、作为字典以及作为集合给出具体（但简短）的建议。其余部分将深入探讨，了解映射是如何实现的、映射语法，以及最后 maps 模块中的函数。

本章使用的术语

  • 最多包含 32 个元素的映射将非正式地称为小映射。
  • 包含超过 32 个元素的映射将非正式地称为大映射。

映射还是记录？

如果遵循本章中的建议，那么记录的性能与使用小映射代替记录的性能预计将相似。因此，记录和映射之间的选择应基于数据结构的期望属性，而不是性能。

与映射相比，记录的优点是：

  • 如果记录字段的名称拼写错误，将会出现编译错误。如果映射键拼写错误，编译器将不会发出警告，并且程序在运行时会以某种方式失败。
  • 记录使用的内存将比映射略少，并且在大多数情况下，性能预计会比映射略好。

与映射相比，记录的缺点是，如果向记录添加新字段，则必须重新编译使用该记录的所有代码。因此，建议仅在可以轻松地一次性重新编译的代码单元（例如，单个应用程序或单个模块）中使用记录。

使用映射替代记录

  • 使用映射语法，而不是 maps 模块中的函数。

  • 避免映射中包含超过 32 个元素。一旦映射中包含超过 32 个元素，它将需要更多内存，并且键不能再与其他映射实例共享。

  • 创建新映射时，始终创建包含将要使用的所有键的映射。为了最大程度地共享键（从而最大限度地减少内存使用），请创建一个使用映射语法构造映射的单个函数并始终使用它。

  • 始终使用 := 运算符（即，要求具有该键的元素已经存在）更新映射。:= 运算符效率更高，并且有助于捕获键的拼写错误。

  • 尽可能一次匹配多个映射元素。

  • 尽可能一次更新多个映射元素。

  • 避免默认值和 maps:get/3 函数。如果存在默认值，则不同映射实例之间的键共享将不太有效，并且不可能一次匹配具有默认值的多个元素。

  • 为了避免处理可能缺少某些键的映射，maps:merge/2 可以有效地添加多个默认值。例如

    DefaultMap = #{shoe_size => 42, editor => emacs},
MapWithDefaultsApplied = maps:merge(DefaultMap, OtherMap)

将映射用作字典

将映射用作字典意味着以下使用模式：

  • 键通常是编译时未知的变量。
  • 映射中可以有任意数量的元素。
  • 通常，一次查找或更新不超过一个元素。

考虑到这种使用模式，使用映射语法和 maps 模块之间的性能差异通常很小。因此，使用哪个主要取决于个人喜好。

映射通常是最有效的字典数据结构，但也有一些例外情况：

  • 如果需要频繁地将字典转换为排序列表，或从排序列表转换为字典，则使用 gb_trees 可能是更好的选择。
  • 如果所有键都是非负整数，则 array 模块可能是更好的选择。

将映射用作集合

从 OTP 24 开始，sets 模块提供了一个选项，可以将集合表示为映射。示例：

1> sets:new([{version,2}]).
#{}
2> sets:from_list([x,y,z], [{version,2}]).
#{x => [],y => [],z => []}

以映射为后盾的 sets 通常是最有效的集合表示形式，但也有一些可能的例外情况：

  • ordsets:intersection/2 比 sets:intersection/2 效率更高。如果频繁使用交集操作，并且避免对集合中的单个元素进行操作（例如 is_element/2），则 ordsets 可能比 sets 更好的选择。
  • 如果频繁使用交集操作，并且还必须高效地执行对集合中单个元素进行操作的操作（例如 is_element/2），则 gb_sets 可能比 sets 更好的选择。
  • 如果集合的元素是相对紧凑范围内的整数，则可以将集合表示为整数，其中每个位代表集合中的一个元素。并集运算由 bor 执行，交集运算由 band 执行。

映射是如何实现的

在内部，映射根据映射中元素的数量有两种不同的表示形式。当映射增长到超过 32 个元素，或者缩小到 32 个或更少的元素时，表示形式会发生变化。

  • 最多包含 32 个元素的映射具有紧凑的表示形式，使其适合作为记录的替代品。
  • 包含超过 32 个元素的映射表示为一棵树，无论有多少元素，都可以有效地搜索和更新。

小映射是如何实现的

小映射在运行时系统内部看起来像这样：

0123N
FLATMAPN键值 1...值 N

表：小映射的表示形式

  • FLATMAP - 小映射的标签（在运行时系统的源代码中称为扁平映射）。

  • N - 映射中元素的数量。

  • 键 - 包含映射键的元组：{Key1,...,KeyN}。键已排序。

  • 值 1 - 与键元组中第一个键对应的值。

  • 值 N - 与键元组中最后一个键对应的值。

例如，让我们看看映射 #{a => foo, z => bar} 是如何表示的：

01234
FLATMAP2{a,z}foobar

表：#{a => foo, z => bar}

让我们更新映射：M#{q => baz}。现在映射看起来像这样：

012345
FLATMAP3{a,q,z}foobazbar

表：#{a => foo, q => baz, z => bar}

最后，更改一个元素的值：M#{z := bird}。现在映射看起来像这样：

012345
FLATMAP3{a,q,z}foobazbird

表：#{a => foo, q => baz, z => bird}

当更新现有键的值时，键元组不会更新，从而允许键元组与具有相同键的其他映射实例共享。实际上，经过一定的处理，键元组可以在具有相同键的所有映射之间共享。为了实现这一点，请定义一个返回映射的函数。例如：

new() ->
    #{a => default, b => default, c => default}.

像这样定义后，键元组 {a,b,c} 将是一个全局字面量。为了确保在创建映射实例时共享键元组，请始终调用 new() 并修改返回的映射：

    (SOME_MODULE:new())#{a := 42}.

使用带有小映射的映射语法特别高效。只要键在编译时已知，映射就会一次性更新，使得更新映射的时间本质上是恒定的，而与更新的键的数量无关。匹配也是如此。（当键是变量时，一个或多个键可能相同，因此操作需要从左到右顺序执行。）

小映射的内存大小是所有键和值的大小加上 5 个字。有关内存大小的更多信息，请参见内存。

大映射是如何实现的

包含超过 32 个元素的映射被实现为 哈希数组映射 trie (HAMT)。无论映射中有多少元素，都可以有效地搜索和更新大映射。

与小映射相比，使用大映射的映射语法来匹配或更新多个元素所获得的性能提升较少。执行时间大致与匹配或更新的元素数量成正比。

大映射的存储开销高于小映射。对于大映射，除了键和值之外的额外字数大致与元素数量成正比。根据 内存 中的公式，对于包含 33 个元素的映射，开销至少为 53 个堆字（而对于小映射，无论元素数量多少，开销都为 5 个额外字）。

当更新大映射时，更新后的映射和原始映射将共享 HAMT 的公共部分，但是共享永远不会像小映射的键元组的最佳共享那样有效。

因此，如果使用映射代替记录，并且预计会创建许多映射实例，则从内存的角度来看，避免使用大映射（例如，通过将相关的映射元素分组到子映射中以减少元素数量）会更有效。

使用映射语法

使用映射语法通常比使用 maps 模块中对应的函数效率稍高。

对于只能使用映射语法实现的以下操作，映射语法的效率提升更加明显：

  • 匹配多个字面键
  • 更新多个字面键
  • 向映射添加多个字面键

例如：

推荐做法

Map = Map1#{x := X, y := Y, z := Z}

不推荐做法

Map2 = maps:update(x, X, Map1),
Map3 = maps:update(y, Y, Map2),
Map = maps:update(z, Z, Map3)

如果映射是一个小映射，则第一个示例的运行速度大约快三倍。

请注意，对于变量键，元素会从左到右顺序更新。例如，给定以下使用变量键进行的更新：

Map = Map1#{Key1 := X, Key2 := Y, Key3 := Z}

编译器会像这样重写代码，以确保更新按从左到右的顺序应用

Map2 = Map1#{Key1 := X},
Map3 = Map2#{Key2 := Y},
Map = Map3#{Key3 := Z}

如果已知键存在于映射中，对于小型映射，使用 := 运算符比使用 => 运算符效率稍高。

使用 maps 模块中的函数

下面是一些关于 maps 模块中大多数函数的说明。对于每个函数，都会说明其实现语言（C 或 Erlang）。我们提到语言的原因是它可以提示函数的效率如何

  • 如果一个函数是用 C 实现的，那么几乎不可能用 Erlang 更高效地实现相同的功能。

  • 但是，有可能在性能上超越用 Erlang 实现的 maps 模块中的函数，因为它们的实现通常是为了使所有可能的输入的性能都合理。

    例如，maps:map/2 会迭代映射的所有元素，调用映射函数，将更新后的映射元素收集到一个列表中，最后使用 maps:from_list/1 将列表转换回映射。如果已知映射中最多只有百分之一的值会发生变化，那么仅更新已更改的值会更有效率。

注意

本节中给出的实现细节将来可能会发生变化。

maps:filter/2

maps:filter/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的映射。如果已知只有少数值会被删除，那么避免使用 maps:filter/2 并编写一个使用 maps:remove/3 删除不需要的值的函数会更有效率。

maps:filtermap/2

maps:filtermap/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的映射。有关如何实现更高效的版本，请参阅 maps:map/2 和 maps:filter/2 的说明。

maps:find/2

maps:find/2 是用 C 实现的。

使用映射匹配语法而不是 maps:find/2 会稍微更有效率，因为可以避免构建 {ok,Value} 元组。

maps:get/2

作为一种优化，编译器会将对 maps:get/2 的调用重写为对守卫 BIF map_get/2 的调用。对守卫 BIF 的调用比对其他 BIF 的调用效率更高，使得性能与使用映射匹配语法类似。

如果映射很小，并且键是在编译时已知的常量，那么使用映射匹配语法比多次调用 maps:get/2 更有效率。

maps:get/3

作为一种优化，编译器会将对 maps:get/3 的调用重写为类似于以下 Erlang 代码：

Result = case Map of
             #{Key := Value} -> Value;
             #{} -> Default
         end

这相当有效率，但如果使用小型映射作为使用记录的替代方案，通常最好不要依赖默认值，因为它会阻止键的共享，最终可能会比不将默认值存储在映射中使用的内存更多。

如果仍然需要默认值，请考虑将默认值放入映射中，并将该映射与另一个映射合并，而不是多次调用 maps:get/3

DefaultMap = #{Key1 => Value2, Key2 => Value2, ..., KeyN => ValueN},
MapWithDefaultsApplied = maps:merge(DefaultMap, OtherMap)

这有助于在默认映射和应用默认值的映射之间共享键，只要默认映射包含所有将要使用的键，而不仅仅是那些具有默认值的键。这是否比多次调用 maps:get/3 更快取决于映射的大小和默认值的数量。

变更

在 OTP 26.0 之前，maps:get/3 是通过调用函数而不是将其重写为 Erlang 表达式来实现的。现在它稍微快一些，但不能再被跟踪。

maps:intersect/2, maps:intersect_with/3

maps:intersect/2 和 maps:intersect_with/3 是用 Erlang 实现的。它们都使用 maps:from_list/1 创建新的映射。

注意

映射通常是实现集合的最有效方式，但一个例外是交集运算，其中对 ordsets 使用的 ordsets:intersection/2 可能比对作为映射实现的集合使用 maps:intersect/2 更有效率。

maps:from_list/1

maps:from_list/1 是用 C 实现的。

maps:from_keys/2

maps:from_keys/2 是用 C 实现的。

maps:is_key/2

作为一种优化，编译器会将对 maps:is_key/2 的调用重写为对守卫 BIF is_map_key/2 的调用。对守卫 BIF 的调用比对其他 BIF 的调用效率更高，使得性能与使用映射匹配语法类似。

maps:iterator/1

maps:iterator/1 在 C 和 Erlang 中高效实现。

maps:keys/1

maps:keys/1 是用 C 实现的。如果需要对结果列表进行排序，请使用 lists:sort/1 对结果进行排序。

maps:map/2

maps:map/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的映射。如果已知只有少数值会被更新，那么避免使用 maps:map/2 并编写一个调用 maps:update/3 仅更新已更改的值的函数会更有效率。

maps:merge/2

maps:merge/2 是用 C 实现的。对于小型映射，如果该参数映射包含所有键，则键元组可以与任何参数映射共享。如果可能，优先使用文字键元组。

变更

maps:merge/2 共享键元组的功能是在 OTP 26.0 中引入的。旧版本总是在调用者的堆上构建一个新的键元组。

maps:merge_with/3

maps:merge_with/3 是用 Erlang 实现的。它更新并返回两个映射中较大的那个。

maps:new/0

编译器会将对 maps:new/0 的调用重写为使用语法 #{} 来构造一个空映射。

maps:next/1

maps:next/1 在 C 和 Erlang 中高效实现。

maps:put/3

maps:put/3 是用 C 实现的。

如果已知键已存在于映射中，maps:update/3 比 maps:put/3 效率稍高。

如果键是在编译时已知的常量，那么使用带有 => 运算符的映射更新语法比多次调用 maps:put/3 更有效率，特别是对于小型映射。

maps:remove/2

maps:remove/2 是用 C 实现的。

maps:size/1

作为一种优化，编译器会将对 maps:size/1 的调用重写为对守卫 BIF map_size/1 的调用。对守卫 BIF 的调用比对其他 BIF 的调用效率更高。

maps:take/2

maps:take/2 是用 C 实现的。

maps:to_list/1

maps:to_list/1 在 C 和 Erlang 中高效实现。如果需要对结果列表进行排序，请使用 lists:sort/1 对结果进行排序。

注意

映射通常比 gb_trees 性能更高，但如果需要频繁地在排序列表之间进行转换，则 gb_trees 可能是更好的选择。

maps:update/3

maps:update/3 是用 C 实现的。

如果键是在编译时已知的常量，那么使用带有 := 运算符的映射更新语法比多次调用 maps:update/3 更有效率，特别是对于小型映射。

maps:values/1

maps:values/1 是用 C 实现的。

maps:with/2

maps:with/2 是用 Erlang 实现的。它使用 maps:from_list/1 创建一个新的映射。

maps:without/2

maps:without/2 是用 Erlang 实现的。它返回输入映射的修改副本。