转载：不允许转载请告知，在第一时间删除。
scala 集合类库使用率非常频繁，也是其它语言开发者羡慕不已功能。本篇讲说明类库中相同的API的执行效率对比，作为使用时的参考依据。只是理论上的特点，没有具体指标量化。
原文传送门 Author: heathermiller
为阅读方便，对内容稍作调整。
不同的容器类型具有不同的性能特点。这通常是选择容器类型的首要依据。以下的两张表格，总结了一些关于容器类型常用操作的性能特点。
标志位解释
为便于理解，先对各标志位做说明：
| 术语 | 操作功能描述 |
|---|---|
| C | 指操作的时间复杂度为常数 |
| eC | 指操作的时间复杂度实际上为常数，但可能依赖于诸如一个向量最大长度或是哈希键的分布情况等一些假设。 |
| aC | 该操作的均摊运行时间为常数。某些调用的可能耗时较长，但多次调用之下，每次调用的平均耗时是常数。 |
| Log | 操作的耗时与容器大小的对数成正比。 |
| L | 操作是线性的，耗时与容器的大小成正比。 |
| - | 操作不被支持。 |
序列类型的性能特点
根据需求选择序列，会大幅提升性能。具体的性能评估如下：
不可变序列性能特点
| 不可变序列 | head | tail | apply | update | prepend | append | insert |
|---|---|---|---|---|---|---|---|
| List | C | C | L | L | C | L | - |
| Stream | C | C | L | L | C | L | - |
| Vector | eC | eC | eC | eC | eC | eC | - |
| Stack | C | C | L | L | C | L | L |
| Queue | aC | aC | L | L | C | C | - |
| Range | C | C | C | - | - | - | - |
| String | C | L | C | L | L | L | - |
可变序列性能特点
| 可变序列 | head | tail | apply | update | prepend | append | insert |
|---|---|---|---|---|---|---|---|
| ArrayBuffer | C | L | C | C | L | aC | L |
| ListBuffer | C | L | L | L | C | C | L |
| StringBuilder | C | L | C | C | L | aC | L |
| MutableList | C | L | L | L | C | C | L |
| Queue | C | L | L | L | C | C | L |
| ArraySeq | C | L | C | C | - | - | - |
| Stack | C | L | L | L | C | L | L |
| ArrayStack | C | L | C | C | aC | L | L |
| Array | C | L | C | C | - | - | - |
序列中操作的功能描述
- head: 选择序列的第一个元素
- tail : 生成一个包含除第一个元素以外所有其他元素的新的列表。
- apply : 索引
- update: 功能性更新不可变序列，同步更新可变序列。
- prepend: 添加一个元素到序列头。对于不可变序列，操作会生成个新的序列。对于可变序列，操作会修改原有的序列。
- append: 在序列尾部插入一个元素。对于不可变序列，这将产生一个新的序列。对于可变序列，这将修改原有的序列。
- insert : 在序列的任意位置上插入一个元素。只有可变序列支持该操作。
集合和映射类型的性能特点
不可变序列性能
| 不可变序列 | lookup | add | remove | min |
|---|---|---|---|---|
| HashSet/HashMap | eC | eC | eC | L |
| TreeSet/TreeMap | Log | Log | Log | Log |
| BitSet | C | L | L | eC1 |
| ListMap | L | L | L | L |
可变序列性能
| 可变序列 | lookup | add | remove | min |
|---|---|---|---|---|
| HashSet/HashMap | eC | eC | eC | L |
| WeakHashMap | eC | eC | eC | L |
| BitSet | C | aC | C | eC1 |
| TreeSet | Log | Log | Log | Log |
可变和不可变集与映射功能描述
- lookup 测试一个元素是否被包含在集合中，或者找出一个键对应的值
- add 添加一个新的元素到一个集合中或者添加一个键值对到一个映射中
- remove 移除一个集合中的一个元素或者移除一个映射中一个键。
- min 集合中的最小元素，或者映射中的最小键。
