Collection Performance & Equality

This content was generated with the assistance of AI and should be verified against the official documentation before being relied on in production.

The reference material consulted while preparing these pages is listed in the section bibliography.

This page is written against Scala 3.10 (3.10.0, released 2026-10-12) and every example was compiled and run with Scala 3.10.0 through Scala CLI on JDK 26 (checked on 2026-10-15). The collections API is the Scala 2.13 one in all of Scala 3 (since 3.8 the library is compiled by Scala 3 and versioned with the compiler), so the 3.9 LTS line (3.9.0, 2026-09-03) and 3.3 LTS (3.3.8) behave identically for everything shown here.

Choosing a collection is mostly choosing a set of costs. The standard library publishes those costs in two tables, and this page explains how to read them, which assumptions hide behind the letters, and what the library promises about equality and hashing, which is the other half of "does this collection behave the way I expect". The examples use the trailhead scenario, where a toolkit plans hikes on a network of mountain trails and keeps routes as sequences of segments. For the types themselves see Sequences and Sets & Maps; for how the operations are built see Collections Architecture & Custom Collections.

How to read the tables

Every entry is one of six symbols. They are costs per operation, as a function of the size of the collection.

Symbol Meaning

C

Constant time: fast and independent of the size.

eC

Effectively constant time. The operation is logarithmic in theory, but with a very large base or a very bounded depth, so for any realistic size it behaves as constant. It can depend on assumptions such as the maximum length of a vector or the distribution of hash codes.

aC

Amortized constant time. A single call can be slow (a buffer that has to grow, a queue that has to reverse its back list), but over many operations the average cost per operation is constant.

Log

Proportional to the logarithm of the size. Balanced trees (TreeSet, TreeMap).

L

Linear: proportional to the size of the collection.

-

The operation is not supported on that collection.

"Effectively constant" is the symbol most worth understanding, because it covers the two workhorses of the library. Vector is a tree with up to 32 children per node, so a vector of a billion elements is about six levels deep, and a lookup visits at most that many nodes. The immutable HashSet and HashMap are hash tries with the same 32-way branching, so their depth is also tiny, provided that hashCode spreads keys well. The "effectively" qualifier is there because the bound depends on those assumptions, not on a measurement.

Sequence types

The first table covers the operations of sequences, immutable and mutable. The operations are:

Operation Meaning

head

Select the first element.

tail

Produce a sequence with all elements except the first.

apply

Indexing, xs(i).

update

Functional update with updated for immutable sequences, side-effecting update for mutable ones.

prepend

Add an element to the front. Immutable sequences produce a new sequence, mutable ones change the existing one.

append

Add an element to the end. Same remark.

insert

Insert an element at an arbitrary position. Only supported directly by mutable sequences.
Immutable head tail apply update prepend append insert

List

C

C

L

L

C

L

-

LazyList

C

C

L

L

C

L

-

ArraySeq

C

L

C

L

L

L

-

Vector

eC

eC

eC

eC

eC

eC

-

Queue

aC

aC

L

L

C

C

-

Range

C

C

C

-

-

-

-

String

C

L

C

L

L

L

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

Queue

C

L

L

L

C

C

L

ArraySeq

C

L

C

C

-

-

-

Stack

C

L

L

L

C

L

L

Array

C

L

C

C

-

-

-

ArrayDeque

C

L

C

C

aC

aC

L

Source: Scala Collections (2.13): Performance Characteristics

Reading the tables gives the rules of thumb that most code needs:

  • List is a singly linked list. Anything at the front (head, tail, prepend) is constant, anything that needs an index or the end is linear. Use it as a stack or when you consume it with pattern matching and recursion.

  • Vector is the default general-purpose immutable sequence: every operation is effectively constant, which is why it is the usual answer when you do not know the access pattern. Its constants are higher than those of List at the front.

  • ArrayBuffer and ArrayDeque are the mutable defaults. ArrayBuffer appends in amortized constant time and is fast to index, but prepending and inserting in the middle shift elements. ArrayDeque makes both ends amortized constant.

  • ListBuffer exists to build a List by appending in constant time; it is slow to index.

  • Strings and arrays index in constant time but cannot grow; every "modification" of a String copies it.

  • Range stores only start, end and step, so everything it supports is constant, which is why 0 until 1_000_000_000 is free until you traverse it.

