Java Collection Framework

1. Collection Framework

The Java Collection Framework provides a standard architecture for storing and manipulating groups of objects. It provides reusable data structures and common operations such as searching, sorting, insertion, manipulation and deletion.

• Collection framework classes and interfaces are mainly in java.util.
• It reduces programming effort through ready-to-use implementations.
• It provides a common set of interfaces, classes and algorithms.

Main Parts

2. Collection, Collections and Iterator

Collection

If we want to represent a group of individual objects as a single entity, we generally use a Collection. The Collection interface defines common operations for collection objects.

Size means the number of objects currently stored. Capacity means how many objects the underlying structure can accommodate before expansion.

Collections class

java.util.Collections contains static utility methods that operate on collections, including algorithms and wrapper methods.

Iterator

Iterator is used to traverse a collection. Important methods are:

Legacy collection classes/interfaces

• Enumeration
• Dictionary
• Hashtable
• Properties
• Vector
• Stack

3. Collection Framework Hierarchy and Interfaces

4. List Interface

List is a child interface of Collection. It is appropriate when duplicates are allowed and insertion order must be preserved. Elements can be distinguished using their indexes.

Common List implementations

5. ArrayList

• Introduced in Java 1.2.
• Underlying structure is a growable/resizable array.
• Insertion order is preserved.
• Duplicates and null values are allowed.
• Heterogeneous objects can be stored when generics are not restricting the type.
• Implements RandomAccess, Serializable and Cloneable.
• Best choice when retrieval/random access is frequent.
• Insertion/deletion in the middle is comparatively expensive because elements may need shifting.

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("A");

System.out.println(list.get(1));

6. Vector and Stack

Vector

• Legacy class introduced in Java 1.0.
• Uses a growable array.
• Insertion order is preserved and duplicates are allowed.
• Methods are synchronized, making Vector thread-safe but adding synchronization overhead.
• Implements RandomAccess, Serializable and Cloneable.

Why ArrayList is faster than Vector?

Vector synchronizes its methods, so access is serialized. ArrayList does not synchronize its methods by default, so it generally has less overhead in single-threaded or externally synchronized use.

Stack

Stack extends Vector and follows the Last-In-First-Out (LIFO) model.

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
System.out.println(stack.pop());

7. LinkedList

• Introduced in Java 1.2.
• Underlying structure is a doubly linked list.
• Duplicates, null values and insertion order are allowed.
• Implements List and Deque.
• Does not implement RandomAccess.
• Suitable when frequent insertion/deletion is required.
• Random access is slower than ArrayList.

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.addFirst("Start");
list.addLast("End");
System.out.println(list.getFirst());
list.removeLast();

8. Set Interface

Set represents a group of objects where duplicates are not allowed.

9. HashSet

• Underlying concept is hashing.
• Duplicates are not allowed.
• Adding a duplicate normally returns false.
• Insertion order is not guaranteed.
• Null insertion is permitted.
• Heterogeneous objects can be stored when not restricted by generics.
• Good choice when fast lookup/search is important.

HashSet<String> set = new HashSet<>();
set.add("Java");
set.add("Spring");
set.add("Java");

System.out.println(set);
System.out.println(set.add("Java")); // false

10. LinkedHashSet

LinkedHashSet is based on HashSet behavior but maintains insertion order.

• Duplicates are not allowed.
• Insertion order is preserved.
• Useful for cache-like applications where uniqueness and insertion order are both required.

11. TreeSet and Sorted Sets

TreeSet represents a group of objects in sorted order.

• Uses a balanced tree structure.
• Duplicates are not allowed.
• Insertion order is not preserved because elements are maintained in sorted order.
• Natural ordering requires mutually comparable elements.
• Incompatible element types can cause ClassCastException.
• String and wrapper classes implement Comparable.

Comparable vs Comparator

class Student implements Comparable<Student> {
    int rollNo;

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.rollNo, other.rollNo);
    }
}

12. Comparator

Comparator is used to define customized sorting for user-defined classes. It is especially useful when the same object must be sorted by different fields such as roll number, name or age.

Comparator<Student> byName =
    (s1, s2) -> s1.name.compareTo(s2.name);

