Java Collections: List, Set, Map and How HashMap Works

The Collections Framework is a guaranteed interview topic, and HashMap is its star question. This article covers the types you must know and the questions that go with them.

The hierarchy at a glance

Collection is the interface, and Collections (with an s) is a utility class with helpers such as sort and unmodifiableList.

import java.util.*;

public class Collections101 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(List.of("b", "a", "c", "a"));
        Set<String> unique = new LinkedHashSet<>(list);
        System.out.println(unique);                         // [b, a, c]

        Map<String, Integer> counts = new HashMap<>();
        for (String word : "the cat and the hat".split(" ")) {
            counts.merge(word, 1, Integer::sum);
        }
        System.out.println(new TreeMap<>(counts));          // {and=1, cat=1, hat=1, the=2}

        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop());                    // 2

        Queue<String> queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");
        System.out.println(queue.poll());                   // first
    }
}

List.of(...), Set.of(...) and Map.of(...) (Java 9) create immutable collections: adding to them throws UnsupportedOperationException.

ArrayList versus LinkedList

ArrayList starts with a default capacity of 10 (allocated on the first add) and grows by about 1.5 times when full.

How HashMap works internally (Java 8 and later)

A HashMap is an array of buckets. Here is what put(key, value) does:

1. Calls key.hashCode() and spreads the bits so that high bits also matter: hash = h ^ (h >>> 16).
2. Picks the bucket: index = (capacity - 1) & hash (capacity is always a power of two).
3. If the bucket is empty, stores the entry there. If not (a collision), it walks the bucket comparing keys with equals(): it replaces the value if the key is already there, or appends a new node.
4. If one bucket grows to 8 or more nodes and the table has at least 64 slots, the bucket's linked list becomes a red-black tree. A lookup in that bucket then costs O(log n) instead of O(n). (If the table is smaller, it resizes instead.) A tree turns back into a list when it shrinks to 6 or fewer.
5. When the number of entries exceeds capacity x load factor (default 16 x 0.75 = 12), the table doubles and entries are redistributed (a rehash).

Key facts to say aloud:

• Average and are O(1). The worst case is O(log n) (O(n) before Java 8).
• It allows one key and many values.
• It is not thread-safe and has no guaranteed iteration order. Use for insertion order, for sorted keys and for concurrent access.
• Keys need a correct and and should be immutable. See equals and hashCode.
• A is just a that uses the elements as keys.

Comparable versus Comparator

Fail-fast iterators

The iterators of , and most collections are fail-fast: they track a modification count, and if the collection is structurally changed during iteration by anything other than the iterator itself, the next step throws .

To remove safely, use , an explicit and its , or collect the items to delete first. Fail-fast is a best-effort bug detector and not a thread-safety guarantee.

Practise

1. Use a to count the letters in a word: character frequency snippet.
2. Make a class a key without , watch the lookup fail, then fix it.
3. Take the Collections, Generics and Exceptions quiz.