Scala Map, in depth: what Map() builds, safe lookups, updates and merges, iteration order, views, defaults and concurrent maps

What Map is, and what Map(...) builds

Without an import, Map in Scala refers to scala.collection.immutable.Map. It is a trait, so Map("a" -> 1) returns some concrete class chosen by the factory. For up to four entries the library uses small specialised classes, Map1 to Map4, which store keys and values in fields and compare keys linearly; that is faster and smaller than any hash structure at that size. Add a fifth entry and you get an immutable.HashMap, a compressed hash trie with effectively constant-time lookup and updates that share most of their structure with the original.

The other implementations are opt-in. TreeMap keeps keys sorted using an implicit Ordering and supports range queries. VectorMap and ListMap preserve insertion order; ListMap is a linked list with linear lookup and is only sensible for tiny maps, while VectorMap keeps fast lookup. Both are SeqMaps, the 2.13 trait for maps with a defined insertion order. On the mutable side, mutable.HashMap is unordered, mutable.LinkedHashMap remembers insertion order, and concurrent.TrieMap is a lock-free map safe for concurrent use.

Reading: apply, get, getOrElse and withDefault

There are four ways to look up a key, and they differ in what happens when it is missing.

val prices = Map("apple" -> 3, "pear" -> 4)

prices("apple")              // 3
prices("kiwi")               // throws NoSuchElementException: key not found: kiwi
prices.get("kiwi")           // None   - returns Option[Int]
prices.getOrElse("kiwi", 0)  // 0      - default evaluated lazily, only if missing
prices.contains("pear")      // true

val withZero = prices.withDefaultValue(0)
withZero("kiwi")             // 0
withZero.get("kiwi")         // None  - get ignores the default!

Use apply only when a missing key is a programming error you want to fail loudly. Use get when absence is meaningful and you will pattern match or chain with map and fold. Use getOrElse for the common default case; its second argument is by-name, so an expensive default costs nothing when the key exists.

withDefault and withDefaultValue wrap the map so that apply returns a computed value instead of throwing. The default is a property of that wrapper only. get still returns None, and map and other transformations that build a map with a new value type drop it. Treat defaults as a local convenience, not as data carried through a pipeline: a map with a default passed through two transformations quietly becomes a map that throws.

Writing: updated, updatedWith and merging

Immutable maps never change; every update returns a new map that shares most of its structure with the old one, so updates are cheap, not copies.

val stock = Map("apple" -> 10, "pear" -> 5)

stock.updated("kiwi", 7)          // add or replace (same as stock + ("kiwi" -> 7))
stock.removed("pear")             // same as stock - "pear"
stock ++ Map("apple" -> 1)        // right-hand side wins: apple -> 1

// Modify based on the current value; return None to remove the key.
stock.updatedWith("apple") {
  case Some(n) if n > 1 => Some(n - 1)
  case _                => None
}

// Merge two maps, combining values for shared keys instead of overwriting.
def mergeWith[K, V](a: Map[K, V], b: Map[K, V])(f: (V, V) => V): Map[K, V] =
  b.foldLeft(a) { case (acc, (k, v)) =>
    acc.updatedWith(k) {
      case Some(old) => Some(f(old, v))
      case None      => Some(v)
    }
  }

mergeWith(stock, Map("apple" -> 3, "fig" -> 2))(_ + _)
// Map(apple -> 13, pear -> 5, fig -> 2)

The ++ rule matters: when keys collide, the right operand wins silently. If losing a value would be a bug, merge with an explicit combining function like mergeWith, which makes the policy visible in code. updatedWith, added in 2.13, replaces the read-then-write pattern of get followed by updated with one call that reads clearly.

Building maps from data

Most maps are built from sequences. toMap on a sequence of pairs is the simplest route, and it has the same silent rule as ++: duplicate keys keep the last value. If duplicates are possible, group first.

case class Sale(region: String, product: String, amount: BigDecimal)

val sales: List[Sale] = loadSales()

// groupBy keeps every element: Map[String, List[Sale]]
val byRegion = sales.groupBy(_.region)

// groupMapReduce groups, maps and reduces in one pass:
// Map[String, BigDecimal] with the total per region
val totals = sales.groupMapReduce(_.region)(_.amount)(_ + _)

// Detect duplicate keys instead of silently dropping them
val pairs = List("a" -> 1, "b" -> 2, "a" -> 3)
val dups  = pairs.groupMap(_._1)(_._2).filter(_._2.size > 1)   // Map(a -> List(1, 3))

groupMapReduce avoids building the intermediate lists that groupBy(...).map(...) would create, which matters for large inputs. The fold and reduce patterns behind it are explained in fold, map and filter in Scala.

Iteration order: why tests pass with four keys and fail with five

An immutable.HashMap iterates in an order determined by key hashes, which has nothing to do with insertion order. The small Map1 to Map4 classes, however, iterate in the order entries were added. So a test that builds a map of three entries and asserts on map.keys.toList or on a rendered JSON string passes; in production the map has twenty entries and the order changes. The bug is not in the library; the test relied on an order the type never promised.

val small = Map("c" -> 3, "a" -> 1, "b" -> 2)
small.keys.toList            // List(c, a, b) - insertion order, by accident of Map3

val large = small ++ Map("d" -> 4, "e" -> 5)
large.keys.toList            // hash order: do not depend on it

// Say what you mean:
import scala.collection.immutable.{TreeMap, VectorMap}
TreeMap.from(large).keys.toList      // List(a, b, c, d, e) - sorted
VectorMap("c" -> 3, "a" -> 1)        // keeps insertion order at any size
large.toList.sortBy(_._1)            // sort at the boundary when rendering

