Maps¶

A map is a collection of its entries, each a Tuple2<K, V>. get returns an Option; put and remove return a new map.

Type	Representation	Iteration order	Positional methods
`HashMap`	a compressed hash trie (CHAMP)	not defined	none
`LinkedHashMap`	a hash-based map that also records the insertion order	insertion order	yes
`TreeMap`	a sorted, balanced tree of entries	the key comparator's	yes

The three implement the Map interface, and TreeMap also SortedMap. Both interfaces are sealed: these classes are their only implementations.

HashMap is the structure of the immutable HashMap of the Scala 2.13 collections library, which Scala 3 uses unchanged: a tree of nodes with up to 32 slots each, where five bits of a mix of the key's hash code pick the slot at each level. A node stores its entries inline, keys and values side by side in one array, so an entry costs no object of its own. Removing an entry folds the tree back, so equal maps have the same shape whatever order their entries came in.

When to choose which¶

HashMap by default.
LinkedHashMap when the order the keys were inserted in matters. Overwriting a key keeps its position. A key repeated in of, ofEntries or a collector does the same: it stays where it first appeared, with its last value.
TreeMap for keys in sorted order, or the least and the greatest key.

var stock     = HashMap.of("apple", 3, "pear", 0);
var restocked = stock.put("pear", 5, Integer::sum).put("fig", 1);  // HashMap<String, Integer>
var pears     = restocked.get("pear");                             // Option<Integer>
var kiwis     = restocked.getOrElse("kiwi", 0);                    // Integer
// pears is Some(5), kiwis is 0

var byName = TreeMap.of("b", 2, "a", 1, "c", 3);
var values = byName.values();  // Vector<Integer>
var first  = byName.head();    // Tuple2<String, Integer>
// values is Vector(1, 2, 3), first is (a, 1)

Updating one key¶

updateWith reads a key and writes it in one call. Its function receives the key's value as an Option, None when the key is absent, and returns the new one: Some puts that value, None removes the key.

var stock = HashMap.of("apple", 3, "pear", 1);
var sold  = stock.updateWith("pear", count -> count.map(n -> n - 1).filter(n -> n > 0));
var added = stock.updateWith("fig", count -> Option.some(count.getOrElse(0) + 4));
// sold has no pear left, added has fig -> 4

When nothing changes, the same map comes back: None for an absent key, or Some of the very object the key already holds. On a LinkedHashMap, an updated key keeps its position.

getOrElse also takes a Supplier, for a default that costs something to make. It runs only when the key is absent.

var prices = HashMap.of("apple", 3);
var apple  = prices.getOrElse("apple", () -> lookUpPrice("apple"));  // 3, lookUpPrice is not called
var kiwi   = prices.getOrElse("kiwi", () -> lookUpPrice("kiwi"));    // what lookUpPrice returns

Putting many entries¶

putAll puts every entry of another map, or of any iterable of Tuple2s, as successive puts would. On a key both sides hold, the argument's value wins: this is Scala's ++ on maps.

merge is the other way round: this map's value stays, and only the keys it lacks are added.

var prices  = HashMap.of("apple", 3, "pear", 4);
var updates = HashMap.of("pear", 5, "fig", 2);
var updated = prices.putAll(updates);  // HashMap<String, Integer>
var kept    = prices.merge(updates);   // HashMap<String, Integer>
// updated has pear -> 5, kept has pear -> 4, both have fig -> 2

On a LinkedHashMap, a key already present keeps its position and a new key goes to the end, as with put.

map, filter, partition and forEach take a function of the key and the value. mapValues, filterKeys and similar methods work on one side. keySet() returns the keys as a set, and values() the values as a Vector, in iteration order.

partition splits a map in one pass into two maps of its own kind: the entries that pass the test, and the others.

var stock = HashMap.of("apple", 3, "pear", 0, "fig", 7);
var split = stock.partition((fruit, count) -> count > 0);
// split._1() has apple and fig, split._2() has pear

Ranges¶

A TreeMap cuts out the entries whose keys lie between two bounds. The bounds need not be keys.

rangeFrom(from) keeps the keys at or after from.
rangeUntil(until) keeps those before until, and rangeTo(to) those at or before to.
rangeFromUntil(from, until) keeps those at or after from and before until. It is empty when from is not before until; for from after until, java.util.TreeMap.subMap throws instead.

Each result is a TreeMap with the same comparator, built in O(log n): it shares the rest of the tree with the map it came from, and is that map itself when nothing is cut.

minAfter(key) is the entry with the least key at or after key, and maxBefore(key) the one with the greatest key strictly before it, both as an Option of a Tuple2. iteratorFrom(start) walks the entries from start on.

var events  = TreeMap.of(9, "standup", 12, "lunch", 15, "review", 18, "gym");
var workday = events.rangeFromUntil(9, 18);  // TreeMap<Integer, String>
var next    = events.minAfter(13);           // Option<Tuple2<Integer, String>>
var last    = events.maxBefore(12);          // Option<Tuple2<Integer, String>>
// workday holds 9, 12 and 15, next is Some((15, review)), last is Some((9, standup))

Costs¶

HashMapLinkedHashMapTreeMap

Operation	Cost	Note
`get`	effectively O(1)	effectively O(1): one hash lookup.
`containsKey`	effectively O(1)	effectively O(1): one hash lookup.
`put`	effectively O(1)	effectively O(1): one lookup and one put.
`putAll`	O(n + m)	O(n + m) for a HashMap of m entries (or the asJava view of one): the two maps are merged part by part, and a part only one of them holds is shared without being walked. For other entries, O(m): one effectively O(1) put each. O(1) when either map is empty.
`remove`	effectively O(1)	effectively O(1): one hash lookup, then a copy of a few small arrays; the rest is shared with this map.
`updateWith`	effectively O(1)	effectively O(1): one hash lookup, then at most one put or remove.
`keySet`	O(n)	O(n), with no hashing and no key comparison: the keys are copied from the trie of the entries, in the same shape.
`values`	O(n)	O(n): the values are copied into a new Vector.

