性能特征

前面的解释已经明确指出，不同的集合类型具有不同的性能特征。这通常是选择一种集合类型而不是另一种集合类型的主要原因。你可以在以下两个表格中看到对集合上一些常见操作的性能特征总结。

序列类型的性能特征

	head	tail	apply	update	prepend	append	insert
immutable
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	-
mutable
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	-	-	-

集合和映射类型的性能特征

	lookup	add	remove	min
immutable
HashSet/HashMap	eC	eC	eC	L
TreeSet/TreeMap	Log	Log	Log	Log
BitSet	C	L	L	eC1
ListMap	L	L	L	L
mutable
HashSet/HashMap	eC	eC	eC	L
WeakHashMap	eC	eC	eC	L
BitSet	C	aC	C	eC1
TreeSet	Log	Log	Log	Log

脚注：¹ビットが密に詰め込まれていると仮定しています。

これらの 2 つの表のエントリは次のように説明されます。

C	操作は (高速) 定数時間かかります。
eC	操作は実質的に定数時間かかりますが、ベクトルの最大長やハッシュキーの分布などの仮定に依存する場合があります。
aC	操作は償却定数時間かかります。操作の呼び出しによっては時間がかかる場合がありますが、多くの操作が実行された場合、平均して操作 1 つあたり定数時間しかかかりません。
Log	操作はコレクションサイズの対数に比例した時間がかかります。
L	操作は線形です。つまり、コレクションサイズに比例した時間がかかります。
-	操作はサポートされていません。

最初の表では、次の操作を持つシーケンスタイプ (不変と可変の両方) を扱います。

head	シーケンスの最初の要素を選択します。
tail	最初の要素を除くすべての要素で構成される新しいシーケンスを生成します。
apply	インデックス付け。
update	不変シーケンスの関数更新 (updated 使用)、可変シーケンスの副作用更新 (update 使用)。
prepend	シーケンスの先頭に要素を追加します。不変シーケンスの場合、新しいシーケンスが生成されます。可変シーケンスの場合、既存のシーケンスが変更されます。
append	シーケンスの末尾に要素を追加します。不変シーケンスの場合、新しいシーケンスが生成されます。可変シーケンスの場合、既存のシーケンスが変更されます。
insert	シーケンス内の任意の位置に要素を挿入します。これは、可変シーケンスに対してのみ直接サポートされています。

2 番目の表では、次の操作を持つ可変および不変セットとマップを扱います。

lookup	要素がセットに含まれているかどうかをテストするか、キーに関連付けられた値を選択します。
add	セットに新しい要素を追加するか、マップにキーと値のペアを追加します。
remove	セットから要素を削除するか、マップからキーを削除します。
min	セットの最小要素またはマップの最小キー。