Java collections and generics

ArrayList, HashMap and HashSet are probably the three classes you will use most in your programming life. This session is about choosing between them and using them correctly: we build the same data structure – a bag (multiset) – twice, once on a list and once on a map, and compare what each costs. Along the way we learn to read the angle brackets that fill the JDK documentation: List<T>, <T> before a return type, ? super T.

The one idea to take away: choose the collection by the question your program asks most often. "What is the 3rd one?" is a List. "Is this one in there?" is a Set. "What belongs to this key?" is a Map. Picking the wrong one still works – it just makes every other line harder.

Pick the collection by the question you ask

The Java collections are a small family of interfaces with several implementations each (Fig. 1). The interface says what you can do – a List has positions, a Set has no duplicates, a Map pairs keys with values. The class says how it is stored, and therefore what is fast.

Declare variables, fields and parameters with the interface type, and name the class only after new. Then the rest of the code can only use what the interface promises, and swapping ArrayList for another List is a one-line change.

// The variable has the interface type; only "new" names the class.
// Switching to another List later is a one-line change.
private final List<BagItem> data;

public Bag() {
    this.data = new ArrayList<>();   // diamond: <BagItem> is inferred
}

Generics: the type in angle brackets

Every collection is generic: the type in < > – the type parameter – says what it holds. From then on the compiler checks every use, so a wrong element type is a compile error instead of a crash at runtime, and you never cast what you take out.

List<String> names = new ArrayList<>();
names.add("Anna");             // fine
names.add(42);                 // compile error: only Strings go in
String first = names.get(0);   // no cast: the compiler knows it's a String

You can write generic methods yourself. The numBoth example counts the common elements of two collections of any element type. The <T> before the return type is the declaration of the type variable – just as a variable must be declared before it is used. Collection<T> in the parameter list only uses it (Fig. 2).

A generic class declares its type variable after the class name, and every instance method can use it. ReverseComparator<T> from the sorting example wraps any comparator and reverses it; T is decided when the object is created, new ReverseComparator<String>(…) or with the diamond.

public class ReverseComparator<T> implements Comparator<T> {
    private final Comparator<? super T> original;

    public ReverseComparator(Comparator<? super T> original) {
        this.original = original;
    }

    @Override
    public int compare(T t1, T t2) {
        return original.compare(t2, t1);   // swap, don't negate
    }
}

A bag on an ArrayList

A bag is like a set, except that an element can be in it several times – so for each element we store how many copies there are. Operations: add some copies, remove some or all, ask how many, clear, and the set operations union, intersection and difference.

The first version keeps a List<BagItem>, where a BagItem is a small class holding the element and its count. To find an element we walk the list (Fig. 3).

private BagItem getItem(String item) {
    for (BagItem bi : data) {
        if (bi.getItem().equals(item)) {   // equals, not ==
            return bi;
        }
    }
    return null;                            // not in the bag
}

public void add(String item, int num) {
    Objects.requireNonNull(item, "item must not be null");
    if (num <= 0) {
        throw new IllegalArgumentException("num must be positive: " + num);
    }
    BagItem bi = getItem(item);
    if (bi == null) {
        data.add(new BagItem(item, num));   // new entry
    } else {
        bi.addNum(num);                      // existing entry: only the count grows
    }
}

Two decisions in add are worth copying. The method refuses bad arguments immediately with an exception, so the bag can never get into an invalid state – a negative count, a null element. And it keeps an invariant: an entry with count 0 never stays in the list; remove deletes the entry instead. Every other method can rely on that.

The collections' search methods – contains, indexOf, remove(Object) – all call equals. The version inherited from Object is plain ==, so for your own classes you override it. And whoever overrides equals must override hashCode too: equal objects must have equal hash codes, otherwise HashSet and HashMap look in the wrong bucket and don't find them.

@Override
public boolean equals(Object o) {
    if (this == o) {
        return true;
    }
    if (!(o instanceof BagItem)) {       // also false for null
        return false;
    }
    BagItem other = (BagItem) o;
    return Objects.equals(item, other.item) && num == other.num;
}

