Erlang 的新数据结构 map 浅析
更新：文中示例代码直接从Joe的新版 Erlang 书中摘抄而来，其中模式匹配的代码有错误，现已纠正。应该用 := 匹配字段，而不是 => 。
即将发布的 Erlang 17 最大变化之一包括新的数据结构 map 的引入。其他很多动态语言，都在语言层面原生地支持映射的数据结构，因此在写程序的时候随手需要表示一个类似对象结构这样的映射数据非常方便。Erlang 原来也有一个类似的结构，record，不过用起来不太方便，语法比较丑陋，“key”只能是原子，而且整个结构在定义了之后是固定的。当然，在标准库中提供了一个 dict 模块，但是这个模块不是语言层面原生提供的，所以使用略麻烦，比如说不能直接进行模式匹配。
现在 Erlang 终于有 map 了，在语言层面提供了支持，用起来就很方面。下面通过 Joe 老头新版 Erlang 书中的例子简单说明一下 map 的用法。
首先是创建：
F1 = #{ a => 1, b => 2 }.Facts = #{ {wife,fred} => "Sue", {age, fred} => 45,{daughter,fred} => "Mary",{likes, jim} => [...]}.
需要 map 的时候随手拿来，不需要事先定义好 map 的结构。而且 key 可以是任意 Eterm，比如 F1 中的原子，F2 中的元组。当然也可以不同类型的 key 的混合。
然后是修改：
F3 = F1#{ c => xx }.始终不要忘了 Erlang 变量都是 immutable 的，所以修改操作实际上会创建新的 map。这里就创建了 F3。之前 F1 中没有 c 字段，=> 操作符的意思表示新创建字段 c，然后把 c 映射到 xx。如果 F1 中原本有 c 字段了，那么这个操作会更新 c 字段的值。另外还有一个 := 操作：
F4 = F1#{ c := 3}.:= 操作表示更新一个已有的 key。这句话会抛异常，因为 F1 中没有 c 这个键。
然后就是模式匹配了：
Henry8 = #{ class => king, born => 1491, died => 1547 }.#{ born := B } = Henry8.
第 1 行将 Henry8 绑定至新创建的 map，第 2 行左侧和右侧匹配，将匹配的 born 键的值绑定至变量 B。很方便吧，再也不用麻烦地调用 dict:fetch/2 这样的函数了。
综上，总结 map 是一个支持字段动态变化的映射数据结构。要注意的是，map 中的 keys 是保持固定顺序的，所以每次输出的时候 keys 的顺序是固定且确定的。下面我们来看一下 map 数据结构在虚拟机的内部实现，以了解 map 结构的局限性。
在 erl_map.h 头文件中可以看到 ascii art 形式的 map 内部结构图：
THING 表示 map 的 Eterm 值。map 是一个 boxed 对象，boxed 对象的一般格式参见 http://www.cnblogs.com/zhengsyao/p/erlang_eterm_implementation_4_boxed.html，当然 map 有自己的新的 tag。然后下面一个字表示 map 的大小，即包含的 kv 对个数。接下来是一个指向一个元组的指针，这个元组中按固定顺序保存了所有的 key 的 Eterm。然后接下来的 n 个 Eterm 就表示 n 个值的 Eterm。
从这个结构我们可以看出 map 存储的特点：线性存储。所有的 key 依次在 tuple 中，value 也依次保存在连续内存空间中。所以查找一个 key 的操作相当于在 key 元组中线性搜索到目标 key 的索引，然后用这个索引得到对应值的 Eterm，参见 beam_emu.c 中的 get_map_element() 函数。
根据之前的描述，更新操作分为两种：=>操作符表示的更新和 := 操作符表示的更新。
先说 := 的更新，这个比较简单，因为 key 都没变。beam_emu.c 中的 update_map_exact() 函数进行这种更新。更新操作创建一个新的 map 是不可避免的。因此上图中的数据结构要创建一个新的。其中所有的 value 除了被更新的那些都复制一遍。由于 key 都没变，所以表示 key 的元组可以复用，keys 指针指向原来的元组即可。
=> 更新复杂一些，因为会改变 map 的结构，这个操作实现在 beam_emu.c 中的 update_map_assoc() 函数中。这个操作也很直观，首先按最坏情况，即更新操作中所有的 key 都不是原来 map 中的 key 的情况，创建足够的空间能完整保存两个 kv 集合，内存布局如下所示：
也就是新创建了一个元组，然后把这个元组放在新创建的 map 上面了。boxed tuple pointer 就是指向这个 key 元组的指针。然后就是依次比较 key 并填充这个数据结构了。由于编译器保证了老 key 序列和新 key 序列是有序的，所以这个操作复杂度是 O(num_of_oldkey + num_of_newkey)。
为了支持 map 的这些操作，编译器可以将所有 map 操作归结为以下 5 个操作：
154: put_map_assoc/5
155: put_map_exact/5
156: is_map/2
157: has_map_field/3
158: get_map_element/4
上面这 5 个条目实际上就是 5 条新的 beam 指令。put_map_assoc 对应的是 => 更新，参数中包含所有更新的 key 和 value。put_map_exact 对应的是 := 更新。is_map 是类型判断，和 is_list is_tuple 之类的是一样的，可以放在 guard 里的。has_map_field 判断是否有字段，get_map_element 获得字段映射的值。实际上我们在 Erlang 里面写的那些狂拽炫酷的模式匹配，经过编译器的处理之后，就是一堆这个存在不存在那个有没有这个是不是等于那个的指令。
以上这些实际上只是一个起点，语言层面的变化还会引起其他层面的变化，比如最核心的是标准库（stdlib）、类型分析器（dialyzer、hipe）、编译器（compiler）、调试器（debugger）、对应的 BIF支持以及 NIF 支持等，然后就是几个IDE都迅速跟进了，Erlide 和 Idea 的 Erlang 插件都支持，再就是各种书籍教程了。
原发布日期：2014-03-09
ps: 新版erlang map的实现有两种，Flatmap 和 HashMap，Flamap正是本文所描述的，当key数量超过32时，就会用HashMap的方式存储，性能相对较好