Java Collections Framework: Overview and Hierarchy

Introduction

What the Collections Framework is

• Interfaces - List, Set, Queue, Deque, Map and others. Each describes a kind of collection and what can be done with it, independent of how it is stored.
• Implementations - classes such as ArrayList, HashSet and HashMap, which store the elements in a particular way: in an array, a hash table, a linked list or a tree.
• Algorithms - ready-made operations such as sorting, searching, shuffling and finding the largest element, in the Collections class and as methods of the interfaces.

The Collection interface hierarchy

• Iterable is the root. Anything Iterable can be used in a for-each loop, which is why every collection can be looped over in the same way. How to make your own classes iterable is shown in Implementing the Iterable interfaceClick to read: Implementing the Iterable interface.
• Collection declares the operations every collection has: add, remove, contains, size, isEmpty, clear, the bulk operations addAll, removeAll and retainAll, and stream().
• List - an ordered sequence that allows duplicates, with access by index: get(i), set(i, e), add(i, e).
• Set - a collection without duplicates. Whether two elements are duplicates is decided by their equals() and hashCode() methods, see the equals and hashCode contractClick to read: the equals and hashCode contract. SortedSet and NavigableSet keep the elements sorted and add range operations such as first(), headSet() and ceiling().
• Queue - elements waiting to be processed, normally first in, first out, with offer, poll and peek. Deque (double-ended queue) can add and remove at both ends, so it serves as a queue and as a stack.
• SequencedCollection, added in Java 21, is the common type of the collections that have a defined order - lists, deques and ordered sets. It gives them uniform methods for both ends: getFirst(), getLast(), addFirst(), addLast(), removeFirst(), removeLast() and reversed(). Java 21 Sequenced Collections ExplainedClick to read: Java 21 Sequenced Collections Explained covers them in detail.

The Map interface hierarchy

• Map declares put, get, getOrDefault, containsKey, remove, size and the three views.
• SequencedMap (Java 21) is the type of maps with a defined order of their entries, with firstEntry(), lastEntry(), pollFirstEntry() and reversed().
• SortedMap and NavigableMap keep the keys sorted and add range operations such as headMap(), floorKey() and ceilingKey().

The main implementations

The common Collection operations

//CommonOperations.java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;

public class CommonOperations {

  static void fill(Collection<String> words) {
    for (String w : List.of("pear", "apple", "fig", "apple", "kiwi", "banana")) {
      words.add(w);
    }
  }

  static void describe(String name, Collection<String> words) {
    System.out.printf("%-10s size %d  contains fig: %-5s  %s%n", name, words.size(), words.contains("fig"), words);
  }

  public static void main(String[] args) {
    Collection<String> list = new ArrayList<>();
    Collection<String> hashSet = new HashSet<>();
    Collection<String> treeSet = new TreeSet<>();
    Collection<String> deque = new ArrayDeque<>();
    fill(list);
    fill(hashSet);
    fill(treeSet);
    fill(deque);
    describe("ArrayList", list);
    describe("HashSet", hashSet);
    describe("TreeSet", treeSet);
    describe("ArrayDeque", deque);

    System.out.println();
    list.remove("apple");
    System.out.println("ArrayList after remove(\"apple\") : " + list);
    list.removeIf(w -> w.length() < 5);
    System.out.println("after removeIf(length < 5)      : " + list);
    treeSet.retainAll(List.of("apple", "kiwi", "plum"));
    System.out.println("TreeSet after retainAll         : " + treeSet);
    for (String w : hashSet) {
      System.out.print(w.toUpperCase() + " ");
    }
    System.out.println("<- for-each over the HashSet");
  }
}

ArrayList  size 6  contains fig: true   [pear, apple, fig, apple, kiwi, banana]
HashSet    size 5  contains fig: true   [banana, apple, pear, kiwi, fig]
TreeSet    size 5  contains fig: true   [apple, banana, fig, kiwi, pear]
ArrayDeque size 6  contains fig: true   [pear, apple, fig, apple, kiwi, banana]

ArrayList after remove("apple") : [pear, fig, apple, kiwi, banana]
after removeIf(length < 5)      : [apple, banana]
TreeSet after retainAll         : [apple, kiwi]
BANANA APPLE PEAR KIWI FIG <- for-each over the HashSet

