erlang 数据结构 --maps

1. 今天是maps

1.1. key-value 数据结构 1.2. 更好的模式匹配

2.操作：

2.0 格式

1> F = #{a => 1, b => 2}. #{a => 1,b => 2}

2.1. 更新key-value

=> 如果原本有key， 则更新, 如果没有key，就插入key-value; := 更新已有的key的value，如果原来没有key，就报错

3> F1 = F#{a => 2}. #{a => 2,b => 2} 4> F2 = F#{c => 3}. #{a => 1,b => 2,c => 3} 5> F3 = F#{a := 1}. #{a => 1,b => 2} 8> F5 = F#{c := 2}. ** exception error: {badkey,c} in function maps:update/3 called as maps:update(c,2,#{a => 1,b => 2}) in call from erl_eval:'-expr/5-fun-0-'/2 (erl_eval.erl, line 255) in call from lists:foldl/3 (lists.erl, line 1263)

2.2 模式匹配

maps 记录频率

freq(Is) -> freq(Is, #{}). freq([I|Is], #{I := C} = M) -> freq(Is, M#{ I := C + 1}); freq([I|Is], M) -> freq(Is, M#{ I => 1 }); freq([], M) -> maps:to_list(M).

gb_trees用于比较的等效代码：

freq(Is) -> freq(Is, gb_trees:empty()). freq([I|Is], T) -> case gb_trees:lookup(I, T) of none -> freq(Is, gb_trees:enter(I, 1), T); {value, V} -> freq(Is, gb_trees:enter(I, V + 1, T)) end; freq([], T) -> gb_trees:to_list(T).

这也是maps相比于其他key-value数据结构不同的地方。

3 内存实现

eep中对内存的描述为 Data layout: map_ext |———————————–

14116SizeKeysValues

erl_map.h 中对内存实现的描述

/* map node * * ----------- * Eterm THING * Uint size * Eterm Keys -> {K1, K2, K3, ..., Kn} where n = size * ---- * Eterm V1 * ... * Eterm Vn, where n = size * ----------- */ /* the head-node is a bitmap or array with an untagged size */

maps 为boxed 对象， 开头为boxed对象的必要tag，接下来为size， 之后Eterm为keys（ 指向了一段连续的内存key tuple）， 之后为value tuple 我们可以从源码 erl_map.c erts_maps_get/2 实现中验证这种看法， 这个函数的目的是得到key对应的value

const Eterm * erts_maps_get(Eterm key, Eterm map) { Uint32 hx; if (is_flatmap(map)) { Eterm *ks, *vs; flatmap_t *mp; Uint n, i; mp = (flatmap_t *)flatmap_val(map); n = flatmap_get_size(mp); if (n == 0) { return NULL; } ks = (Eterm *)tuple_val(mp->keys) + 1; vs = flatmap_get_values(mp); if (is_immed(key)) { for (i = 0; i < n; i++) { if (ks[i] == key) { return &vs[i]; } } } else { for (i = 0; i < n; i++) { if (EQ(ks[i], key)) { return &vs[i]; } } } return NULL; } ASSERT(is_hashmap(map)); hx = hashmap_make_hash(key); return erts_hashmap_get(hx, key, map); }

可以看出先在ks的tuple中找到key对应的index i， 然后从value的tuple vs[i] 得到。

4.使用场景

有很多种说法，

4.1. 替换record ，

No more need for records

4.2 更好的key-value 数据结构

也有认为是将maps定义为一个具有模式匹配的更好的key-value数据结构。虽然从上面实现上看并不是很理想， 比如当寻找某个值的时候其实是遍历了整个keys tuple，o(N) 的时间复杂度， 我们可以在实际项目中看到的是maps 替换了proplists，但是， 相比于其他比如dict， gb_tree, 还没有优势。

5.后语：

自己只是很简单的看了下目前maps的接口，使用和内存实现，以及自己看到的使用情况。更加具体的内容可以看引用中大神的blog

6. 引用

6.1. yufeng Erlang 新数据类型Map的定位和性能 6.2. siyao Erlang 的新数据结构 map 浅析 6.3. 坚强2002 当我们谈论Erlang Maps时,我们谈论什么 Part 1 and 当我们谈论Erlang Maps时,我们谈论什么 Part 2 6.4. learnyousomeerlang