Java Collections Framework: ArrayList, HashMap, HashSet and More Explained

The Java Collections Framework is one of the most tested topics in Java interviews. Understanding which collection to use, why, and what the performance implications are separates developers who write good Java from those who write slow, buggy Java.

This guide covers the key interfaces, their implementations, and when to use each.

The Collections Hierarchy

The framework is built on a set of interfaces that define behavior, with multiple implementations offering different performance trade-offs.

code
Iterable
  Collection
    List         -- ordered, allows duplicates
    Set          -- no duplicates
    Queue        -- FIFO or priority-based processing
    Deque        -- double-ended queue

Map              -- key-value pairs (does not extend Collection)

List Implementations

ArrayList

Backed by a dynamic array. Fast random access, slow insertion/deletion in the middle.

java
List<String> list = new ArrayList<>();
list.add("Alice");
list.add("Bob");
list.add("Carol");

list.get(1);           // "Bob" — O(1) random access
list.add(1, "Dave");   // O(n) — shifts elements right
list.remove(0);        // O(n) — shifts elements left
list.size();           // O(1)

Time complexity:

Operation	Complexity
get(i)	O(1)
add(end)	O(1) amortized
add(i)	O(n)
remove(i)	O(n)
contains	O(n)

LinkedList

Doubly linked list. Fast insertion/deletion anywhere, slow random access.

java
List<String> list = new LinkedList<>();
Deque<String> deque = new LinkedList<>(); -- also implements Deque

list.add("Alice");
list.addFirst("Bob");   // O(1)
list.addLast("Carol");  // O(1)
list.get(2);            // O(n) -- must traverse

When to use LinkedList over ArrayList: Only when you have frequent insertions/deletions at the front or middle. In practice, ArrayList outperforms LinkedList for most workloads due to cache locality.

In most real-world code, ArrayList is the right default choice. Use LinkedList only when you have profiled and confirmed it helps.

Set Implementations

HashSet

Backed by a HashMap. No ordering, no duplicates, O(1) average for add/contains/remove.

java
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple");  // duplicate — ignored

set.contains("banana"); // true — O(1) average
set.size();             // 2

LinkedHashSet

Like HashSet but maintains insertion order. Slightly more memory overhead.

java
Set<String> set = new LinkedHashSet<>();
set.add("banana");
set.add("apple");
set.add("cherry");

-- Iteration order: banana, apple, cherry (insertion order)

TreeSet

Backed by a Red-Black tree. Elements are sorted. O(log n) for all operations.

java
Set<Integer> set = new TreeSet<>();
set.add(5);
set.add(1);
set.add(3);

-- Iteration order: 1, 3, 5 (sorted ascending)
set.first();  // 1
set.last();   // 5
set.headSet(3); // [1] -- elements less than 3

Choosing between Set implementations:

	Ordering	Performance	Use when
HashSet	None	O(1) avg	Fast lookup, no order needed
LinkedHashSet	Insertion order	O(1) avg	Fast lookup + predictable order
TreeSet	Sorted	O(log n)	Need sorted elements or range queries

Map Implementations

HashMap

The most used collection in Java. Stores key-value pairs with O(1) average operations.

java
Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Carol", 92);

scores.get("Alice");           // 95 — O(1) average
scores.getOrDefault("Dave", 0); // 0 — safe default
scores.containsKey("Bob");     // true
scores.remove("Carol");