The rule: if order matters, encode it in the type with TreeMap or VectorMap, or sort at the point of output. Comparing maps for equality is safe regardless of order, because Map equality compares key-value pairs, not sequence.

Views: mapValues and filterKeys in 2.13

Before 2.13, mapValues returned a lazy wrapper that reran the function on every access, a famous source of repeated side effects and slow loops. In 2.13 mapValues and filterKeys on a Map are deprecated and the operations moved to MapView, so the laziness is visible in the type.

val raw = Map("a" -> "1", "b" -> "2")

// Lazy: parse runs every time a value is read
val view: scala.collection.MapView[String, Int] = raw.view.mapValues(_.toInt)

// Strict: parse runs once per entry, result is an ordinary Map
val parsed: Map[String, Int] = raw.view.mapValues(_.toInt).toMap
// or, without the view
val parsed2 = raw.map { case (k, v) => k -> v.toInt }

Use a view when you will read a few entries of a large map once, and materialise with toMap otherwise. If a function passed to a view has side effects, such as logging or calling a service, materialise immediately.

Mutable and concurrent maps

Mutable maps are fine as local, single-threaded accumulators. getOrElseUpdate is the idiomatic way to memoise or to build multimaps in place, and updateWith is the mutable counterpart of updatedWith.

import scala.collection.mutable
import scala.collection.concurrent.TrieMap

val index = mutable.HashMap.empty[String, mutable.ArrayBuffer[Int]]
for ((word, line) <- words) index.getOrElseUpdate(word, mutable.ArrayBuffer.empty) += line
val frozen: Map[String, Seq[Int]] = index.view.mapValues(_.toSeq).toMap   // publish immutable

val cache = TrieMap.empty[String, Price]
cache.putIfAbsent(sku, price)        // atomic
cache.updateWith(sku) {              // atomic read-modify-write
  case Some(p) => Some(p.copy(amount = p.amount * 0.9))
  case None    => None
}
val snap = cache.snapshot()          // consistent copy, constant time

Never share a mutable.HashMap between threads without a lock: concurrent writes can corrupt it, and readers can see half-done updates. For shared state, prefer an immutable map in an atomic reference (or a Ref in an effect system), which gives readers a consistent snapshot for free, or use TrieMap or Java's ConcurrentHashMap through asScala when write contention is high. With any concurrent map, keep the value computation in getOrElseUpdate side-effect free, because in a concurrent setting it may run even when another thread's value ends up stored.

Keys: what makes a good key

A map is only as correct as its keys' equals and hashCode. Strings, numbers and case classes of immutable fields make good keys because their equality is structural and stable. Three kinds of key cause trouble. Mutable objects: if a key's fields change after insertion, its hash changes and the entry becomes unreachable. Arrays: they use reference equality, so two arrays with the same contents are different keys; convert them to Vector or ArraySeq first. Floating-point numbers: 0.1 + 0.2 is not 0.3, so computed doubles make unreliable keys; round to a fixed precision or use BigDecimal.

Worked example: reconciling inventory feeds

A warehouse service receives stock counts from two feeds, the shop floor and returns processing, each as a list of records. It must produce one map of SKU to quantity, flag SKUs reported twice in one feed as data errors, drop SKUs whose total is zero, and emit a report sorted by SKU.

final case class Count(sku: String, qty: Int)

def reconcile(floor: List[Count], returns: List[Count]): (Map[String, Int], Set[String]) = {
  def dupes(feed: List[Count]): Set[String] =
    feed.groupMapReduce(_.sku)(_ => 1)(_ + _).collect { case (k, n) if n > 1 => k }.toSet

  val errors = dupes(floor) ++ dupes(returns)

  val totals = (floor ++ returns)
    .filterNot(c => errors(c.sku))
    .groupMapReduce(_.sku)(_.qty)(_ + _)
    .filter { case (_, q) => q != 0 }

  (totals, errors)
}

val (totals, errors) = reconcile(floorFeed, returnsFeed)
val report = scala.collection.immutable.TreeMap.from(totals)
  .map { case (sku, q) => f"$sku%-12s $q%6d" }
  .mkString("\n")

Each step uses the matching tool: groupMapReduce for counting and summing in one pass, an explicit duplicate check rather than trusting toMap, a strict filter on the result, and TreeMap only at the output boundary where order matters. Nothing here mutates shared state, so the function is trivial to test with small literal maps, and those tests stay valid at any size because none of them depends on hash order.

Performance and trade-offs

For lookups and updates, immutable.HashMap and mutable.HashMap are both effectively constant time; the mutable version has lower constants and less allocation, the immutable one gives safe sharing and cheap snapshots. TreeMap is logarithmic but buys ordering and range queries. VectorMap costs some memory to remember order. ListMap is linear and rarely the right choice. Measured differences depend on key type and size, so benchmark before switching; Scala collections performance covers how to measure properly. The usual winning pattern is to build with a local mutable map or a builder inside a function, then publish an immutable map.

What to do next

1. Search your code for map(key) lookups on data from outside and replace them with get or getOrElse unless failure is intended.
2. Find tests that assert on map iteration order; switch to equality checks, sorted output, TreeMap or VectorMap.
3. Replace deprecated mapValues and filterKeys calls with .view.mapValues(...).toMap or a strict map.
4. Wherever two maps are combined with ++ or a list becomes toMap, decide whether silent last-wins is acceptable; if not, merge with an explicit function or detect duplicates.
5. Audit shared mutable maps; replace them with an immutable map in an atomic reference, TrieMap or ConcurrentHashMap.
6. Check map keys for arrays, mutable objects and computed doubles.