• fill() and describe() accept any Collection<String>, so the same code worked with a list, two sets and a deque.
• The list and the deque kept both "apple"s and the insertion order. The two sets dropped the duplicate, so their size is 5: add() on a set returns false when the element is already there.
• The TreeSet printed its words in alphabetical order. The HashSet printed them in an order that comes from the words' hash codes; it is not insertion order, and a program must not depend on it.
• remove("apple") removed only the first of the two, removeIf() removed every word shorter than five letters (see Collection.removeIfClick to read: Collection.removeIf), and retainAll() kept only the words that are also in the given list.
• The for-each loop works on every collection, because every collection is Iterable.

Maps and their views

//WordCount.java
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class WordCount {
  public static void main(String[] args) {
    String text = "the cat and the dog and the bird";
    Map<String, Integer> counts = new HashMap<>();
    for (String word : text.split(" ")) {
      counts.put(word, counts.getOrDefault(word, 0) + 1);
    }
    System.out.println("counts           : " + counts);
    System.out.println("count of the     : " + counts.get("the"));
    System.out.println("count of fish    : " + counts.get("fish") + " / getOrDefault: " + counts.getOrDefault("fish", 0));

    Map<String, Integer> sorted = new TreeMap<>(counts);
    System.out.println("keySet (sorted)  : " + sorted.keySet());
    System.out.println("values           : " + sorted.values());
    for (Map.Entry<String, Integer> e : sorted.entrySet()) {
      System.out.print(e.getKey() + "=" + e.getValue() + "  ");
    }
    System.out.println("<- entrySet");
  }
}

counts           : {the=3, and=2, cat=1, bird=1, dog=1}
count of the     : 3
count of fish    : null / getOrDefault: 0
keySet (sorted)  : [and, bird, cat, dog, the]
values           : [2, 1, 1, 1, 3]
and=2  bird=1  cat=1  dog=1  the=3  <- entrySet

• put() with a key that is already there replaces its value, which is how each count went up: getOrDefault(word, 0) returns the current count, or 0 for a new word.
• get() returns null for a key that is not in the map, which is easy to miss; getOrDefault() avoids it.
• Copying the HashMap into a TreeMap sorted the entries by key. The views then showed the keys, the values in key order, and the entries as key-value pairs.

Programming to the interface

• The rest of the code depends only on what a list can do, not on how this one is stored. Changing the implementation is then a change of one line - from ArrayList to LinkedList, or from HashSet to TreeSet when the elements should come out sorted.
• Methods that take and return interface types, such as fill(Collection<String>) above, can be used with any implementation.

Sequenced collections in Java 21

//SequencedDemo.java
import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.SequencedMap;
import java.util.SequencedSet;

public class SequencedDemo {
  public static void main(String[] args) {
    List<String> steps = new ArrayList<>(List.of("plan", "build", "test"));
    steps.addFirst("idea");
    steps.addLast("ship");
    System.out.println("list     : " + steps + "  first " + steps.getFirst() + ", last " + steps.getLast());
    System.out.println("reversed : " + steps.reversed());

    SequencedSet<String> visited = new LinkedHashSet<>(List.of("home", "search", "product"));
    System.out.println("set      : " + visited + "  last visited " + visited.getLast());

    SequencedMap<String, Integer> scores = new LinkedHashMap<>();
    scores.put("Tom", 72);
    scores.put("Ann", 95);
    scores.put("Raj", 88);
    System.out.println("map      : " + scores + "  first entry " + scores.firstEntry() + ", reversed " + scores.reversed());
  }
}

list     : [idea, plan, build, test, ship]  first idea, last ship
reversed : [ship, test, build, plan, idea]
set      : [home, search, product]  last visited product
map      : {Tom=72, Ann=95, Raj=88}  first entry Tom=72, reversed {Raj=88, Ann=95, Tom=72}

Choosing a collection

• Looked up by a key? - a Map.
• Must duplicates be rejected? - a Set.
• Taken from the front or the back, as in a queue or a stack? - a Deque, or a PriorityQueue when the smallest (or highest-priority) element must come out first.
• Otherwise - a List.
• Then the order: the hash-based class by default, the linked one to keep insertion order, the tree-based one to keep the elements sorted.

Summary