Maps

ed Lesson

Table of contents

• Sets
• Maps

Sets

A while ago, we learned about sets, an abstract data type representing a collection of unique values. Sets can optimize for the add, remove, and contains operations.

In Java, sets are represented by the Set interface. Java also provides two common implementations of the Set interface.

TreeSet

Elements are stored in sorted order. In the worst case, the runtime of TreeSet operations are all in Θ(log₂ N) with respect to the N, the size of the TreeSet. In later lessons, we’ll learn about binary search trees, the foundational idea underlying TreeSet and its logarithmic runtimes.

HashSet

Elements are stored in a consistent but unpredictable order. For our purposes, the worst case runtime of HashSet operations all have a constant order of growth with respect to the size of the HashSet. In other words, HashSet operations are (for our purposes) as fast as a single array access, arithmetic operation, assignment statement, etc.

HashSet is faster than TreeSet, but TreeSet has the advantage of maintaining items in sorted order, which can be helpful if we want to iterate over the elements in order from least to greatest with a for-each loop or iterator. For example, a TreeSet<String> will iterate over its strings in dictionary order.

Client

List<String> list = new ArrayList<String>();
list.add("hi");
list.add("hello");
...

// Empty TreeSet
Set<String> set = new TreeSet<String>();
// Create a new TreeSet with all of the values in the list
set = new TreeSet<String>(list);
// Create a new HashSet with all of the values in the list
set = new HashSet<String>(list);

It turns out that the ideas behind TreeSet and HashSet can not only be used to implement the set abstract data type, but also another fundamental abstract data type known as a map.

Maps

In programming, we frequently run into a need to associate data with other data. There are many ways to solve this problem.

Letter Inventory

We associated each letter in a given word with the count of its appearances in the word. To solve this problem, we treated each char letter as an index into an array storing the counts of each letter.

Guitar Hero

We associated each key with a pitch value. The position of the key in the KEYBOARD constant could be used to determine the pitch of the key by subtracting 24 from its index.

Assassin Manager

We associated the name of each player with their killer (if they were killed) as well as the person they’re assigned to assassinate next, all stored in an AssassinNode instance.

All of these problems and more can be solved using a map! Maps associate a set of unique keys with a collection of values, where each key is associated with one value. We can reframe each of these problems in terms of key-value entries.

Letter Inventory

Let the key be each char letter and the value be the count of that letter.

Guitar Hero

Let the key be each key in the KEYBOARD and the value be the pitch of that key.

The Java Map interface supports three key operations.

• containsKey(key) returns true if the given key is in the map.
• get(key) the value associated with the given key. Returns null if the key is not in the map.
• put(key, value) an entry for the key–value mapping. (Similar to add in lists and sets.)
• remove(key) the entry for the given key and its mapped value.

Since maps involve both keys and values (which can be different data types), declaring and using a Map is different from using a Set or a List. Say we want to build a letter inventory for the string “Washington” using a TreeMap where the keys are characters and the values are integers.

Client

Map<Character, Integer> inventory = new TreeMap<Character, Integer>();
// Add [aghinnostw] to the empty inventory
inventory.put('a', 1);
inventory.put('g', 1);
inventory.put('h', 1);
inventory.put('i', 1);
inventory.put('n', 2);
inventory.put('o', 1);
inventory.put('s', 1);
inventory.put('t', 1);
inventory.put('w', 1);

To later add the inventory for the string “State”, we can call put again with the same key and the updated value. The new entry will overwrite the old entry for the given key.

Client

// Add [aetts] to the [aghinnostw] inventory
inventory.put('a', inventory.get('a') + 1);
inventory.put('e', 1);
inventory.put('s', inventory.get('s') + 1);
inventory.put('t', inventory.get('t') + 2);

Since maps associate two types of data, the for-each loop is a bit more complicated since we need to specify whether we want to loop over the keySet() or the collection of values().

Client

for (char letter : inventory.keySet()) {
    int count = inventory.get(letter);
    System.out.println(name + ": " + count);
}

Like sets, there also exists a HashMap class that also implements the Map interface.

Client

Map<Character, Integer> inventory = new HashMap<Character, Integer>();