$ Java Collections Framework
// Interview Prep — Quick Reference
Quick Reference
List
Duplicate + Ordered + Index Based
Set
Unique Elements
Queue
First In First Out (FIFO)
Map
Key-Value Pair
Synchronized
Thread Safe classes
Legacy
Older thread-safe classes, largely superseded
Legend
List
Set
Queue
Map
Synchronized / Thread Safe
Legacy
Naming Patterns
Hash → No Insertion Order Guarantee
Linked → Insertion Order
Tree → Sorted Order
Hierarchy Trees
Collection Framework Hierarchy
│ │ ├── Collection (I): Root Interface for List, Set and Queue. │ │ │ ├── List (I): Duplicate Allowed, Insertion Order Preserved, Index Based │ │ ├── ArrayList (C): Dynamic Array Structure, Random Access Fast, Middle Insertion/Deletion Slow │ │ ├── LinkedList (C): Doubly Linked List Structure,Insertion/Deletion Fast, Random Access Slow │ │ ├── Vector (C): Same as ArrayList, Synchronized & Thread Safe, Legacy │ │ │ └── Stack (C): Last In First Out (LIFO) │ │ │ ├── Set (I): Unique Elements (No Duplicates) │ │ ├── HashSet (C): No Insertion Order Guarantee │ │ │ └── LinkedHashSet (C): Insertion Order │ │ │ │ │ └── SortedSet (I): Elements are automatically stored in sorted order │ │ └── NavigableSet (I): SortedSet + Navigation Methods │ │ └── TreeSet (C): Sorted Order, Red-Black Tree │ │ │ └── Queue (I): First In First Out (FIFO) │ ├── PriorityQueue (C): Based on Priority (Default: Ascending Order) │ ├── Deque (I): Double Ended Queue │ │ ├── ArrayDeque (C) │ │ └── LinkedList (C) │ │ │ └── BlockingQueue (I): Multithreading │ ├── LinkedBlockingQueue (C) │ ├── ArrayBlockingQueue (C) │ └── PriorityBlockingQueue (C)
Map Hierarchy
└── Map (I): Key-Value Pair, Keys Unique, Values Duplicate │ ├── HashMap (C): No Insertion Order Guarantee, 1 Null Key Allowed │ └── LinkedHashMap (C): Insertion Order, 1 Null Key Allowed │ ├── WeakHashMap (C): If key has no strong reference, GC can remove the corresponding entry ├── IdentityHashMap (C): Uses == instead of equals() for key comparison ├── Hashtable (C): Synchronized & Thread Safe, No Null Key/Value, Legacy, Whole Map Locked ├── ConcurrentHashMap (C): Modern Thread Safe Map, No Null Key/Value, Better Performance than Hashtable, Bucket/Node Locked │ └── SortedMap (I): Keys are automatically stored in sorted order └── NavigableMap (I): SortedMap + Navigation Methods └── TreeMap (C): Sorted by Key, No Null Key, Red-Black Tree
HashMap Internals & Sorting Interfaces
HashMap Internal Working
put(key, value)
HashMap
↓
Array of Buckets
↓
hashCode(key)
↓
Bucket Index Calculation
↓
Bucket Empty?
↙   ↘
Yes
Store Entry
No
Collision
↓
Linked List
↓
Nodes > 8?
↙ ↘
Yes
Red-Black Tree
No
Linked List
get(key)
get(key)
↓
hashCode(key)
↓
Find Bucket
↓
equals(key)
↓
Return Value
hashCode() → Finds Bucket
equals()   → Finds Exact Object
Comparable vs Comparator
Comparable
Purpose Natural Sorting Order
Implements compareTo()
Logics Single Sorting Logic
Comparator
Purpose Custom Sorting Order
Implements compare()
Logics Multiple Sorting Logics