This chapter is from the book
This chapter is from the book
This chapter is from the book
4.5 Linked and Sorted Maps
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)