Structural sharing

The reason immutable updates are cheap is that the new collection reuses most of the old one. Prepending to a List creates one node and points it at the old list, and updated on a Vector copies only the path from the root to the changed leaf. The next program shows both.

//> using scala 3.10.0
package trailhead

enum Segment:
  case Path(km: Double)
  case Ridge(km: Double)
  case Hut(beds: Int)

@main def run(): Unit =
  import Segment.*
  // List: prepend is constant time and shares the tail
  val route = List[Segment](Path(2.5), Ridge(1.2))
  val longer = Hut(20) :: route
  println(longer)
  println(s"tail shared with the original: ${longer.tail eq route}")

  // Vector: indexed access and append are effectively constant time
  val v = Vector[Segment](Path(2.5), Ridge(1.2))
  val v2 = v :+ Hut(20)
  println(v2(2))
  println(s"v unchanged: ${v.size == 2}, v2 has ${v2.size} elements")

  // updated on a Vector shares most of its structure
  val big = Vector.tabulate(100000)(i => i)
  val big2 = big.updated(50000, -1)
  println(s"${big(50000)} ${big2(50000)} ${big2.size}")
List(Hut(20), Path(2.5), Ridge(1.2))
tail shared with the original: true
Hut(20)
v unchanged: true, v2 has 3 elements
50000 -1 100000

Source: Scala Collections (2.13): Performance Characteristics

longer.tail eq route is true because the tail of the new list is the old list itself, not a copy. The cost of the prepend is constant whatever the length of route, and it is also why prepending is the idiomatic way to build a List, with a reverse at the end if the order matters.

A sanity check, not a benchmark

A linear operation on a long collection is easy to observe. The next program reads elements near the end of a List and of a Vector with the same 50,000 elements. The timings are machine dependent and a plain stopwatch is not a benchmark (there is no isolation from warm-up, garbage collection or the JIT), so only the ratio matters. For real measurements use sbt-jmh or the JMH harness directly (not run here).

//> using scala 3.10.0
def time[A](body: => A): Long =
  val t0 = System.nanoTime()
  body
  (System.nanoTime() - t0) / 1_000_000

@main def run(): Unit =
  val n = 50_000
  val list = List.tabulate(n)(identity)
  val vec = Vector.tabulate(n)(identity)
  val reads = 5_000
  // read elements near the end: List.apply walks the list, Vector.apply does not
  def sum(f: Int => Int): Long =
    var acc = 0L
    var i = 0
    while i < reads do
      acc += f(n - 1 - (i % 10))
      i += 1
    acc
  sum(list(_)); sum(vec(_)) // warm up
  val tList = time(sum(list(_)))
  val tVec = time(sum(vec(_)))
  println(s"List ${tList} ms, Vector ${tVec} ms for $reads reads at index ~$n")
  println(s"List.apply was at least 20 times slower: ${tList >= 20 * math.max(tVec, 1)}")
List 396 ms, Vector 0 ms for 5000 reads at index ~50000
List.apply was at least 20 times slower: true

Source: Scala Collections (2.13): Performance Characteristics

The table predicted this: apply is L for List and eC for Vector. Interleaving such reads with a loop over indexes (for i <- 0 until xs.length do xs(i)) on a List is the classic way to turn a linear pass into a quadratic one.

Set and map types

The second table covers lookup, add, remove and the smallest element (min) of sets and maps. For maps, lookup is selecting a value by key, add is adding a key/value pair, and remove is removing a key.

Immutable lookup add remove min

HashSet / HashMap

eC

eC

eC

L

TreeSet / TreeMap

