Scala Set, in depth: the Set contract, immutable and mutable implementations, set algebra, iteration-order and map-deduplication traps, element equality and performance

The contract

A set holds each distinct element at most once, where distinct means not equal according to the element's equals and hashCode, or its Ordering for sorted sets. It answers contains quickly. It makes no promise about iteration order, except for the sorted and insertion-ordered implementations, which promise exactly that. Two sets are equal when they contain the same elements, whatever their implementation. A HashSet and a TreeSet holding 1, 2 and 3 compare equal, while a Set and a List with the same elements do not.

Two more properties shape everyday code. First, a Scala set is also a function from A to Boolean: calling s(x) is s.contains(x), so a set can be passed anywhere a predicate is expected. Second, the default immutable Set is invariant in its element type. A List[Int] can be used as a List[Any], but a Set[Int] cannot be used as a Set[Any]. This is a consequence of the first property, since a function's argument type cannot vary in the covariant direction. When you need the wider type, copy explicitly with toSet[Any].

Building and querying sets

Without an import, Set refers to scala.collection.immutable.Set. Adding or removing an element returns a new set and leaves the original untouched. Unchanged structure is shared between the old and new set, so this is cheap, not a full copy. The symbolic operators have word aliases: + is incl, - is excl, ++ is concat, | is union, & is intersect and &~ is diff.

val admins = Set("ana", "bo")               // immutable.Set[String]
val staff  = admins + "cy" ++ Set("dee", "bo") // new set; "bo" is not duplicated
staff.contains("cy")                        // true, effectively constant time
staff("zed")                                // false: a Set is also a function A => Boolean
List("ana", "zed").filter(staff)            // List(ana): pass the set as a predicate

val engineers = Set("bo", "cy", "eve")
staff | engineers   // union:        ana, bo, cy, dee, eve
staff & engineers   // intersection: bo, cy
staff &~ engineers  // difference:   ana, dee
admins.subsetOf(staff)  // true

import scala.collection.mutable
val seen = mutable.Set.empty[Long]
if (seen.add(42L)) println("first time")    // add returns false when already present

On mutable sets, add returns whether the element was new. That makes a mutable set the idiomatic check-and-insert for de-duplication: one call both tests and records the element. On an immutable set, check contains before calling +, or compare sizes afterwards.

Which implementation you get

Since 2.13, immutable HashSet is a CHAMP trie (compressed hash-array mapped prefix tree). It uses each 5-bit slice of the element's hash to pick one of 32 branches, and stores elements and sub-nodes in compact arrays. A million elements need about four levels, which is why lookups behave like constant time and updates copy only the few nodes on one path.

BitSet uses one bit per possible value up to the largest element present, so memory follows the maximum value rather than the element count. A set holding only the number 10,000,000 uses over a megabyte. Use it for dense small IDs such as enum ordinals or array indices, not for sparse user IDs.

TreeSet needs an implicit Ordering, and that Ordering defines equality for the set. An Ordering that compares only part of an element treats two different elements as duplicates and silently drops one. Mapping a TreeSet needs an Ordering for the result type and returns another sorted set. Without one, 2.13 refuses to compile and suggests calling unsorted first, which gives an ordinary Set.

Worked example: permission checks

Sets are the natural model for permissions: a role grants a set of permissions, a user's effective permissions are the union over their roles minus any explicit denials, and an action is allowed if the permissions it needs are a subset of the effective set.

enum Perm { case Read, Write, Delete, Admin }   // Scala 3; use a sealed trait in Scala 2
import Perm.*

val roleGrants: Map[String, Set[Perm]] = Map(
  "viewer" -> Set(Read),
  "editor" -> Set(Read, Write),
  "owner"  -> Set(Read, Write, Delete),
)

def effective(roles: Set[String], denied: Set[Perm]): Set[Perm] =
  roles.iterator.flatMap(r => roleGrants.getOrElse(r, Set.empty)).toSet &~ denied

def canDo(roles: Set[String], denied: Set[Perm], needed: Set[Perm]): Boolean =
  needed.subsetOf(effective(roles, denied))

val alice = Set("viewer", "editor")
effective(alice, denied = Set.empty)              // Set(Read, Write)
canDo(alice, Set.empty, Set(Read, Write))         // true
canDo(alice, Set(Write), Set(Read, Write))        // false: Write explicitly denied
canDo(alice, Set.empty, Set.empty)                // true: empty set is a subset of everything

Trace alice through it. Her roles map to Set(Read) and Set(Read, Write). Flattening and collecting with toSet gives Set(Read, Write), with Read appearing once. Subtracting a denial of Write leaves Set(Read), and Set(Read, Write) is not a subset of that, so the call returns false. The last line shows an edge case worth deciding on deliberately: an action that needs no permissions is allowed for everyone, because the empty set is a subset of every set. If an empty requirement means someone forgot to configure the action, reject it explicitly.

The traps

Three behaviours surprise almost everyone at least once.

case class User(name: String, age: Int)
val users = Set(User("a", 30), User("b", 30), User("c", 40))

users.map(_.age).sum          // 70, not 100: map on a Set returns a Set, so 30 appears once
users.toList.map(_.age).sum   // 100
users.iterator.map(_.age).sum // 100, and no intermediate collection

