過時公告
先前的說明已經清楚地說明不同的收集類型有不同的效能特性。這通常是選擇一種收集類型而不是另一種的主要原因。您可以在下表中看到對收集的一些常見操作的效能特性的摘要。
序列類型的效能特性
| 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 |
註腳：1 假設位元緊密封裝。
這兩個表中的條目說明如下
| C | 操作需要（快速）常數時間。 |
| eC | 操作需要有效常數時間，但這可能取決於某些假設，例如向量的最大長度或雜湊金鑰的分配。 |
| aC | 操作需要攤銷常數時間。某些調用操作可能需要更長的時間，但如果對平均值執行許多操作，則每個操作只會花費常數時間。 |
| Log | 操作時間與集合大小的對數成正比。 |
| L | 操作為線性，也就是說操作時間與集合大小成正比。 |
| - | 不支援此操作。 |
第一個表格處理序列類型，包括不可變和可變類型，以及下列操作
| head | 選取序列的第一個元素。 |
| tail | 產生一個新的序列，包含所有元素，但第一個元素除外。 |
| apply | 索引。 |
| update | 函式更新（使用 updated）適用於不可變序列，副作用更新（使用 update）適用於可變序列。 |
| prepend | 在序列前面新增一個元素。對於不可變序列，這會產生一個新的序列。對於可變序列，這會修改現有的序列。 |
| append | 在序列後面新增一個元素。對於不可變序列，這會產生一個新的序列。對於可變序列，這會修改現有的序列。 |
| insert | 在序列中的任意位置插入一個元素。這僅直接支援可變序列。 |
第二個表格處理可變和不可變集合和對應，以及下列操作
| lookup | 測試集合中是否包含一個元素，或選取與金鑰關聯的值。 |
| add | 在集合中新增一個新元素，或在對應中新增一個金鑰/值對。 |
| remove | 從集合中移除一個元素，或從對應中移除一個金鑰。 |
| min | 集合中最小的元素，或對應中最小的金鑰。 |