Question

1. 不可变序列的性能特征：

   	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	-
   Queue	aC	aC	L	L	L	C	-
   Range	C	C	C	-	-	-	-
   String	C	L	C	L	L	L	-

   其中：

   • C 表示 $ O(1 ) $ 的常量时间复杂度。
   • eC 表示从效果上来看是常量时间复杂度，但是这取决于某些前提假设，如：假设向量的最大长度或者哈希键的分布情况。
   • aC 表示平摊的常量时间复杂度。该操作的某些调用可能会耗时一些，但是大量操作的平均时间为常量时间。
   • L 表示 $ O(n) $ 的线性时间复杂度。
   • Log 表示 $ O(\log n) $ 的对数时间复杂度。
   • - 表示对应的集合不支持该操作。

   每一列表示：

   • head：选择序列的第一个元素。
   • tail：选择序列除了第一个元素之外的外部元素集合。
   • apply：下标索引。
   • update：对不可变序列执行函数式更新（updated 方法），对可变序列执行原地更新（update 方法）。
   • prepend：将元素添加到序列头部。对不可变序列而言，该操作创建一个新的序列；对可变序列而言，该操作执行原地修改。
   • append：将元素添加到序列尾部。对不可变序列而言，该操作创建一个新的序列；对可变序列而言，该操作执行原地修改。
   • insert：将元素插入到序列中的指定位置。该操作只对可变序列有效。

2. 可变序列的性能特征：

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

3. 不可变 Set/Map 的性能特征：

   	lookup	add	remove	min
   HashSet/HashMap	eC	eC	eC	L
   TreeSet/TreeMap	Log	Log	Log	Log
   BitSet	C	L	L	eC
   ListMap	L	L	L	L

4. 可变 Set/Map 的性能特征：

   	lookup	add	remove	min
   HashSet/HashMap	eC	eC	eC	L
   WeakHashMap	eC	eC	eC	L
   BitSet	C	aC	C	eC

   其中每一列表示：

   • lookup：测试某个元素是否包含在set 中，或者选择某个 key 关联的值。
   • add：添加新元素到集合中。
   • remove：从集合中移除元素。
   • min：set 的最小元素，或者map 的最小key 。