Log

Log

Log

Log

BitSet

C

L

L

eC1

VectorMap

eC

eC

aC

L

ListMap

L

L

L

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

1 Assuming the bits are densely packed.

Source: Scala Collections (2.13): Performance Characteristics

Notes on the table that the letters alone do not say:

  • HashSet/HashMap are the default Set and Map beyond four elements. min is linear because a hash structure has no order. Use TreeSet/TreeMap (balanced trees, Log everywhere, including min) when you need ordered traversal or range queries.

  • VectorMap keeps insertion order with effectively constant lookup and add, but removal is only amortized constant; ListMap keeps insertion order too but every operation walks a linked list. Prefer VectorMap whenever order matters.

  • BitSet is a compact set of small non-negative integers. Membership is constant, but adding to or removing from an immutable BitSet is linear in the number of words it stores (L), and min is only effectively constant if the set is dense, because the search scans the words for the first non-empty one.

  • Immutable Set and Map with up to four elements use specialised classes (Set1 …​ Set4, Map1 …​ Map4) that are faster than a hash trie at that size. This is an implementation detail, but it explains why Set(1, 2, 3) prints in insertion order while larger sets do not.

The next program exercises the "amortized" and "insertion order" entries.

//> using scala 3.10.0
import scala.collection.immutable.{ListMap, VectorMap, Queue, BitSet}
import scala.collection.mutable

@main def run(): Unit =
  // Immutable Queue: amortized constant enqueue/dequeue
  val q = Queue("Refugio", "Collado").enqueue("Pico")
  val (first, rest) = q.dequeue
  println(s"$first, then $rest")

  // mutable.ArrayDeque: amortized constant at both ends
  val dq = mutable.ArrayDeque(2, 3)
  dq.prepend(1)
  dq.append(4)
  println(dq)

  // ListMap vs VectorMap: both keep insertion order, lookups differ
  val stops = Seq("Refugio" -> 0, "Collado" -> 1, "Pico" -> 2)
  println(ListMap.from(stops).keys.toList)
  println(VectorMap.from(stops).keys.toList)
  println(VectorMap.from(stops).removed("Collado").keys.toList)

  // BitSet: lookup is constant, min is effectively constant only for densely packed bits
  val bits = BitSet(3, 5, 8)
  println(s"${bits.contains(5)} ${bits.min}")

  // length is linear on a List, constant on a Vector; knownSize tells you when it is cheap
  println(s"${List(1, 2, 3).knownSize} ${Vector(1, 2, 3).knownSize} ${LazyList(1, 2).knownSize}")
  println(List(1, 2, 3).sizeCompare(2))
Refugio, then Queue(Collado, Pico)
ArrayDeque(1, 2, 3, 4)
List(Refugio, Collado, Pico)
List(Refugio, Collado, Pico)
List(Refugio, Pico)
true 3
-1 3 -1
1

Source: Scala Collections (2.13): Performance Characteristics

knownSize is the standard way to ask whether the size is already known without traversing: it returns -1 when it is not (a List or a LazyList). sizeCompare compares a collection with a number without computing the full length, so xs.sizeCompare(2) > 0 is the cheap spelling of xs.length > 2 on a List.

Why "effectively constant" depends on the hash code

Hash-based entries say eC, not C, because they assume keys spread out. The assumption is on your hashCode, so a key type with a poor hash turns the lookup into a scan of one bucket. The program below counts how many times equals is called to find the last of 2,000 keys, once with a constant hashCode and once with a well-distributed one.

//> using scala 3.10.0
import scala.collection.immutable.{HashSet, TreeSet}

var eqCalls = 0

final class BadKey(val id: Int):
  override def hashCode: Int = 42           // every key lands in the same bucket
  override def equals(o: Any): Boolean =
    eqCalls += 1
    o match
      case k: BadKey => k.id == id
      case _ => false

