Topics in This Chapter A1
A classic programmer’s saying is, “If you can only have one data structure, make it a hash table.” Hash tables—or, more generally, maps—are among the most versatile data structures. As you will see in this chapter, Scala makes it particularly easy to use them.
When looking up a key in a map, there may not be a matching value. An option is perfect for describing that situation. An option is used in Scala whenever a value may be present or absent.
Maps are collections of key/value pairs. Scala has a general notion of tuples—aggregates of n objects, not necessarily of the same type. A pair is simply a tuple with n = 2. Tuples are useful whenever you need to aggregate two or more values together.
Highlights of the chapter are:
Scala has a pleasant syntax for creating, querying, and traversing maps.
You need to choose between mutable and immutable maps.
By default, you get a hash map, but you can also get a tree map.
You can easily convert between Scala and Java maps.
Use the Option
type for values that may or may not be present—it is safer than using null
.
Tuples are useful for aggregating values.
You can construct a map as
val scores = Map("Alice" -> 10, "Bob" -> 3, "Cindy" -> 8)
This constructs an immutable Map[String, Int]
whose contents can’t be changed. See the next section for mutable maps.
If you want to start out with a blank map, you have to supply type parameters:
val scores = scala.collection.mutable.Map[String, Int]()
In Scala, a map is a collection of pairs. A pair is simply a grouping of two values, not necessarily of the same type, such as ("Alice", 10)
.
The ->
operator makes a pair. The value of
"Alice" -> 10
is
("Alice", 10)
You could have equally well defined the map as
Map(("Alice", 10), ("Bob", 3), ("Cindy", 8))
The ->
operator is just a little easier on the eyes than the parentheses. It also supports the intuition that a map data structure is a kind of function that maps keys to values. The difference is that a function computes values, and a map just looks them up.
In Scala, the analogy between functions and maps is particularly close because you use the ()
notation to look up key values.
scores("Bob")
//
Like scores.get("Bob") in Java or scores["Bob"] in JavaScript, Python, or C++
If the map doesn’t contain a value for the requested key, an exception is thrown.
To check whether there is a key with the given value, call the contains
method:
if scores.contains("Donald") then scores("Donald") else 0
Since this call combination is so common, there is a shortcut:
scores.getOrElse("Donald", 0)
//
If the map contains the key "Bob", return the value; otherwise, return 0.
Finally, the call map.get(key)
returns an Option
object that is either Some(value for key)
or None
. We discuss the Option
class in Section 4.7, “The Option Type,” on page 56.
Note
Given an immutable map, you can turn it into a map with a fixed default value for keys that are not present, or a function to compute such values.
val scores2 = scores.withDefaultValue(0)
scores2("Zelda")
//
Yields 0 since "Zelda" is not presentval scores3 = scores.withDefault(_.length)
scores3("Zelda")
//
Yields 5, applying the length function to the key that is not present
In this section, we discuss mutable maps. Here is how to construct one:
val scores = scala.collection.mutable.Map("Alice" -> 10, "Bob" -> 3, "Cindy" -> 8)
In a mutable map, you can update a map value, or add a new one, with a ()
to the left of an =
sign:
scores("Bob") = 10
//
Updates the existing value for the key "Bob" (assuming scores is mutable)scores("Fred") = 7
//
Adds a new key/value pair to scores (assuming it is mutable)
Alternatively, you can use the ++=
operator to add multiple associations:
scores ++= Map("Bob" -> 10, "Fred" -> 7)
To remove a key and its associated value, use the -=
operator:
scores -= "Alice"
You can’t update an immutable map, but you can do something that’s just as useful—obtain a new map that has the desired update:
val someScores = Map("Alice" -> 10, "Bob" -> 3)
val moreScores = someScores + ("Cindy" -> 7) //
Yields a new immutable map
The moreScores
map contains the same associations as someScores
, as well as a new association for the key "Cindy"
.
Instead of saving the result as a new value, you can update a var
:
var currentScores = moreScores
currentScores = currentScores + ("Fred" -> 0)
You can even use the +=
operator:
currentScores += "Donald" -> 5
Similarly, to remove a key from an immutable map, use the -
operator to obtain a new map without the key:
currentScores = currentScores - "Alice"
or
currentScores -= "Alice"
You might think that it is inefficient to keep constructing new maps, but that is not the case. The old and new maps share most of their structure. (This is possible because they are immutable.)
The following amazingly simple loop iterates over all key/value pairs of a map:
for (k, v) <-
mapdo process(k, v)
The magic here is that you can use pattern matching in a Scala for
loop. (Chapter 14 has all the details.) That way, you get the key and value of each pair in the map without tedious method calls.
If for some reason you want to visit only the keys or values, use the keySet
and values
methods. The values
method returns an Iterable
that you can use in a for
loop.
val scores = Map("Alice" -> 10, "Bob" -> 7, "Fred" -> 8, "Cindy" -> 7)
scores.keySet //
Yields a set with elements "Alice", "Bob", "Fred", and "Cindy"for v <- scores.values do println(v) //
Prints 10 7 8 7
Note
For a mutable map, the collections returned by keySet
and values
are “live”—they are updated as the contents of the map changes.
To invert a map—that is, switch keys and values—use
for (k, v) <-
mapyield (v, k)
There are two common implementation strategies for maps: hash tables and binary trees. Hash tables use the hash codes of the keys to scramble entries. Tree maps use the sort order of the keys to build a balanced tree. By default, Scala gives you a map based on a hash table because it is usually more efficient.
Immutable hash maps are traversed in insertion order. This is achieved by additional links in the hash table. For example, when iterating over
Map("Fred" -> 1, "Alice" -> 2, "Bob" -> 3)
the keys are visited in the order "Fred"
, "Alice"
, "Bob"
, no matter what the hash codes of these strings are.
However, in a mutable map, insertion order is not maintained. Iterating over the elements yields them in unpredictable order, depending on the hash codes of the keys.
scala.collection.mutable.Map("Fred" -> 1, "Alice" -> 2, "Bob" -> 3)
//
Printed as HashMap(Fred -> 1, Bob -> 3, Alice -> 2)
If you want to visit the keys in insertion order, use a LinkedHashMap
:
scala.collection.mutable.LinkedHashMap("Fred" -> 1, "Alice" -> 2, "Bob" -> 3)
//
Printed as LinkedHashMap(Fred -> 1, Alice -> 2, Bob -> 3)
To visit the keys in sorted order, use a SortedMap
instead.
scala.collection.SortedMap("Fred" -> 1, "Alice" -> 2, "Bob" -> 3)
scala.collection.mutable.SortedMap("Fred" -> 1, "Alice" -> 2, "Bob" -> 3)
//
Printed as TreeMap(Alice -> 2, Bob -> 3, Fred -> 1)
If you get a Java map from calling a Java method, you may want to convert it to a Scala map so that you can use the pleasant Scala map API.
Simply add an import
statement:
import scala.jdk.CollectionConverters.*
Then use the asScala
method to turn the Java map into a Scala map:
val ids = java.time.ZoneId.SHORT_IDS.asScala
//
Yields a scala.collection.mutable.Map[String, String]
In addition, you can get a conversion from java.util.Properties
to a Map[String, String]
:
val props = System.getProperties.asScala
//
Yields a Map[String, String], not a Map[Object, Object]
Conversely, to pass a Scala map to a method that expects a Java map, provide the opposite conversion. For example:
import java.awt.font.TextAttribute.* //
Import keys for map belowval attrs = Map(FAMILY -> "Serif", SIZE -> 12) //
A Scala mapval font = java.awt.Font(attrs.asJava) //
Expects a Java map
Option
TypeThe Option
class in the standard library expresses values that might or might not be present. The subclass Some
wraps a value. The object None
indicates that there is no value.
var friend: Option[String] = Some("Fred")
friend = None //
No friend
This is less ambiguous than using an empty string and safer than using null
for a missing value.
Option
is a generic type. For example, Some("Fred")
is an Option[String]
.
The get
method of the Map
class returns an Option
. If there is no value for a given key, get
returns None
. Otherwise, it wraps the value inside Some
.
val scores = Map("Alice" -> 10, "Bob" -> 7, "Cindy" -> 8)
val alicesScore = scores.get("Alice") // Some(10)
val dansScore = scores.get("Dan") // None
To find out what is inside an Option
instance, you can use the isEmpty
and get
methods:
if alicesScore.isEmpty
then println("No score")
else println(alicesScore.get)
That’s tedious, though. It is better to use the getOrElse
method:
println(alicesScore.getOrElse("No score"))
If alicesScore
is None
, then getOrElse
returns "No score"
.
Note
The argument of the getOrElse
method is executed lazily. For example, in the call
alicesScore.getOrElse(System.getProperty("DEFAULT_SCORE"))
the call to System.getProperty
only happens when alicesScore
is empty.
This delayed evaluation is achieved with a “by name” parameter. See Chapter 12 for details.
A more powerful way of working with options is to consider them as collections that have zero or one element. You can visit the element with a for
loop:
for score <- alicesScore do println(score)
If alicesScore
is None
, nothing happens. If it is a Some
, then the loop executes once, with score
bound to the contents of the option.
You can also use methods such as map
, filter
, or foreach
. For example,
val biggerScore = alicesScore.map(_ + 1) //
Some(score + 1) or Noneval acceptableScore = alicesScore.filter(_ > 5) //
Some(score) if score > 5 or NonealicesScore.foreach(println) //
Prints the score if it exists
Tip
When you create an Option
from a value that may be null
, simply use Option(value)
. The result is None
if value
is null
and Some(value)
otherwise.
Maps are collections of key/value pairs. Pairs are the simplest case of tuples—aggregates of values of different types.
A tuple value is formed by enclosing individual values in parentheses. For example,
(1, 3.14, "Fred")
is a tuple of type
(Int, Double, String)
If you have a tuple, say,
val t = (1, 3.14, "Fred")
then you can access its components as t(0)
, t(1)
, and t(2)
.
As long as the index value is an integer constant, the types of these expressions are the component types:
val second = t(1) //
second has type Double
Note
Alternatively, you can access components with the methods _1
, _2
, _3
, for example:
val third = t._3 //
Sets third to "Fred"
Note that these component accessors start with _1
. There is no _0
.
If the index is variable, the type of t(n)
is the common supertype of the elements:
var n = 1
val component = t(n) //
component has type Any
Caution
If the tuple index is a val
, you get a complex “match type” that is no more useful than Any
:
val m = 0
val first = t(m) /*
first has typem.type match {
case 0 => Int
case scala.compiletime.ops.int.S[n1] =>
scala.Tuple.Elem[(Double, String), n1]
} */
Often, it is easiest to use the “destructuring” syntax to get at the components of a tuple:
val (first, second, third) = t //
Sets first to 1, second to 3.14, third to "Fred"
You can use an _
if you don’t need all components:
val (first, second, _) = t
You can concatenate tuples with the ++
operator:
("x", 3) ++ ("y", 4) //
Yields ("x", 3, "y", 4)
Tuples are useful for functions that return more than one value. For example, the partition
method of the StringOps
class returns a pair of strings, containing the characters that fulfill a condition and those that don’t:
"New York".partition(_.isUpper) //
Yields the pair ("NY", "ew ork")
Caution
Sometimes, the Scala compiler wants to “help out” to convert between tuples and function argument lists. This can lead to surprises. Here is a typical example:
val destination = "world"
val b = StringBuilder()
b.append("Hello") //
b holds "Hello"b.append(" ", destination) //
Oops, b holds "Hello( ,world)"
There is no append
method with multiple arguments. Therefore, Scala turns the arguments into a tuple and passes that as the single argument of type Any
.
This “auto tupling” behavior can be surprising, and it may be restricted or removed in future versions of Scala.
One reason for using tuples is to bundle together values so that they can be processed together. This is commonly done with the zip
method. For example, the code
val symbols = Array("<", "-", ">")
val counts = Array(2, 10, 2)
val pairs = symbols.zip(counts)
yields an array of pairs
Array(("<", 2), ("-", 10), (">", 2))
The pairs can then be processed together:
for (s, n) <- pairs do print(s * n) //
Prints <<---------->>
Tip
The toMap
method turns a collection of pairs into a map.
If you have a collection of keys and a parallel collection of values, zip them up and turn them into a map like this:
keys.zip(values).toMap
1. Set up a map of prices for a number of gizmos that you covet. Then produce a second map with the same keys and the prices at a 10 percent discount.
2. Write a program that reads words from a file. Use a mutable map to count how often each word appears. To read the words, simply use a java.util.Scanner
:
val in = java.util.Scanner(new java.io.File("myfile.txt"))
while in.hasNext() do
processin.next()
Or look at Chapter 9 for a Scalaesque way.
At the end, print out all words and their counts.
3. Repeat the preceding exercise with an immutable map.
4. Repeat the preceding exercise with a sorted map, so that the words are printed in sorted order.
5. Repeat the preceding exercise with a java.util.TreeMap
that you adapt to the Scala API.
6. Define a linked hash map that maps "Monday"
to java.util.Calendar.MONDAY
, and similarly for the other weekdays. Demonstrate that the elements are visited in insertion order.
7. Print a table of all Java properties reported by the getProperties
method of the java.lang.System
class, like this:
java.runtime.name | Java(TM) SE Runtime Environment
sun.boot.library.path | /home/apps/jdk1.6.0_21/jre/lib/i386
java.vm.version | 17.0-b16
java.vm.vendor | Sun Microsystems Inc.
java.vendor.url | http://java.sun.com/
path.separator | :
java.vm.name | Java HotSpot(TM) Server VM
You need to find the length of the longest key before you can print the table.
8. Write a function minmax(values: Array[Int])
that returns a pair containing the smallest and the largest values in the (nonempty) array.
9. Reimplement the function from the preceding exercise to return an Option
that is None
if the array happens to be empty.
10. Write a program that prompts the user for a first and last letter, then prints a matching word from scala.io.Source.fromFile("/usr/share/dict/words").mkString.split("
")
. Use find
. What alternatives do you have for dealing with the returned Option
?
11. Write a program that demonstrates that the argument of the getOrElse
method in the Option
class is evaluated lazily.
12. Write a function lteqgt(values: Array[Int], v: Int)
that returns a triple containing the counts of values less than v
, equal to v
, and greater than v
.
13. What happens when you zip together two strings, such as "Hello".zip("World")
? Come up with a plausible use case.