Skip to content

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 hash-based tree 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

When to choose which

  • HashMap by default.
  • LinkedHashMap when the order the keys were inserted in matters. Overwriting a key keeps its position.
  • TreeMap for keys in sorted order, ranges, or the least and the greatest key.
HashMap<String, Integer> stock = HashMap.of("apple", 3, "pear", 0);
HashMap<String, Integer> restocked = stock.put("pear", 5, Integer::sum).put("fig", 1);
Option<Integer> pears = restocked.get("pear");
int kiwis = restocked.getOrElse("kiwi", 0);
// pears is Some(5), kiwis is 0

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

map, filter 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.

Costs

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(Object,).
remove effectively O(1) effectively O(1) (a path copy of the trie).
keySet O(n) O(n) (the keys are copied into a new HashSet).
values O(n) O(n).
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(Object,).
remove effectively O(1) effectively O(1) (one hash removal and one marker in the insertion order), amortised: when the markers outnumber the entries, the insertion order is rebuilt in O(n).
keySet O(1) O(1) (a LinkedHashSet view sharing this map).
values O(n) O(n).
head effectively O(1) effectively O(1) (the first key of the insertion order, then one hash lookup).
take effectively O(min(n, size - n)) effectively O(min(n, size - n)) (the smaller of the kept and the removed keys is inserted into or removed from the hash map; the insertion order is sliced). After removals, finding the cut also walks the insertion order from the nearer end past the removed keys' markers.
drop effectively O(min(n, size - n)) effectively O(min(n, size - n)), that of take(int).
Operation Cost Note
get O(log n) O(log n) comparisons.
containsKey O(log n) O(log n) comparisons.
put O(log n) O(log n) (one lookup and one insertion in the tree).
remove O(log n) O(log n) (one lookup and one deletion in the tree).
keySet O(n log n) O(n log n) (the keys are built into a new TreeSet).
values O(n) O(n).
head O(log n) O(log n) (the leftmost path of the tree).
take O(log n) O(log n) (one rank split of the tree).
drop O(log n) O(log n) (one rank split of the tree).

Every method: complexity page.

Sharp edges

  • Do not rely on the iteration order of a HashMap: it depends on the hashes and may change between versions.
  • LinkedHashMap.remove is amortised: most calls are effectively O(1), and now and then one pays O(n) to clean up the insertion order.
  • 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.