(1 to 4).toSet.toList   // List(1, 2, 3, 4): Set1..Set4 keep insertion order
(1 to 5).toSet.toList   // a HashSet: order follows hash bits, not insertion

val s: Set[Int] = Set(1, 2)
// val t: Set[Any] = s    // does not compile: immutable Set is invariant in A
val t: Set[Any] = s.toSet[Any]  // explicit widening at the use site

map removes duplicates. Transforming a Set produces a Set, so equal results collapse into one. Summing the ages of three users gives 70 rather than 100 because two users are 30. Whenever the result of a map is aggregated rather than used as a set, go through toList, a view or an iterator first. The same applies to flatMap and collect.

Order changes at five elements. Set() with up to four elements returns Set1 to Set4, which iterate in insertion order. The fifth element moves the contents into a HashSet, which iterates in hash order. Code that accidentally depends on order passes small tests and fails on real data. If order matters, say so in the type: TreeSet for sorted order, ListSet or mutable.LinkedHashSet for insertion order.

Invariance. A method that takes Set[Animal] will not accept a Set[Dog]. Either make the method generic, as in def feed[A <: Animal](s: Set[A]), or widen at the call site.

Element equality and hashing

A hash set is only as correct as its elements' equals and hashCode. Case classes and immutable values get both for free and are safe. Four kinds of element cause trouble.

• Mutable elements. If a field used in hashCode changes after insertion, the element sits in the bucket for its old hash. contains then returns false for an element the set holds, and you can add a second copy. Never mutate an element while it is in a set; remove it, change it, and add it again.
• Arrays. A Scala Array is a JVM array with reference equality, so Set(Array(1), Array(1)) has two elements. Use Vector or List, or wrap arrays in a type that defines content equality.
• Classes without equals. A plain class compares by reference, so two objects with the same field values are distinct. Make it a case class or define equals and hashCode together.
• Inconsistent Ordering. For TreeSet, compare returning 0 means equal. Compare every field that defines identity.

Concurrency

Immutable sets are safe to share between threads because they never change. To share an evolving set, hold an immutable set in an AtomicReference and update it with updateAndGet, or in an actor's state. Readers then always see a consistent snapshot. mutable.HashSet is not thread-safe, and concurrent adds can corrupt it. The standard library has no concurrent set class. When you need one, use the JDK's ConcurrentHashMap.newKeySet viewed through scala.jdk.CollectionConverters, which gives a mutable.Set backed by a concurrent map. For the concurrent map in the Scala library itself, see TrieMap.

Using a set to drive a graph search

A visited set is the classic use: it prevents a traversal from looping on cycles and from processing a node twice. This breadth-first search is purely functional. The visited set is threaded through the recursion, and the set itself is used as the predicate in filterNot.

import scala.annotation.tailrec
import scala.collection.immutable.Queue

def reachable[A](start: A)(edges: A => Iterable[A]): Set[A] = {
  @tailrec
  def go(frontier: Queue[A], visited: Set[A]): Set[A] =
    frontier.dequeueOption match {
      case None => visited
      case Some((node, rest)) =>
        val fresh = edges(node).iterator.filterNot(visited).toSet  // set used as predicate
        go(rest.enqueueAll(fresh), visited ++ fresh)
    }
  go(Queue(start), Set(start))
}

val graph = Map(1 -> List(2, 3), 2 -> List(4), 3 -> List(4), 4 -> List(1), 5 -> List(6))
reachable(1)(graph.getOrElse(_, Nil))   // Set(1, 2, 3, 4); 5 and 6 are unreachable

The graph has a cycle from 4 back to 1, and the visited set is what stops the search there. Adding fresh nodes to visited when they are enqueued, rather than when they are dequeued, keeps each node in the queue at most once. Node 4 is reached from both 2 and 3 but enqueued once. For graphs with millions of nodes, a local mutable.HashSet is faster and is still safe because it never escapes the function.

Performance guidance

For membership tests on more than a handful of elements, any hash set beats scanning a List or Vector, which is linear. Converting a list to a set costs one pass, so it pays off as soon as you test membership more than a few times. Small immutable sets are cheapest of all, because Set1 to Set4 avoid the trie entirely. Boxing matters for primitives: a Set[Int] stores boxed integers, so a BitSet or a primitive-specialised library is far smaller for large integer sets. Building a large immutable set one element at a time in a loop allocates a path of nodes per insertion. Prefer building it in one go with toSet or a builder, or accumulate in a local mutable set and convert at the end. More measurements are in Scala collections performance, and the wider library is introduced in Scala collections.

Failure modes

What to do next

1. Search your codebase for map, flatMap and collect called on sets whose results are then summed, counted or averaged, and route them through an iterator.
2. Find places that iterate a Set and depend on order, such as rendering, serialisation or tests, and switch to TreeSet or LinkedHashSet.
3. Check that every type used as a set element is immutable with value equality, and that every TreeSet Ordering compares all identity fields.
4. Replace repeated contains calls on Lists and Vectors with a set built once.
5. Use a BitSet for dense small integer domains and a HashSet for sparse ones.
6. For shared evolving sets, use an immutable set in an AtomicReference or ConcurrentHashMap.newKeySet, never a shared mutable.HashSet.
7. Compare with Java's sets in the Java Collections Framework if you work across both languages.