Comparator<Student> byAge =
    (s1, s2) -> Integer.compare(s1.age, s2.age);

students.sort(byName);

The comparator's compare(obj1, obj2) method returns a negative value, zero or a positive value depending on the ordering relationship.

13. Map Interface

Map is not a child of Collection. It represents objects as key-value pairs.

• Both keys and values are objects.
• Duplicate keys are not allowed.
• Duplicate values are allowed.
• Each key-value pair is called an Entry.
• Map.Entry is nested inside the Map interface.

14. HashMap

• Introduced in Java 1.2.
• Hash-based Map implementation.
• Duplicate keys are not allowed; duplicate values are allowed.
• Insertion order is not guaranteed.
• Heterogeneous keys and values are possible when generics do not restrict them.
• One null key is allowed and multiple null values are allowed.

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 10);
map.put("banana", 20);
map.put("orange", 30);

System.out.println(map.get("banana"));

15. Java 8 Map Features

16. LinkedHashMap, IdentityHashMap and WeakHashMap

LinkedHashMap

Same general key-value behavior as HashMap while preserving insertion order. Introduced in Java 1.4.

IdentityHashMap

Unlike HashMap's normal equality-based key comparison, IdentityHashMap uses reference identity (==) for comparing keys.

WeakHashMap

Entries can become eligible for garbage collection when their keys no longer have strong external references. This differs from a normal HashMap, which strongly references its keys through its entries.

17. TreeMap

TreeMap stores key-value pairs while maintaining keys in sorted order.

• Uses a Red-Black tree.
• Duplicate keys are not allowed.
• Values can be duplicated.
• Natural ordering uses Comparable keys.
• A Comparator can be supplied for customized ordering.
• Incompatible keys can result in ClassCastException.
• Null values are allowed; null-key behavior should be considered according to the ordering/comparator being used.

TreeMap<Integer, String> map = new TreeMap<>();
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

System.out.println(map); // sorted by key

18. Hashtable, SortedMap and NavigableMap

Hashtable

• Legacy Map implementation introduced in Java 1.0.
• Methods are synchronized.
• Duplicate keys are not allowed; duplicate values are allowed.
• Null keys and null values are not allowed.
• Insertion order is not preserved.

SortedMap

A child interface of Map that maintains entries according to sorted keys.

NavigableMap

A child interface of SortedMap that adds navigation methods for locating closest matching keys/entries.

19. Dictionary and Properties

Dictionary represents a key-value storage abstraction and is a legacy abstract class.

Properties extends Hashtable and is commonly used for configuration data, where keys and values are strings.

A major benefit of external properties files is that frequently changing configuration values can be changed without recompiling the Java class.

20. Queue, RandomAccess and PriorityQueue

Queue

Queue represents objects waiting for processing and extends Collection.

RandomAccess

RandomAccess is a marker interface. A collection implementing it indicates that indexed element access can be performed efficiently. ArrayList and Vector implement it.

PriorityQueue

• Implements Queue.
• Maintains elements according to priority rather than insertion order.
• Priority may use natural ordering or a Comparator.
• Duplicates are allowed in the normal PriorityQueue contract.
• Null elements are not allowed.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(20);

System.out.println(pq.poll()); // 10

21. For-each Loop

The enhanced for-each loop executes once for every element in a collection or array.

for (String value : collection) {
    System.out.println(value);
}

If a collection contains n elements, the loop body is executed once for each of those elements.

22. Internal Data Structures

23. Capacity and Load Factor

The commonly cited default HashMap load factor is 0.75. For an initial capacity of 16, the threshold is 12.

24. HashMap Internal Working

HashMap works using hashing and an array of buckets.

1. When put(key,value) is called, the key's hash is calculated.
2. Java 8 spreads hash bits to improve distribution.
3. The bucket index is calculated using the table size and hash.
4. If the bucket is empty, a new node is placed there.
5. If a collision occurs, entries are linked within the bucket.
6. When collisions become sufficiently large and the table is large enough, Java 8 can convert a bucket to a Red-Black tree.
7. get(key) calculates the same hash/index and searches the bucket using key equality.
8. When the threshold is exceeded, the table is resized, normally by expanding the capacity and redistributing entries.