@Override
public int hashCode() {                  // equal objects – equal hash codes
    return Objects.hash(item, num);
}

The same bag on a HashMap

The bag really is a mapping from element to count, so a Map<String, Integer> fits it exactly – no BagItem class needed. More importantly, the lookup is no longer a walk: the key's hash code points at one bucket, and only the few entries in it are compared (Fig. 4).

private final Map<String, Integer> data = new HashMap<>();

public void add(String item, int num) {
    // put overwrites the old value, so compute the new count first
    data.put(item, howMany(item) + num);
    // the same in one call: data.merge(item, num, Integer::sum);
}

public int howMany(String item) {
    return data.getOrDefault(item, 0);   // get would return null for a missing key
}

put overwrites the value of an existing key – the map can't know you meant "add to it". So we compute the new count first, or let merge do it in one call. To walk a map, iterate over entrySet(), which gives you key and value together; walking keySet() and calling get for every key does each lookup twice.

Union, intersection, difference

On bags the set operations work element by element on the counts (Fig. 5): the union adds them, the intersection takes the smaller one, the difference subtracts – and whatever drops to zero or below is left out.

public Bag union(Bag other) {
    Bag result = new Bag();
    for (Map.Entry<String, Integer> entry : other.data.entrySet()) {
        result.add(entry.getKey(), entry.getValue());
    }
    for (Map.Entry<String, Integer> entry : data.entrySet()) {
        result.add(entry.getKey(), entry.getValue());
    }
    return result;
}

Notice that union reads other.data although data is private. Visibility in Java is per class, not per object: a Bag may see the private fields of another Bag. And the result is built through add, so it gets the validation and the zero-count invariant for free. Intersection and difference are your first tasks below.

Bulk operations instead of loops

Collections have operations that work on a whole collection at once: addAll (union), retainAll (intersection), removeAll (difference), containsAll. The numBoth example uses them to count the common elements of two collections without writing a single loop – the loops still run, inside the library (Fig. 6).

public static <T> int numBoth(Collection<T> c1, Collection<T> c2) {
    Set<T> common = new HashSet<>(c1);   // copy: duplicates drop out
    Set<T> s2 = new HashSet<>(c2);       // fast contains() for retainAll
    common.retainAll(s2);                // intersection, in place on the copy
    return common.size();
}

Sorting with a Comparator

Some classes have a natural order: they implement Comparable and compare themselves – numbers by size, Strings alphabetically. For every other order you hand the sort a Comparator: an object with one method, compare(a, b), that returns a negative number if a comes first, zero if they are equal, positive if b comes first. The sort algorithm itself knows nothing about your order – it only keeps asking (Fig. 7).

// Natural order: the class compares itself (String, Integer implement Comparable)
Collections.sort(words);

// Any other order: pass a Comparator
words.sort(String.CASE_INSENSITIVE_ORDER);
creatures.sort(Comparator.comparingInt(Creature::getDistance).reversed());

The Sort1 example sorts integers by their remainder modulo n, ascending or descending:

public class RemainderComparator implements Comparator<Integer> {
    private final int n;
    private final boolean ascending;

    @Override
    public int compare(Integer i1, Integer i2) {
        int r1 = Math.floorMod(i1, n);   // 0..n-1 even for negative numbers
        int r2 = Math.floorMod(i2, n);
        return ascending ? Integer.compare(r1, r2) : Integer.compare(r2, r1);
    }
}

Three details in this small class are worth knowing. Math.floorMod instead of %, because % keeps the sign (-1 % 3 == -1), while the mathematical remainder is always between 0 and n-1. Integer.compare(r1, r2) instead of the tempting r1 - r2, which overflows for large numbers of opposite sign. And descending order by swapping the two arguments – negating the result fails for Integer.MIN_VALUE, whose negation is itself.

public static List<Integer> getSortedByNRemainder(List<Integer> list, int n) {
    return getSortedByNRemainder(list, n, true);   // the "default argument"
}