final class GoodKey(val id: Int):
  override def hashCode: Int = id.##
  override def equals(o: Any): Boolean =
    eqCalls += 1
    o match
      case k: GoodKey => k.id == id
      case _ => false

@main def run(): Unit =
  val n = 2000
  val bad = HashSet.from((0 until n).map(BadKey(_)))
  eqCalls = 0
  bad.contains(BadKey(n - 1))
  println(s"BadKey lookups made $eqCalls equals calls")
  val good = HashSet.from((0 until n).map(GoodKey(_)))
  eqCalls = 0
  good.contains(GoodKey(n - 1))
  println(s"GoodKey lookup made $eqCalls equals calls")
BadKey lookups made 2000 equals calls
GoodKey lookup made 1 equals calls

Source: Scala Collections (2.13): Performance Characteristics

With the constant hash the lookup degrades to linear (2,000 equals calls for 2,000 keys), while the good hash needs one. Case classes and the standard types get a consistent hashCode for free; the problem appears in hand-written keys and in hashCode implementations that only look at a few fields. See Case Classes for the generated members.

Equality

The collections library has one uniform rule for == and hashCode, summarised in two sentences:

  1. Collections are divided into three categories: sequences (Seq), sets (Set) and maps (Map). Collections in different categories are never equal, even when they contain the same elements.

  2. Within a category, two collections are equal if and only if they have the same elements (for sequences, the same elements in the same order). It does not matter which concrete class they are or whether they are mutable or immutable.

Source: Scala Collections (2.13): Equality

The next program tries a range of combinations. Pairs that cannot be equal by definition (a List against a Set) are written through an Any-typed value because Scala 3 rejects them at compile time, as the next section shows.

//> using scala 3.10.0
import scala.collection.immutable.{HashSet, TreeSet, ListMap, TreeMap}
import scala.collection.mutable

def asAny(x: Any): Any = x

@main def run(): Unit =
  println(s"List == Vector:            ${List(1, 2, 3) == Vector(1, 2, 3)}")
  println(s"List == mutable.Buffer:    ${List(1, 2, 3) == mutable.ArrayBuffer(1, 2, 3)}")
  println(s"List == Range:             ${List(1, 2, 3) == (1 to 3)}")
  println(s"List == LazyList:          ${List(1, 2, 3) == LazyList(1, 2, 3)}")
  println(s"List == Set:               ${asAny(List(1, 2, 3)) == Set(1, 2, 3)}")
  println(s"HashSet == TreeSet:        ${HashSet(1, 2) == TreeSet(2, 1)}")
  println(s"Set == mutable.Set:        ${Set(1, 2) == mutable.Set(2, 1)}")
  println(s"Map == ListMap:            ${Map("a" -> 1, "b" -> 2) == ListMap("b" -> 2, "a" -> 1)}")
  println(s"Map == TreeMap:            ${Map("a" -> 1) == TreeMap("a" -> 1)}")
  println(s"Map == Set of pairs:       ${asAny(Map("a" -> 1)) == Set("a" -> 1)}")
  println(s"List == Tuple:             ${asAny(List(1, 2)) == (1, 2)}")
  println(s"Vector(1,2) == Seq(1,2):   ${Vector(1, 2) == Seq(1, 2)}")
  println(s"Array == Array:            ${Array(1, 2) == Array(1, 2)}")
  println(s"Array.sameElements:        ${Array(1, 2).sameElements(Array(1, 2))}")
  println(s"Array.toSeq == Array.toSeq: ${Array(1, 2).toSeq == Array(1, 2).toSeq}")
  println(s"IArray == IArray:          ${IArray(1, 2) == IArray(1, 2)}")
  println(s"Array == List (mixed):     ${asAny(Array(1, 2)) == List(1, 2)}")
  println(s"hashCode equal (List/Vector): ${List(1, 2, 3).## == Vector(1, 2, 3).##}")
  println(s"hashCode equal (HashSet/TreeSet): ${HashSet(1, 2).## == TreeSet(2, 1).##}")
  println(s"Iterator sameElements:     ${Iterator(1, 2).sameElements(List(1, 2))}")
  println(s"Vector.sameElements(List): ${Vector(1, 2).sameElements(List(1, 2))}")
