Phase 5
Collections Framework & Data Structures
📂 Module 1... \\ Collections part1 demos & Collections_Part2_Demos
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
• 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 (
1. When you do
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)!
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 viacompareTo(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 originalCourseclass! -
The compare() Contract
Returns negative if
c1 < c2, zero if equal, positive ifc1 > c2. When sorting custom objects inTreeSetorTreeMap, 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 implementComparable<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 akeySet()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 underlyingNode<K,V>bucket array directly, giving both key and value in a single memory access without extra hashing.