Java Collections Framework: Collection Hierarchy and Interfaces

Try writing Collection<String> names = new HashMap<String, String>(); and the compiler stops you with incompatible types: HashMap<String,String> cannot be converted to Collection<String>. HashMap is part of the Java Collections Framework, yet it does not implement the Collection interface. Mistakes like this disappear once you see the collection hierarchy as a whole.

The Java Collections Framework (also called the Collection Framework or the Java Collections API) is a set of interfaces, implementations and algorithms in the java.util package for storing and processing groups of objects: lists, sets, queues and key–value maps. A collection in Java is simply an object that holds other objects. Unlike an array, a collection grows and shrinks dynamically, and ready-made methods let you search, sort and filter elements without writing the loops yourself. Collections appeared in J2SE 1.2 (1998); generics were added to them in Java 5.

What the Java Collections Framework consists of

The Java Collections Framework has three parts: interfaces that describe the behavior of a collection (list, set, queue, map), implementations such as ArrayList and HashMap that provide a concrete data structure, and algorithms, which are static methods for sorting, searching and shuffling.

By convention, a variable is declared with the interface type, and the implementation appears only after new: List<String> names = new ArrayList<>();. You can then switch to another implementation by changing one line, without touching the rest of the code.

Collection hierarchy in Java

The collection hierarchy in Java has two independent branches. The first starts with the Collection interface (which extends Iterable) and splits into List, Set and Queue. The second is the Map interface for key–value pairs: it belongs to the Collections Framework but does not extend Collection.

The same hierarchy as text (an arrow → means “extends / implements”; the main classes are listed after the dash):

Iterable<T>
└── Collection<E>
    ├── List<E>            — ArrayList, LinkedList, Vector → Stack
    ├── Set<E>             — HashSet → LinkedHashSet
    │   └── SortedSet<E> → NavigableSet<E>   — TreeSet
    └── Queue<E>           — PriorityQueue
        └── Deque<E>       — ArrayDeque, LinkedList

Map<K,V>                   — HashMap → LinkedHashMap, Hashtable
└── SortedMap<K,V> → NavigableMap<K,V>  — TreeMap

Note that LinkedList appears in two branches: it implements both List and Deque. Vector, Stack and Hashtable date back to Java 1.0 and were fitted into the hierarchy later; new code does not use them.

Core collection interfaces in Java

The Java Collections Framework has six core collection interfaces: List (an ordered list with indexes), Set (no duplicates), SortedSet/NavigableSet (a sorted set), Queue, Deque (a double-ended queue that also works as a stack) and Map (key–value pairs). They differ in whether duplicates are allowed and in what order elements come back.

Uniqueness in a HashSet and in HashMap keys is decided by equals() and hashCode(): if you store your own objects, override both (see the equals() method in Java).

Choosing an implementation: performance comparison

To pick a collection class, answer three questions: do you need index access, does element order matter, and do you need sorting? For most tasks ArrayList, HashSet, HashMap and ArrayDeque are enough. Other classes are for a special order or fast inserts at the ends of a list. The last column shows Java collections performance in Big O notation.

Ordered vs sorted collections in Java

The “Order” column above mixes two different properties. An ordered collection iterates over its elements in a predictable order that does not depend on their values: by index or by insertion order. A sorted collection arranges elements by their values — in natural ordering (Comparable) or by a Comparator.

Set<String> linked = new LinkedHashSet<>(List.of("pear", "apple", "fig"));
Set<String> sorted = new TreeSet<>(List.of("pear", "apple", "fig"));
System.out.println(linked); // [pear, apple, fig] - insertion order
System.out.println(sorted); // [apple, fig, pear] - alphabetical

So “ordered” is not enough when you need sorted output: a LinkedHashSet keeps the order you added elements in, but does not sort them. PriorityQueue is a special case: poll() always returns the smallest element, but its iterator walks the heap without sorting.