List == Vector:            true
List == mutable.Buffer:    true
List == Range:             true
List == LazyList:          true
List == Set:               false
HashSet == TreeSet:        true
Set == mutable.Set:        true
Map == ListMap:            true
Map == TreeMap:            true
Map == Set of pairs:       false
List == Tuple:             false
Vector(1,2) == Seq(1,2):   true
Array == Array:            false
Array.sameElements:        true
Array.toSeq == Array.toSeq: true
IArray == IArray:          false
Array == List (mixed):     false
hashCode equal (List/Vector): true
hashCode equal (HashSet/TreeSet): true
Iterator sameElements:     true
Vector.sameElements(List): true

Source: Scala Collections (2.13): Equality

The results follow from the rules:

  • A List, a Vector, an ArrayBuffer, a Range and a LazyList with the same elements are all equal, because they are all sequences. Hash codes agree too (the hashCode of a sequence is computed from its elements, in order, by the library), which is what lets a Vector(1, 2) find an entry stored under List(1, 2) in a Map[Seq[Int], String].

  • HashSet(1, 2) equals TreeSet(2, 1), and Map equals ListMap or TreeMap with the same entries: sets and maps ignore order, and == on a sorted set does not care that it has an ordering.

  • A Map is not a Set of pairs, and a List is not a tuple.

  • Arrays and IArray are not collections in this sense. They are JVM arrays, so == is reference equality: two arrays with the same contents are different. Compare contents with sameElements, or convert them to a sequence first (Array(1, 2).toSeq compares by content, as the output shows).

  • The collections have sameElements on sequences and iterators for an explicit element-by-element comparison, regardless of category. Iterable itself has no sameElements since 2.13, because equality is no longer defined at the Iterable level but separately in the Seq, Set and Map branches.

Mutable collections as keys

Equality looks at the current elements, so a mutable collection can be equal to different collections at different times. That is a trap when it is used as a key in a hash map: the entry was stored under the hash code at insertion time, and a later lookup computes a different hash.

//> using scala 3.10.0
import scala.collection.mutable.{ArrayBuffer, HashMap}

@main def run(): Unit =
  val key = ArrayBuffer(1, 2, 3)
  val map = HashMap(key -> "ridge")
  println(map(key))
  key(0) += 1
  println(key)
  println(map.contains(key))
  println(map.get(ArrayBuffer(1, 2, 3)))
  println(map.get(ArrayBuffer(2, 2, 3)))
  println(map.toList)
ridge
ArrayBuffer(2, 2, 3)
false
None
None
List((ArrayBuffer(2, 2, 3),ridge))

Source: Scala Collections (2.13): Equality

After the mutation, map(key) would throw NoSuchElementException (the original guide shows that line), and contains returns false; looking the entry up with a copy of the old contents also fails, because the entry now sits in the bucket of the old hash while its key reports the new one. The entry is not lost (it is still in the map’s iteration), only unreachable by key. The cure is to use an immutable collection (a List, Vector or case class) as the key.

Compile-time checks on ==

Scala 3 refuses to compile == between types that cannot possibly be equal, without any flags.

//> using scala 3.10.0
@main def run(): Unit =
  val a = List(1, 2, 3)
  val b = Set(1, 2, 3)
  println(a == b)
-- [E172] Type Error: ./e1.scala:5:10
5 |  println(a == b)
  |          ^^^^^^
  |   Values of types List[Int] and Set[Int] cannot be compared with == or !=
1 error found

Source: Scala 3 Book: Multiversal Equality

This error (code E172) catches at compile time what compiled in Scala 2 and silently evaluated to false. Note that the check is about the static types: the List and Set in the previous program compare fine as Any. With -language:strictEquality the check becomes an opt-in whitelist (CanEqual), and the library provides CanEqual instances for sequences of comparable element types. The compiler message below is abbreviated.

