Scala - Collections Overview (Mutable vs Immutable)
• Scala provides two parallel collection hierarchies—immutable collections in `scala.collection.immutable` (default) and mutable collections in `scala.collection.mutable`—with immutable collections...
Key Insights
• Scala provides two parallel collection hierarchies—immutable collections in scala.collection.immutable (default) and mutable collections in scala.collection.mutable—with immutable collections preferred for thread-safety and functional programming paradigms.
• The performance characteristics differ significantly: immutable collections use structural sharing for memory efficiency but require copying for modifications, while mutable collections allow in-place updates with O(1) operations but sacrifice thread-safety.
• Understanding when to use each type depends on your use case—immutable for concurrent access and functional transformations, mutable for performance-critical sequential operations with frequent updates.
The Two Collection Hierarchies
Scala’s standard library defaults to immutable collections. When you import scala.collection._ or use collections without explicit imports, you’re working with immutable versions. This design choice reflects Scala’s functional programming roots and emphasis on thread-safety.
import scala.collection.mutable
// Immutable by default
val immutableList = List(1, 2, 3)
val immutableSet = Set("a", "b", "c")
val immutableMap = Map("key1" -> "value1", "key2" -> "value2")
// Mutable requires explicit import and instantiation
val mutableList = mutable.ListBuffer(1, 2, 3)
val mutableSet = mutable.Set("a", "b", "c")
val mutableMap = mutable.Map("key1" -> "value1", "key2" -> "value2")
The immutable collections share a common trait hierarchy: Iterable, Seq, Set, and Map all have immutable implementations. Mutable collections mirror this structure but add mutation methods.
Immutable Collections: Operations and Performance
Immutable collections create new instances on modification. This sounds expensive, but Scala uses structural sharing to minimize copying.
val original = List(1, 2, 3, 4, 5)
val prepended = 0 :: original // O(1) - shares structure
val appended = original :+ 6 // O(n) - must copy
// Vector provides better append performance
val vec = Vector(1, 2, 3, 4, 5)
val vecPrepended = 0 +: vec // O(log n)
val vecAppended = vec :+ 6 // O(log n)
// Map operations
val scores = Map("Alice" -> 95, "Bob" -> 87)
val updated = scores + ("Charlie" -> 92) // New map
val removed = scores - "Bob" // New map
println(scores) // Map(Alice -> 95, Bob -> 87)
println(updated) // Map(Alice -> 95, Bob -> 87, Charlie -> 92)
Key immutable collection types and their characteristics:
List: Singly-linked list. Fast prepend (O(1)), slow append (O(n)). Best for sequential access and recursive algorithms.
Vector: Indexed sequence with balanced tree structure. O(log n) for most operations. Default choice for indexed access.
Set: Hash-based set implementation. O(1) average lookup, add, and remove.
Map: Hash-based map. O(1) average lookup and insertion.
// Chaining transformations efficiently
val numbers = (1 to 1000000).toVector
val result = numbers
.filter(_ % 2 == 0)
.map(_ * 2)
.take(10)
// These operations are lazy when possible and don't create
// intermediate collections unnecessarily with views
val efficientResult = numbers.view
.filter(_ % 2 == 0)
.map(_ * 2)
.take(10)
.toVector
Mutable Collections: In-Place Modifications
Mutable collections provide methods that modify the collection in place, returning Unit or the collection itself for chaining.
import scala.collection.mutable
// ListBuffer - mutable alternative to List
val buffer = mutable.ListBuffer(1, 2, 3)
buffer += 4 // Append, returns buffer
buffer.prepend(0) // Prepend
buffer.insert(2, 99) // Insert at index
buffer.remove(1) // Remove at index
println(buffer) // ListBuffer(0, 2, 99, 3, 4)
// ArrayBuffer - backed by array, resizable
val array = mutable.ArrayBuffer(1, 2, 3)
array += 4
array ++= Seq(5, 6, 7)
array(0) = 99 // Direct index update
println(array) // ArrayBuffer(99, 2, 3, 4, 5, 6, 7)
// Mutable Set
val set = mutable.Set(1, 2, 3)
set += 4 // Returns true if added
set -= 2 // Returns true if removed
set.add(5) // Returns boolean
println(set) // Set(1, 3, 4, 5)
// Mutable Map
val map = mutable.Map("a" -> 1, "b" -> 2)
map("c") = 3 // Add/update
map += ("d" -> 4) // Add
map -= "b" // Remove
map.getOrElseUpdate("e", 5) // Get or insert
println(map) // Map(a -> 1, c -> 3, d -> 4, e -> 5)
Performance Comparison
The choice between mutable and immutable affects performance significantly depending on your access patterns.
import scala.collection.mutable
// Benchmark: Building a large collection
def immutableBuild(n: Int): List[Int] = {
(0 until n).foldLeft(List.empty[Int])((acc, i) => i :: acc)
}
def mutableBuild(n: Int): mutable.ListBuffer[Int] = {
val buffer = mutable.ListBuffer.empty[Int]
(0 until n).foreach(i => buffer += i)
buffer
}
// Immutable List: O(1) prepend but O(n) append
val list = List(1, 2, 3)
val prepend = 0 :: list // Fast
val append = list :+ 4 // Slow
// Mutable ListBuffer: O(1) for both
val listBuffer = mutable.ListBuffer(1, 2, 3)
listBuffer.prepend(0) // Fast
listBuffer.append(4) // Fast
// Random access comparison
val immutableVec = Vector.fill(10000)(0)
val mutableArray = mutable.ArrayBuffer.fill(10000)(0)
// Vector: O(log n) access
immutableVec(5000)
// ArrayBuffer: O(1) access
mutableArray(5000)
Conversion Between Mutable and Immutable
Converting between collection types is straightforward but creates copies.
import scala.collection.mutable
// Immutable to mutable
val immutableList = List(1, 2, 3, 4, 5)
val mutableBuffer = immutableList.to(mutable.ListBuffer)
val mutableSet = immutableList.to(mutable.Set)
// Mutable to immutable
val mutableList = mutable.ListBuffer(1, 2, 3)
val backToImmutable = mutableList.toList
val toVector = mutableList.toVector
val toSet = mutableList.toSet
// Working with Java collections
import scala.jdk.CollectionConverters._
val javaList = new java.util.ArrayList[String]()
javaList.add("a")
javaList.add("b")
val scalaBuffer = javaList.asScala
val scalaImmutable = javaList.asScala.toList
Thread Safety Considerations
Immutable collections are inherently thread-safe because they cannot be modified. Mutable collections require explicit synchronization.
import scala.collection.mutable
import java.util.concurrent.ConcurrentHashMap
// Immutable: thread-safe by design
@volatile var immutableMap = Map("a" -> 1, "b" -> 2)
def updateImmutable(key: String, value: Int): Unit = {
immutableMap = immutableMap + (key -> value) // Atomic reference update
}
// Mutable: requires synchronization
val mutableMap = mutable.Map("a" -> 1, "b" -> 2)
def updateMutable(key: String, value: Int): Unit = {
mutableMap.synchronized {
mutableMap(key) = value
}
}
// For concurrent access, use Java's concurrent collections
val concurrent = new ConcurrentHashMap[String, Int]().asScala
concurrent.put("a", 1)
concurrent.put("b", 2)
Practical Guidelines
Choose immutable collections when:
- Working in multi-threaded environments
- Implementing functional algorithms
- Passing collections across API boundaries
- Default choice unless performance profiling indicates otherwise
// API design with immutable collections
class UserRepository {
private var users: Map[String, User] = Map.empty
def addUser(user: User): Unit = {
users = users + (user.id -> user)
}
def getUsers: Map[String, User] = users // Safe to return
}
Choose mutable collections when:
- Building collections incrementally with many modifications
- Performance-critical code with profiled bottlenecks
- Interfacing with Java libraries expecting mutable structures
- Local scope where mutation is controlled
// Performance-critical parsing
def parseLogFile(lines: Iterator[String]): Seq[LogEntry] = {
val entries = mutable.ArrayBuffer.empty[LogEntry]
for (line <- lines) {
parseLogLine(line).foreach(entries += _)
}
entries.toVector // Return immutable
}
The general pattern: use mutable collections locally for construction, then convert to immutable for storage and return values. This combines the performance benefits of mutable collections with the safety guarantees of immutable ones.