Scala Collections Series, Part 2 - More Fundamental Structures

May 26, 2017

This blog post is the middle of a three part series, this section covers:

Sets
Maps (HashMap and TreeMap)
Array and List Buffers
Queues and Stacks

For performance characteristics of the various data structures listed below, please see: Performance Characteristics

Sets

Sets in Scala are relatively straightforward. There are few interesting bits of trivia around Sets which will be covered in the trivia section. For now, here are a number of examples of their use:

scala> val makes = Set("Ford", "Toyota", "Mazda", "Chevy", "Tesla", "Volkswagen")
makes: scala.collection.immutable.Set[String] = Set(Toyota, Tesla, Chevy, Mazda, Volkswagen, Ford)

scala> makes ++ Set("Ferrari")
res0: scala.collection.immutable.Set[String] = Set(Toyota, Tesla, Chevy, Mazda, Volkswagen, Ferrari, Ford)

scala> Set("Ford", "Volkswagen") subsetOf makes
res1: Boolean = true

scala> makes -- Set("Volkswagen", "Tesla")
res2: scala.collection.immutable.Set[String] = Set(Toyota, Chevy, Mazda, Ford)

scala> makes union Set("Volkswagen", "Ferrari")
res3: scala.collection.immutable.Set[String] = Set(Toyota, Tesla, Chevy, Mazda, Volkswagen, Ferrari, Ford)

scala> makes diff Set("Volkswagen", "Ferrari")
res4: scala.collection.immutable.Set[String] = Set(Toyota, Tesla, Chevy, Mazda, Ford)

Sorted Sets (TreeSet uses a RB-Tree implementation):

scala> val emptyTreeSet = collection.immutable.TreeSet.empty[String]
res8: scala.collection.immutable.TreeSet[String] = TreeSet()

scala> emptyTreeSet ++ makes
res9: scala.collection.immutable.TreeSet[String] = TreeSet(Chevy, Ford, Mazda, Tesla, Toyota, Volkswagen)

scala> emptyTreeSet ++ makes range ("Chevy", "Tesla")
res10: scala.collection.immutable.TreeSet[String] = TreeSet(Chevy, Ford, Mazda)

scala> emptyTreeSet ++ makes from "Tesla"
res11: scala.collection.immutable.TreeSet[String] = TreeSet(Tesla, Toyota, Volkswagen)

Maps (HashMap and TreeMap)

Scala provides both mutable and immutable Maps.

Immutable HashMaps are implemented using a hash trie with specialized representations for smaller maps, which we’ll go over in trivia. Immutable TreeMaps are implemented using RB-trees.

scala> val aMap = Map("Chevy" -> Set("Camaro", "Corvette"), "Ford" -> Set("Mustang", "Fusion"))
aTreeMap: scala.collection.immutable.Map[String,scala.collection.immutable.Set[String]] = Map(Chevy -> Set(Camaro, Corvette), Ford -> Set(Mustang, Fusion))

scala> val aTreeMap = scala.collection.immutable.TreeMap("Chevy" -> Set("Camaro", "Corvette"), "Ford" -> Set("Mustang", "Fusion"))
aTreeMap: scala.collection.immutable.TreeMap[String,scala.collection.immutable.Set[String]] = Map(Chevy -> Set(Camaro, Corvette), Ford -> Set(Mustang, Fusion))

scala> aMap("Chevy")
res1: scala.collection.immutable.Set[String] = Set(Camaro, Corvette)

scala> aMap.getOrElse("Tesla", Set("Model S"))
res2: scala.collection.immutable.Set[String] = Set(Model S)

scala> aMap.isDefinedAt("Toyota")
res3: Boolean = false

scala> aMap - "Ford" ++ Map("Tesla" -> Set("Model S"))
res6: scala.collection.immutable.Map[String,scala.collection.immutable.Set[String]] = Map(Chevy -> Set(Camaro, Corvette), Tesla -> Set(Model S))

scala> aMap.keys
res8: Iterable[String] = Set(Chevy, Ford)

scala> aMap.values
res9: Iterable[scala.collection.immutable.Set[String]] = MapLike(Set(Camaro, Corvette), Set(Mustang, Fusion))

scala> aMap.values.flatten
res10: Iterable[String] = List(Camaro, Corvette, Mustang, Fusion)

Array and List Buffers

ArrayBuffer

ArrayBuffer is similar to an Array, but has the advantage of speed due to mutability. It simply modifies the underlying array.

scala> val anArrayBuffer = scala.collection.mutable.ArrayBuffer.empty[Int]
anArrayBuffer: scala.collection.mutable.ArrayBuffer[Int] = ArrayBuffer()

scala> anArrayBuffer += 1
res0: anArrayBuffer.type = ArrayBuffer(1)

scala> anArrayBuffer ++= Array(2,3,4)
res1: anArrayBuffer.type = ArrayBuffer(1, 2, 3, 4)

scala> anArrayBuffer ++= Array(4,4,5,6)
res2: anArrayBuffer.type = ArrayBuffer(1, 2, 3, 4, 4, 4, 5, 6)

scala> anArrayBuffer.toSet
res3: scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 3, 4)

scala> collection.immutable.TreeSet.empty[Int] ++ anArrayBuffer
res4: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 2, 3, 4, 5, 6)

ListBuffer

Surprise! ListBuffer works almost exactly the same way, only it’s backed by a list as opposed to an array. Only caveat is if you want to build a list eventually, use a ListBuffer over an ArrayBuffer.

Queues and Stacks

Both mutable and immutable queues and stacks are available in Scala. Here are some usage examples for queues and stacks:

scala> val queue = new scala.collection.mutable.Queue[Set[String]]
queue: scala.collection.mutable.Queue[Set[String]] = Queue()

scala> queue.enqueue(Set("Model S", "Model X"))

scala> queue.enqueue(Set("Camaro", "Corvette"))

scala> queue.flatten
res21: scala.collection.mutable.Queue[String] = Queue(Model S, Model X, Camaro, Corvette)

scala> queue.dequeue
res22: Set[String] = Set(Model S, Model X)

scala> queue.dequeue
res23: Set[String] = Set(Camaro, Corvette)

scala> val stack = new scala.collection.mutable.Stack[Set[String]]
stack: scala.collection.mutable.Stack[Set[String]] = Stack()

scala> stack.push(Set("Model S", "Model X"))
res11: stack.type = Stack(Set(Model S, Model X))

scala> stack.top
res12: Set[String] = Set(Model S, Model X)

scala> stack.flatten
res13: scala.collection.mutable.Stack[String] = Stack(Model S, Model X)

scala> stack.flatten.filterNot(_ == "Model S")
res14: scala.collection.mutable.Stack[String] = Stack(Model X)

scala> stack.pop()
res15: Set[String] = Set(Model S, Model X)

scala> stack.top
java.util.NoSuchElementException: head of empty list

scala> stack.headOption
res18: Option[Set[String]] = None