The O(1) for hash-based classes holds only when hashCode() spreads keys evenly. If every key returns the same hash code, all of them land in one bucket and lookups degrade (since Java 8, a crowded HashMap bucket turns into a tree, so the worst case is O(log n) rather than O(n) for comparable keys).

Generic collections

All interfaces and classes of the Java Collections Framework are generic (since Java 5): you specify the element type in angle brackets, for example List<String>. The compiler then refuses to add an object of another type, and you need no cast when reading. A collection without a type parameter (a raw type) compiles with only a warning and fails at runtime instead.

import java.util.ArrayList;
import java.util.List;

public class RawListExample {
    public static void main(String[] args) {
        List raw = new ArrayList();      // raw type: the compiler only warns
        raw.add("Java");
        raw.add(42);                     // no error: element type is not checked

        for (Object item : raw) {
            String s = (String) item;    // fails on the second element
            System.out.println(s.toUpperCase());
        }
    }
}

Output:

JAVA
Exception in thread "main" java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String (java.lang.Integer and java.lang.String are in module java.base of loader 'bootstrap')
	at RawListExample.main(RawListExample.java:11)

With List<String> list = new ArrayList<>(); the line list.add(42) does not compile, so the bug is caught before the program runs. Primitives such as int and double cannot be stored directly: you use a wrapper class (List<Integer>) and autoboxing. Wildcards <? extends T> and <? super T> in method parameters are covered in the lesson on Java generics.

Immutable collections

An immutable (unmodifiable) collection is one whose add(), remove() and set() methods throw UnsupportedOperationException. In modern Java you create them with the factory methods List.of(), Set.of(), Map.of() (Java 9) and List.copyOf() (Java 10). The options differ in details: whether null is allowed and whether the result is linked to the source data.

What does this code print?

import java.util.Arrays;
import java.util.List;

public class UnmodifiableExample {
    public static void main(String[] args) {
        List<String> fixed = Arrays.asList("a", "b");
        fixed.set(0, "z");
        System.out.println(fixed);

        try {
            fixed.add("c");
        } catch (UnsupportedOperationException e) {
            System.out.println("Arrays.asList: add() not allowed");
        }

        List<String> immutable = List.of("a", "b");
        try {
            immutable.set(0, "z");
        } catch (UnsupportedOperationException e) {
            System.out.println("List.of: set() not allowed");
        }
    }
}

[z, b]
Arrays.asList: add() not allowed
List.of: set() not allowed

Arrays.asList() returns a fixed-size list, not an immutable one: you may replace an element but not change the size. If you need an ordinary mutable list with initial elements, wrap the factory: new ArrayList<>(List.of("a", "b")). Converting a primitive array such as int[] is a separate case — see convert int array to List. The toList() terminal operation belongs to the Stream API.

Thread-safe collections in Java

The standard ArrayList, HashSet and HashMap are not thread-safe: concurrent writes from several threads lose data, and iteration can fail with ConcurrentModificationException. For multithreaded code Java offers three groups of collections: legacy synchronized classes, Collections.synchronizedXxx() wrappers and the classes of the java.util.concurrent package (Java 5).

Example: two threads each increment a shared counter in a ConcurrentHashMap 10,000 times. The merge() method reads and writes atomically, so no increment is lost (Integer::sum is a method reference):

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentCounter {
    public static void main(String[] args) throws InterruptedException {
        Map<String, Integer> counts = new ConcurrentHashMap<>();
        Runnable task = () -> {
            for (int i = 0; i < 10_000; i++) {
                counts.merge("clicks", 1, Integer::sum);
            }
        };

        Thread t1 = new Thread(task);
        Thread t2 = new Thread(task);
        t1.start();
        t2.start();
        t1.join();
        t2.join();

        System.out.println(counts.get("clicks")); // Output: 20000
    }
}

Replace ConcurrentHashMap with HashMap and the result becomes unpredictable: usually less than 20000, because the threads overwrite each other’s updates.

Topics of the Collections module

The Collections module goes from general to specific: first the root interface and basic data structures, then each branch of the hierarchy — lists, sets, queues and maps — and finally the tools for working with them.