-- Iterate entries
for (Map.Entry<String, Integer> entry : scores.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

-- Modern Java
scores.forEach((name, score) ->
    System.out.println(name + ": " + score)
);

-- Compute if absent (great for grouping)
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("admins", k -> new ArrayList<>()).add("Alice");
groups.computeIfAbsent("admins", k -> new ArrayList<>()).add("Bob");

How HashMap Works Internally

HashMap uses an array of buckets. The key's hashCode() determines which bucket. If multiple keys hash to the same bucket (collision), they are stored in a linked list (or a tree for large buckets since Java 8).

This is why:

• Objects used as keys must implement hashCode() and equals() correctly
• A bad hashCode() that always returns the same value degrades to O(n)

LinkedHashMap

Maintains insertion order (or access order if configured). Same O(1) operations as HashMap.

java
Map<String, Integer> map = new LinkedHashMap<>();
map.put("banana", 1);
map.put("apple", 2);
map.put("cherry", 3);
-- Iteration: banana, apple, cherry

TreeMap

Sorted by keys. O(log n) operations. Useful for range queries.

java
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 1);
map.put("apple", 2);
map.put("cherry", 3);

-- Iteration: apple, banana, cherry (alphabetical)
map.firstKey();              // "apple"
map.subMap("apple", "cherry"); // {"apple": 2, "banana": 1}

ConcurrentHashMap

Thread-safe HashMap without global locking. Use when multiple threads read/write the same map.

java
Map<String, Integer> map = new ConcurrentHashMap<>();
-- Safe for concurrent access

Queue and Deque

Queue (FIFO)

java
Queue<String> queue = new LinkedList<>();
queue.offer("first");   // add to tail
queue.offer("second");
queue.offer("third");

queue.peek();   // "first" -- view head, do not remove
queue.poll();   // "first" -- remove and return head
queue.size();   // 2

PriorityQueue

Elements dequeued in priority order (natural ordering or custom Comparator):

java
PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap
pq.offer(5);
pq.offer(1);
pq.offer(3);

pq.poll(); // 1 -- smallest first
pq.poll(); // 3
pq.poll(); // 5

-- Max-heap
PriorityQueue<Integer> maxPq =
    new PriorityQueue<>(Comparator.reverseOrder());

ArrayDeque

Double-ended queue. Use as a stack or queue. Faster than LinkedList for both roles.

java
Deque<String> deque = new ArrayDeque<>();

-- As a stack (LIFO)
deque.push("first");
deque.push("second");
deque.pop(); // "second"

-- As a queue (FIFO)
deque.offerLast("first");
deque.offerLast("second");
deque.pollFirst(); // "first"

Common Interview Questions

Q: What is the difference between ArrayList and LinkedList?

ArrayList is backed by an array — O(1) random access, O(n) insertion/deletion in the middle. LinkedList is doubly linked — O(1) insertion/deletion at known positions, O(n) random access. ArrayList is almost always faster in practice due to CPU cache efficiency.

Q: What is the difference between HashMap and Hashtable?

Hashtable is legacy, synchronized (thread-safe but slow), and does not allow null keys or values. HashMap is not synchronized, allows one null key and multiple null values, and is generally preferred. Use ConcurrentHashMap for thread safety.

Q: Why must hashCode() and equals() be consistent?

If two objects are equal (.equals() returns true), they must have the same hash code. If they have different hash codes, they would end up in different buckets and HashMap would never find one when looking up the other.

Q: When would you use a TreeMap over a HashMap?

When you need keys in sorted order or need range queries like "give me all entries between key A and key B." For simple lookups where order does not matter, HashMap is faster.

Practice Java on Froquiz

Collections questions appear in virtually every Java interview. Test your Java knowledge on Froquiz — covering collections, OOP, concurrency, and more across all difficulty levels.

Summary

• ArrayList — default List choice; fast random access, slow mid-list inserts
• LinkedList — fast front/back inserts; rarely better than ArrayList in practice
• HashSet — fast O(1) membership checks, no order
• TreeSet — sorted set, O(log n) operations
• HashMap — default Map choice; O(1) average, requires good hashCode/equals
• TreeMap — sorted keys, O(log n), good for range queries
• ConcurrentHashMap — thread-safe HashMap for concurrent code
• ArrayDeque — fast stack and queue, prefer over Stack and LinkedList
• PriorityQueue — process elements by priority, not insertion order