Node structure

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Hash calculation in Java 8 style

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

For a table length n, the bucket index is calculated as (n - 1) & hash when the table length is a power of two.

25. HashMap Collision Handling and Treeification

• Multiple keys can produce the same bucket index.
• A bucket initially uses linked nodes for collisions.
• When the number of nodes reaches the treeification threshold (8 in the Java 8 implementation) and the table is sufficiently large, the bucket can be treeified.
• The minimum table capacity for treeification is 64 in Java 8.
• Tree bins improve worst-case bucket lookup from linear behavior toward logarithmic behavior.

26. ConcurrentHashMap Internal Working

Java 8 redesigned ConcurrentHashMap around a Node array and fine-grained concurrency instead of the old segment-locking design.

1. For put(), the key is hashed and its bucket located.
2. If the bucket is empty, an atomic CAS operation can insert a node.
3. If the bucket contains nodes, a synchronized block can protect that specific bucket while the key is searched/updated.
4. get() is designed as a read operation that normally does not require locking the entire map.
5. Operations such as compute/merge use localized synchronization.
6. Table expansion can be performed cooperatively by multiple threads.

27. BlockingQueue

BlockingQueue extends Queue and provides thread-safe blocking operations.

• If a consumer attempts to retrieve from an empty queue, it can wait until an element becomes available.
• If a producer attempts to insert into a full bounded queue, it can wait until space becomes available.
• Null elements are not permitted.
• Implementations are thread-safe.

public interface BlockingQueue<E> extends Queue<E>

28. hashCode() and equals()

hashCode()

hashCode() returns an integer hash value. If two objects are equal according to equals(), they must return the same hash code.

Different objects can still have the same hash code; this is a hash collision.

Why override equals()?

Override equals() when logical equality should be based on object properties rather than object identity. For example, an Employee object could define equality based on salary, ID or another business property.

29. Synchronizing Collections

The Collections utility class provides wrappers for synchronized collection access:

Collections.synchronizedList(list);
Collections.synchronizedSet(set);
Collections.synchronizedSortedSet(sortedSet);
Collections.synchronizedMap(map);
Collections.synchronizedSortedMap(sortedMap);

30. Generic Collections

Generics provide three important benefits:

• Type safety — invalid types are detected at compile time.
• Less type casting — retrieved values already have the declared type.
• Earlier bug detection — many errors are caught during compilation.

List<String> names = new ArrayList<>();
names.add("Java");
// names.add(10); // compile-time error

31. Hash Collision

A hash collision occurs when different keys produce the same hash value or map to the same bucket. Common collision-handling strategies include:

• Separate chaining
• Open addressing

Java's HashMap uses bucket-based chaining and, in modern Java versions, tree bins for sufficiently large collision chains.

32. Fail-fast Iterator

A fail-fast iterator detects structural modification of a collection during iteration and may throw ConcurrentModificationException. It does not require a separate copy of the entire collection.

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");

for (String value : list) {
    // Structural modification here may cause
    // ConcurrentModificationException.
}

33. Read-only ArrayList and Removing Duplicates

Read-only view

List<String> readOnly =
    Collections.unmodifiableList(list);

Modification operations through the unmodifiable view are rejected.

Remove duplicates

Use HashSet when ordering does not matter, or LinkedHashSet when insertion order should be preserved.

List<String> list =
    new ArrayList<>(Arrays.asList("A","B","A","C"));

List<String> unique =
    new ArrayList<>(new LinkedHashSet<>(list));

34. ArrayList vs LinkedList

35. ConcurrentHashMap Overview

ConcurrentHashMap is a thread-safe map designed for concurrent access. Retrieval operations do not lock the entire table, and the class provides high concurrency for updates. It is functionally compatible with the Map contract while avoiding the coarse synchronization model of legacy Hashtable.

36. Map Views

The Map interface provides three main collection views:

• keySet() — view of keys.
• values() — view of values.
• entrySet() — view of key-value entries.

These views can be traversed using iterators.

37. HashMap vs TreeMap

38. Collection Class Constructor Overview

39. Quick Interview Revision