Operation	Cost	Note
`get`	effectively O(1)	effectively O(1): one hash lookup.
`containsKey`	effectively O(1)	effectively O(1): one hash lookup.
`put`	effectively O(1)	effectively O(1): one lookup and one put.
`putAll`	O(m)	O(m) for m entries, one effectively O(1) put each. When this map is empty, the entries are built into a new map as ofEntries does, and a LinkedHashMap is returned as is.
`remove`	effectively O(1)	effectively O(1): one hash removal, and the key taken out of the insertion order on the path from its root, on any version of the map.
`updateWith`	effectively O(1)	effectively O(1): one hash lookup, then at most one put or one remove.
`keySet`	O(1)	O(1): a LinkedHashSet view that shares this map; nothing is copied.
`values`	O(n)	O(n): the values are copied into a new Vector.
`head`	effectively O(1)	effectively O(1): the first key of the insertion order, found from its root, then one hash lookup.
`take`	O(min(k, n - k))	O(min(k, n - k)) for k kept entries: the smaller side, kept or dropped, is added to or taken out of a hash map, and the rest is shared; the insertion order is cut along the paths from its root to the cut.
`drop`	O(min(k, n - k))	O(min(k, n - k)) for k dropped entries, as take.

Operation	Cost	Note
`get`	O(log n)	O(log n): one walk down the tree, comparing keys with the comparator.
`containsKey`	O(log n)	O(log n): one walk down the tree, comparing keys with the comparator.
`put`	O(log n)	O(log n): one lookup, then one insertion.
`putAll`	O(m log(n + m))	O(m log(n + m)) for m entries, one insertion each. When entries is a TreeMap with an equal comparator (for a lambda, the same object), the cost is O(m log(n / m + 1)), m then being the smaller of the two sizes: the two trees are cut and joined, not rebuilt. O(1) when entries is an empty map.
`remove`	O(log n)	O(log n): one walk down the tree, then one deletion on the way back up when the key is present.
`updateWith`	O(log n)	O(log n): one lookup, then at most one insertion or deletion.
`keySet`	O(n)	O(n), with no comparison: the keys are copied from the tree of the entries, in the same shape.
`values`	O(n)	O(n): one walk in key order, the values copied into a Vector.
`head`	O(log n)	O(log n): the entry with the smallest key is found by walking down the tree, with no comparison.
`take`	O(log n)	O(log n): the tree is cut at that position without visiting the entries, and the result shares the rest of the tree.
`drop`	O(log n)	O(log n): the tree is cut at that position without visiting the entries, and the result shares the rest of the tree.

Every method: complexity page.

When nothing changes¶

An operation that changes nothing returns the map itself, not a copy: no allocation, and == tells you nothing changed.

put of the key and the value already there, the same objects. An equal key or value that is another object replaces the one there, so that put returns a new map.
remove of an absent key, removeAll of absent keys, and merge with keys this map already has.
putAll of the map itself, of a HashMap whose entries are all keys and values already there (one made from this map by removals, say), or of entries given one by one that are the keys and values already there. putAll of this map with one value replaced returns its argument, to which this map adds nothing.
The filters (filter, filterKeys, filterValues and their reject forms) and retainAll that keep every entry; partition returns the map as the side that gets everything. retainAll keeps the map's own keys and values, not the equal ones it is given.
mapValues and replaceAll whose function returns every value itself.
replace(entry, newEntry) whose new key and value are the objects already there for the key of entry. An equal key or value that is another object replaces the one there.
take and drop of a LinkedHashMap or TreeMap, and the ranges of a TreeMap, that cut nothing.
putAll or merge on an empty map returns the argument when it is a map of the same kind.

When something changes, the parts of the tree or trie that do not are shared, not copied: putAll of a map of the same kind shares the parts either map leaves as they are, and partition of a HashMap gives each side the parts whose entries all go to it.

Equality¶

Two maps are equal when they hold the same entries, keys and values compared with their own equals. The kind does not matter: a HashMap, a LinkedHashMap and a TreeMap of the same entries are all equal, whatever the key comparator of the TreeMap. a.equals(b) and b.equals(a) always agree, and equal maps have the same hashCode.

A TreeMap's comparator decides the lookups: get, containsKey, put, remove and the bulk operations. Equality is the one place where it does not. With a case-insensitive comparator, get("A") finds the value of the key "a", and the map equals a map whose key is "a", not one whose key is "A".

Sharp edges¶

Do not rely on the iteration order of a HashMap: it depends on the hashes and may change between versions.
asJava() on a map is a java.util.Collection of its Tuple2 entries; the java.util.Map view is asJavaMap() (Java interop).
Neither keys nor values can be null. A function or a supplier that returns null fails with a NullPointerException naming the method.
With two getOrElse overloads, a null default needs a cast to the value type: getOrElse(key, (Integer) null). Without it, getOrElse(key, null) does not compile on most maps, and on a Map<K, Object> it picks the Supplier overload and throws supplier is null, even when the key is present. On a Map<K, Object>, a Supplier passed as the default is called, not returned.
groupMap groups what its function returns for each entry in a Vector, in the map's iteration order, as values() does; groupBy groups whole entries in maps of the same type.