public static List<Integer> getSortedByNRemainder(List<Integer> list, int n, boolean ascending) {
    List<Integer> listCopy = new ArrayList<>(list);   // the caller's list stays as it was
    listCopy.sort(new RemainderComparator(n, ascending));
    return listCopy;
}

The function sorts a copy, so the caller's list is not touched – the signature returns a list, and a reader expects a function that returns something to leave its input alone. Java has no default parameter values; the usual substitute is an overload with fewer parameters that calls the full version, so the logic stays in one place.

Reading ? super T and ? extends T

The Sort2 example has this signature, and the JDK documentation is full of similar ones:

public static <T> void sort(List<T> list, int i, int j, Comparator<? super T> comparator)

? is a wildcard – "some type I don't name" – and super T restricts it to T or a supertype of T. Together: a comparator that can compare Ts, or something more general. If we sort a List<Integer> (so T = Integer, whose supertypes are Number and Object):

Why not simply Comparator<T>? Because inheritance does not carry over to type parameters: Integer is a Number, but a List<Integer> is not a List<Number>. Surprising at first, but necessary:

List<Integer> ints = new ArrayList<>();
List<Number> nums = ints;   // compile error – luckily, because otherwise...
nums.add(3.14);             // ...a double would end up in the list of ints

The wildcards loosen this rigidity exactly where it is safe. The rule of thumb: something you take Ts out of (a source) is ? extends T; something you give Ts to (a consumer) is ? super T. A comparator receives two Ts, so it is a consumer.

// Collections.sort: T must be able to compare itself with a T (or a supertype of T)
static <T extends Comparable<? super T>> void sort(List<T> list)

// ArrayList copy constructor: takes anything whose elements ARE E's
public ArrayList(Collection<? extends E> c)

<T extends Comparable<? super T>> is a bounded type variable: T can't be anything, only a type that can compare itself to another T. That is why this version of sort needs no comparator.

Views: subList and keySet

Some methods don't return a new collection but a view of an existing one. list.subList(from, to) is a window on a slice of the list (from inclusive, to exclusive): sort the view and you have sorted that slice of the original. The Sort2 example uses exactly that to sort three slices of one list in place (Fig. 8).

keySet(), values() and entrySet() of a map are views too: removing a key from the key set removes the entry from the map. That is useful inside a class – and dangerous when a getter hands a view out.

public List<String> items() {
    // keySet() is a view: removing from it removes from the map.
    // Hand out a copy, so the caller can't reach the bag's insides.
    return new ArrayList<>(data.keySet());
}

Practice

for (BagItem bi : data) {
    int common = Math.min(bi.getNum(), other.howMany(bi.getItem()));
    // ... only add to the result if common is positive
}

Bag result = new Bag();
for (Map.Entry<String, Integer> entry : data.entrySet()) {
    int mine = entry.getValue();
    int theirs = other.howMany(entry.getKey());   // a lookup, not a second loop
    // ... your rule for the count, and add it if it's positive
}
return result;

before:  [5, 2 | 8, 1, 9 | 3, 7]
after:   [5, 2 | 1, 8, 9 | 7, 3]

Comparator<T> reversed = new ReverseComparator<>(comparator);
list.subList(i, j + 1).sort(comparator);   // to is exclusive, hence j + 1
// ... and the two outer slices with reversed

Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    counts.merge(word, 1, Integer::sum);
}

Summary

• —Choose by the question you ask: positions and order – List; "is it in there?" – Set; lookup by key – Map. Declare with the interface, create with the class.
• —Generics move type errors to compile time. <T> before the return type declares a type variable; type parameters are never primitives.
• —Collections find objects with equals, hash collections also with hashCode – override both together, and keep keys immutable.
• —An ArrayList search is linear; a HashMap lookup is constant on average. Iterate a map with entrySet(); use getOrDefault where get could return null.
• —Sort with a Comparator: the algorithm moves, the comparator decides. Use Integer.compare, not subtraction.
• —? extends T for sources, ? super T for consumers. subList and keySet are views – return copies from your getters.