//> using scala 3.10.0
//> using option -language:strictEquality
@main def run(): Unit =
  println(List(1, 2, 3) == Vector(1, 2, 3))
  println(Set(1) == Set(1))
  println(List(1) == Vector("a"))
  case class Km(v: Double)
  println(List(Km(1)) == List(Km(1)))
-- [E172] Type Error: ./e2.scala:6:10
6 |  println(List(1) == Vector("a"))
  |          ^^^^^^^^^^^^^^^^^^^^^^
  |Values of types List[Int] and Vector[String] cannot be compared with == or !=.
  |I found:
  |    CanEqual.canEqualSeqs[T, U](/* missing */summon[CanEqual[T, U]])
  |But no implicit values were found that match type CanEqual[T, U].
-- [E172] Type Error: ./e2.scala:8:10
8 |  println(List(Km(1)) == List(Km(1)))
  |          ^^^^^^^^^^^^^^^^^^^^^^^^^^
  |   Values of types List[Km] and List[Km] cannot be compared with == or !=.
  |   I found:

Source: Scala 3 Book: Multiversal Equality

The first two comparisons compile (List against Vector of Int, and Set against Set); the third is rejected because Int and String have no CanEqual, and the fourth because the case class Km has no CanEqual instance. See Multiversal Equality for derives CanEqual.

Differences from Java and Kotlin

  • Java: List.equals is defined by the List interface and works across implementations (ArrayList.equals(LinkedList) is true), Set.equals and Map.equals likewise, and a List never equals a Set. This is the same three-category model, with the difference that Java’s Object.equals(Object) accepts anything, so the mismatch shows up at run time as false, while Scala 3 often reports it at compile time. Java arrays compare by reference, like Scala’s. The cost model is also similar but less documented: ArrayList.get is constant and LinkedList.get is linear. See The Collections Framework for the Java side.

  • Kotlin: the same three categories and the same cross-implementation rule for read-only and mutable collections (mutableListOf(1) == listOf(1) is true); arrays need contentEquals. See Collections & Sequences and Equality & Operator Overloading.

  • Neither language publishes a table of per-operation costs for its collections; Scala’s tables are part of the official guide.

Pitfalls

  • Calling xs(i), xs.length, xs.last or xs :+ x in a loop over a List: all linear, so the loop is quadratic. Switch to a Vector, or restructure to traverse once.

  • Treating Vector as free: it is effectively constant, and its constants are higher than List for pure front access.

  • A mutable collection or a class with a mutable hash input as a Map key.

  • Expecting Array(1, 2) == Array(1, 2) to be true. Use sameElements, or ArraySeq / Vector when the data needs value semantics.

  • Comparing a Set with a Seq (always false), or an ordered ListMap with an unordered Map expecting order to matter (it does not for ==).

  • A hand-written hashCode that depends on too few fields, or inconsistently with equals.

Where the books are outdated

  • Scala 2.12-era tables list Stream, the immutable Stack, MutableList and ArrayStack. These no longer exist in 2.13 or Scala 3 (LazyList replaced Stream, and the others were removed). The 2.13 tables above are the ones to use.

  • Older material describes immutable HashSet and HashMap as tries with their own performance notes; since 2.13 they are implemented as CHAMP tries, with the same documented costs.

  • Material from before 2.13 says Iterable defines equality. Since 2.13 it is defined separately in the Seq, Set and Map branches.

  • Older advice to use Stream for lazily growing lists maps to LazyList now; its costs are in the table above.

Scala 3.9 LTS versus 3.10

The tables, the equality model and the library are the same on every Scala 3 release. The equality program above printed identical results on 3.3.8, 3.9.0 and 3.10.0 (the only extra output on 3.3.8 was a JDK warning about sun.misc.Unsafe), and the E172 error for List(1, 2, 3) == Set(1, 2, 3) has the same text on all three.

References