Start learning free

LESSON 263 OF 414 · HASH TABLE

Hash Sets in Scala: Set, mutable.Set and LinkedHashSet

Lesson Read the full explanation

A Scala Set stores unique values. If the same value is added more than once, it still appears only once.

Creating a Set:

val mySet = Set("b", "c", "c", "d")

// mySet contains b, c, and d

Checking membership:

val exists = mySet.contains("c") // true

Mutable sets:

val mutableSet = scala.collection.mutable.Set("b", "c", "d")
mutableSet += "x"
mutableSet -= "c"

Iterating:

for (value <- mySet) {
    println(value)
}

Assignment
Follow the Coding Tutorial and let's play with sets.

Hint
Use Set(...) for unique values.

STEP 1 OF 6
    Ctrl + Enter to check

    SCALA · HASH TABLE

    Hash Set in Scala, explained

    What a set is

    A Set is a collection of unique values. Adding a value that is already present changes nothing, so a value is either in the set or not, and it can't appear twice. A hash set stores its values in a hash table, which makes "is this value in the set?" a constant-time operation on average. That fast membership check is the reason to reach for a set: whenever a loop keeps asking "have I seen this before?", a set answers without scanning a list.

    Creating and reading sets

    In Scala, Set(...) builds an immutable set. Duplicates in the arguments collapse into one element:

    val mySet = Set("b", "c", "c", "d")
println(mySet)                 // Set(b, c, d)
println(mySet.contains("c"))   // true
println(mySet.size)            // 3

    Besides contains, you can apply a set to a value like a function: mySet("c") is the same test and returns a Boolean. Two sets are equal when they hold the same elements, whatever the order: Set(1, 2) == Set(2, 1) is true.

    Immutable and mutable sets

    The default Set never changes. The + operator returns a new set and leaves the original untouched:

    val im = Set(1, 2, 3)
println(im + 4)   // Set(1, 2, 3, 4)
println(im)       // Set(1, 2, 3)

    To update a set in place, use the one from scala.collection.mutable. The package name is written out in full because the lesson doesn't import it:

    val mutableSet = scala.collection.mutable.Set("b", "c", "d")
mutableSet += "x"   // adds x
mutableSet -= "c"   // removes c

    The variable is a val, yet the set changes. A val only stops the variable from pointing at another object; the object it points to can still be modified when its type is mutable. += adds an element, -= removes one, and removing a value that isn't there does nothing. The method add also inserts, and returns true if the value was new and false if it was already present.

    Iteration order

    A hash set doesn't promise any particular order when you loop over it. If you want the elements back in the order they were first inserted, use scala.collection.mutable.LinkedHashSet. It is a hash set that also remembers insertion order, so printing or looping over it is predictable:

    val ordered = scala.collection.mutable.LinkedHashSet("b", "a", "b", "c")
println(ordered)   // LinkedHashSet(b, a, c)

    The lesson's exercise, step by step

    The exercise starts with data that contains a duplicate and then exercises each basic set operation:

    1. An array with a duplicate. fruitsArray holds "apples", "bananas" and "apples". It is declared with val and Array(...).
    2. Build the set from the array. The constructor of LinkedHashSet[String] takes the elements as separate arguments, so the array is spread with fruitsArray: _*. The duplicate "apples" disappears, and the order is apples, bananas.
    3. Add a value. fruits += "oranges" inserts it in place. Adding it a second time would have no effect.
    4. Test membership. fruits.contains("apples") is true, so the program prints We have apples.
    5. Remove a value. fruits -= "bananas" takes it out.
    6. Loop over what is left. A for comprehension with a variable fruit prints each remaining element.

    The solution in Scala

    val fruitsArray = Array("apples", "bananas", "apples")

val fruits = scala.collection.mutable.LinkedHashSet[String](fruitsArray: _*)

fruits += "oranges"

if (fruits.contains("apples")) {
    println("We have apples")
}

fruits -= "bananas"

for (fruit <- fruits) {
    println(fruit)
}

    The program prints:

    We have apples
apples
oranges

    The syntax fruitsArray: _* is the older way to pass an array as a sequence of arguments. Scala 3.5 still accepts it but reports a warning and prefers fruitsArray*. Both mean the same.

    Common mistakes

    • Expecting += to change an immutable set. On a val holding an immutable Set, += doesn't compile, because there is no variable to reassign. Use the mutable set, or a var and accept that each addition builds a new set.
    • Relying on order from a plain hash set. The order of Set and mutable.HashSet can differ from the order you inserted. Use LinkedHashSet when the order matters.
    • Counting an array as a set. Array(1, 2) == Array(1, 2) is false, because arrays compare by reference. Sets compare by content.

    Key takeaways

    • A set keeps one copy of each value and answers contains in constant time on average.
    • Set(...) is immutable; scala.collection.mutable.Set changes in place with +=, -= and add.
    • A val can hold a mutable set that still changes.
    • LinkedHashSet adds insertion order to a hash set.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free