Link Menu Search Expand Document


ed Lesson

Table of contents


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.

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.
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.


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.


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 keyvalue 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.


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.


// 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().


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.


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