# 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 Θ(log2 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>();
...

// 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.
How might we reframe Assassin Manager using the map ADT?

We might prefer using two maps.

1. Let the key be each player’s name and the value be that player’s killer. (Only present if already killed.)
2. Let the key be each player’s name and the value be the person they’re assigned to assassinate next.

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);
}
``````
Explain why there's no method to get the key associated with a given value.

Keys in a map are unique, so there is only one value for each key. However, values are not necessarily unique! For example, there are many letters in the `inventory` with count 1, so it’s impossible to say which key we want in particular.

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

Client

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