☕
Core Java Roadmap Phase 05
0 / 40 (0%)
☰ Syllabus Index Next: P06 →

Collections Framework & Low-Level Data Structures

📂 Repository Module: Module 1_ Collections part1 & part2 demos \ Demos_Data_Structures
📖 Textbook Alignment: Volume I — Chapter 9: Collections (Lists, Sets, Maps, Queues, Iterators, and Algorithms)
Phase 5

Collections Framework & Data Structures

📂 Module 1... \\ Collections part1 demos & Collections_Part2_Demos
📖 Core Java Textbook Alignment: Volume I — Chapter 9: Collections (The JCF Hierarchy, Maps, Views, and Algorithms)

5.1 Collections Hierarchy: List, Set, Queue & Why Map is Separate

📖 Cay S. Horstmann • Core Java Volume I — Chapter 9, Section 9.1 ("The Collections Framework")
“The Java library separates interfaces and implementations. A LinkedList has constant-time insertions at an iterator position, while an ArrayList has constant-time random access. In a hash table, when a bucket contains ≥ 8 nodes, Java 8 converts the linked list to a balanced red-black tree.”
  • Growth MathArrayList grows by 1.5x: newCapacity = oldCapacity + (oldCapacity >> 1).
⚡ Pro-Tip: Fail-Fast Iterators & modCount
Mutating a collection directly while looping throws ConcurrentModificationException! Use iterator.remove() or list.removeIf().
💡 Real-World Analogy: The Warehouse Storage Systems
• List (The Numbered Shelf): Elements have exact index numbers (0, 1, 2, ...). Insertion order is preserved, and duplicate items are completely welcome.
• Set (The Unique Keyring): A bag of unique items. You cannot have two identical room keys. If you try to add a duplicate, it gets ignored.
• Queue (The Supermarket Checkout Line): First-In, First-Out (FIFO). The first customer in line is the first one served.
• Map (The Theater Coat Check): You hand the attendant your jacket and get ticket #42. To retrieve your jacket, you present ticket #42. A Map holds Key → Value pairs. It does not extend Collection because key-value mappings cannot support single-element methods like add(element).
🖊 Architectural Diagram: Java Collections & Map Framework Hierarchy [Core Java Vol I Ch 9] Mermaid Diagram
graph TD Iterable["java.lang.Iterable"] --> Collection["java.util.Collection"] Collection --> List["List (Ordered, Index-accessible)"] Collection --> Set["Set (Unique elements)"] Collection --> Queue["Queue / Deque (FIFO / LIFO)"] List --> ArrayList["ArrayList (Dynamic Resizable Array)"] List --> LinkedList["LinkedList (Doubly-linked nodes)"] List --> Vector["Vector / Stack (Legacy Synchronized)"] Set --> HashSet["HashSet (Backed by HashMap)"] Set --> LinkedHashSet["LinkedHashSet (Maintains insertion order)"] Set --> TreeSet["TreeSet (Sorted Red-Black Tree)"] Queue --> PriorityQueue["PriorityQueue (Min-Heap)"] Queue --> ArrayDeque["ArrayDeque (Circular array buffer)"] Map["java.util.Map (Key-Value Mappings)"] Map --> HashMap["HashMap (Node Array + Red-Black Tree)"] Map --> LinkedHashMap["LinkedHashMap (Hash table + Linked list)"] Map --> TreeMap["TreeMap (Navigable Red-Black Tree)"] Map --> ConcurrentHashMap["ConcurrentHashMap (Lock-striped concurrent)"]

5.2 HashMap Internals: Bucket Hashing, Collisions & Treeification

💡 Real-World Analogy: How HashMap Works (The Post Office Mailboxes)
Imagine a wall of 16 mailboxes labeled 0 through 15 (Node<K,V>[] table).
1. When you do map.put("Alice", 25), Java takes the key's hash code and calculates: index = (16 - 1) & hash. Suppose it equals 3.
2. Java opens mailbox #3 and places the package inside.
3. Hash Collision: What if another key ("Bob") ALSO calculates to mailbox #3? Java links Bob's package to Alice's package like a chain (Singly Linked List).
4. Treeification (Java 8+): If 8 people all collide into mailbox #3, scanning that long chain becomes slow (O(n)). So Java transforms that mailbox into a balanced Red-Black Tree, speeding search up to O(log n)!
🖊 Architectural Deep Dive: HashMap Bucket Collisions & Treeification Mermaid Diagram
graph LR subgraph BucketArray ["Bucket Array: Node<K,V>[] table"] B0["Bucket [0]"] B1["Bucket [1]"] B2["Bucket [2]"] end subgraph SingleNode ["Bucket [0]: Single Node"] N0["Node: Key='Alice', Hash=1024, Val=100"] end subgraph LinkedListChain ["Bucket [1]: Linked List (len < 8)"] L1["Node 1"] --> L2["Node 2"] --> L3["Node 3"] end subgraph RedBlackTree ["Bucket [2]: Treeified (len >= 8 & cap >= 64)"] Root["TreeNode (Root)"] Left["TreeNode (Left)"] Right["TreeNode (Right)"] Root --> Left Root --> Right end B0 --> SingleNode B1 --> LinkedListChain B2 --> RedBlackTree
📂 Module 1.../SortByNameComparator.java — Custom Comparator
package com.accenture.ltt.collections;

