Solution: A Set Backed by a Map

Each element of the set is a key of the map. Before we write any code, we have to settle two things: what to store as the value, and how each Set operation maps onto a Map operation.

What to store as the value

A map stores a value with every key, but a set has no values. The obvious choice is to store null as the value, since the value means nothing. That does not work. The Map contract rejects a null value: put throws an IllegalArgumentException.

So we need some non-null value. The set never reads it, so any non-null value works. Here are three options:

Store the item itself as its own value, in a Map<T, T>. This works, but it makes the value look like it carries information when it does not. A reader might wonder why each key is paired with itself.
Store one shared dummy object, in a Map<T, Object>. This works too, but a bare Object does not tell the reader what it is for.
Store true, in a Map<T, Boolean>. The value reads as “this item is present.”

I chose the third option. Java turns the true into a Boolean object automatically, and it reuses one Boolean object for true, so storing it does not create a new object for each element.

We declare the field with the interface type, Map<T, Boolean>, and create the map in the constructor. The code for this problem includes ArrayMap, so I used that. LinkedMap would work the same way. The rest of the class uses only Map operations, so switching to a different map is a one-line change in the constructor.

Mapping each operation

Each Set operation becomes one Map operation:

add(item)       →  map.put(item, true)
remove(item)    →  map.remove(item)
contains(item)  →  map.containsKey(item)
size()          →  map.size()
iterator()      →  map.iterator()

The return values match. put returns true when the key was not already present and false when it was. That is exactly what add must report. When the key is already present, put replaces its value, but the old value is true and the new value is true, so the stored value stays true. Because put already reports whether the key was new, add does not need to call containsKey first. That would search the map twice. remove on the map returns true when it took the key out and false when the key was not there, which is what remove on the set must report.

size returns the map’s size. We do not keep a separate count in the set. The map already counts its keys, and a second count would be one more thing to keep equal to the first.

A Map is Iterable<K> over its keys, and the keys are the set’s elements. So the set’s iterator is the map’s key iterator. It visits every key once and throws NoSuchElementException when next is called after the last key, which is what the set’s iterator must do.

Both contracts reject null with an IllegalArgumentException, so passing a null item to the map would already throw the right exception. We still check for null at the top of each method, so the set’s code states its own contract and does not rely on the map to do it.

public class MapSet<T> implements Set<T> {

  private Map<T, Boolean> map;  // the elements are the keys; every value is true

  public MapSet() {
    map = new ArrayMap<>();
  }

  @Override
  public boolean add(T item) {
    if (item == null) {
      throw new IllegalArgumentException();
    }
    return map.put(item, true);  // put reports whether the key was new
  }

  @Override
  public boolean remove(T item) {
    if (item == null) {
      throw new IllegalArgumentException();
    }
    return map.remove(item);
  }

  @Override
  public boolean contains(T item) {
    if (item == null) {
      throw new IllegalArgumentException();
    }
    return map.containsKey(item);
  }

  @Override
  public int size() {
    return map.size();
  }

  @Override
  public Iterator<T> iterator() {
    return map.iterator();  // the map iterates over its keys, which are the elements
  }
}

Here is a trace of add(4), add(9), add(4). The first two calls each put a new key, so ArrayMap appends an entry and put returns true:

after add(4), add(9)

arr  ┌──────────┬──────────┬───┬───┐
     │ 4 : true │ 9 : true │   │ … │
     └──────────┴──────────┴───┴───┘
size 2

The third call, add(4), finds 4 in the map. put overwrites the value true with true and returns false, so add returns false. The map is unchanged:

after add(4) again

arr  ┌──────────┬──────────┬───┬───┐
     │ 4 : true │ 9 : true │   │ … │
     └──────────┴──────────┴───┴───┘
size 2

Cost

Each set operation does one map operation plus a constant amount of work, so the set costs what the map costs. With ArrayMap, add, remove, and contains are $O (n)$ , because each one searches the map for the key. size is $O (1)$ . Creating an iterator is $O (1)$ , and a full loop over the set is $O (n)$ .

These are the same costs as ArraySet. MapSet uses more memory, though. ArraySet stores each element directly in its array. ArrayMap stores an Entry object for each element, which holds the key and a reference to the shared Boolean. In return, MapSet has no search code of its own. Each method is a few lines that pass the work to the map, and a faster map would make the set faster with no change to the set’s methods.