import java.util.Comparator;

/**
 * Comparable vs Comparator:
 * - Comparable defines the NATURAL sorting order inside the class itself (compareTo).
 * - Comparator defines EXTERNAL custom sorting strategies without modifying the class.
 */
public class SortByNameComparator implements Comparator<Course> {
    @Override
    public int compare(Course c1, Course c2) {
        return c1.getCourseName().compareToIgnoreCase(c2.getCourseName());
    }
}
👁 Comparable vs Comparator Architectural Differences
  • Comparable (Natural Ordering) Implemented inside the domain model (e.g. class Employee implements Comparable<Employee>). Defines the single default sort order via compareTo(o). Modifies the class directly.
  • Comparator (Custom Sorting Strategies) Implemented in separate external classes or inline lambdas (Comparator.comparing(Course::getCourseName)). Adheres to the Open/Closed Principle: you can introduce 20 different sorting strategies (by price, rating, date) without modifying the original Course class!
  • The compare() Contract Returns negative if c1 < c2, zero if equal, positive if c1 > c2. When sorting custom objects in TreeSet or TreeMap, returning 0 causes the second object to be treated as a duplicate and dropped!
📂 Module 1.../Collections_Part2_Demos/.../CourseComparableTester.java
package com.accenture.ltt.collection.assignment.comparable;

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

// Class implements Comparable to define its NATURAL order
class Course implements Comparable<Course> {
    private int courseId;
    private String courseName;
    private int courseFee;

    public Course(int id, String name, int fee) {
        this.courseId = id;
        this.courseName = name;
        this.courseFee = fee;
    }

    public int getCourseFee() { return courseFee; }
    public String getCourseName() { return courseName; }

    // compareTo defines sorting by course fee ascending
    @Override
    public int compareTo(Course o) {
        return Integer.compare(this.courseFee, o.courseFee);
    }
}

public class CourseComparableTester {
    public static void main(String[] args) {
        List<Course> courses = new ArrayList<>();
        courses.add(new Course(1056, "C#.Net", 20000));
        courses.add(new Course(1045, "Java", 15000));
        courses.add(new Course(4532, "Python", 20500));

        Collections.sort(courses); // Sorts automatically using compareTo()
        courses.forEach(c -> System.out.println(c.getCourseName() + " : $" + c.getCourseFee()));
    }
}
👁 Comparable compareTo() Sorting Mechanics
  • Integer.compare() Line 24: Prefer Integer.compare(a, b) over subtraction (this.fee - o.fee) to defend against integer arithmetic overflow when comparing large or negative values.
  • Collections.sort() Integration Line 35: Collections.sort(courses) requires elements to implement Comparable<T>. At runtime, the JVM uses TimSort (adaptive merge sort, O(N log N)).
📂 Module 1.../Collections part1 demos/.../HashMapIteratorExample.java
package com.accenture.ltt.collection.demo.map;

import java.util.*;

public class HashMapIteratorExample {
    public static void main(String[] args) {
        Map<Integer, String> directory = new HashMap<>();
        directory.put(404232, "Venkat Rajaram");
        directory.put(502113, "Tia Mathew");
        directory.put(562190, "Ali Mohammed");

        // Method 1: Iterating over keySet (Requires secondary map.get(key) lookup)
        for (Integer contact : directory.keySet()) {
            System.out.println("KeySet -> Contact: " + contact + " | Name: " + directory.get(contact));
        }

        // Method 2: Iterating over entrySet (MOST EFFICIENT: No secondary lookup!)
        for (Map.Entry<Integer, String> entry : directory.entrySet()) {
            System.out.println("EntrySet -> " + entry.getKey() + " = " + entry.getValue());
        }

        // Method 3: Java 8+ forEach BiConsumer lambda
        directory.forEach((k, v) -> System.out.println("Lambda -> " + k + " : " + v));
    }
}
👁 Map Traversal Performance: keySet() vs entrySet()
  • The keySet() Penalty Calling map.get(key) inside a keySet() loop performs a second hash calculation and bucket lookup for every single key! Avoid this in large loops.
  • The entrySet() Efficiency entrySet() iterates over the underlying Node<K,V> bucket array directly, giving both key and value in a single memory access without extra hashing.