Parth Agarwal — Software Engineer | Full Stack Developer Portfolio

Basics

Key Traits

▸Objects only — no primitives. Growable, hetero or homogeneous.

▸Hierarchy: Iterable ← Collection ← Queue / List / Set

Initial Capacities & Growth

Class	Initial Capacity	Growth Strategy	Backed By
`ArrayList`	10	1.5× (old + old >> 1)	Dynamic array
`Vector`	10	2× (doubles)	Dynamic array (synchronized)
`HashMap`	16	2× (doubles) at LF=0.75	Array of Node buckets
`HashSet`	16	2× (doubles) at LF=0.75	HashMap internally
`LinkedHashMap`	16	2× (doubles) at LF=0.75	HashMap + doubly linked list
`TreeMap`	—	—	Red-Black Tree
`TreeSet`	—	—	TreeMap internally
`Hashtable`	11	2n + 1	Array of Entry buckets
`PriorityQueue`	11	< 64: +2 · ≥ 64: 1.5×	Binary heap array
`ArrayDeque`	16	2× (doubles)	Circular array
`ConcurrentHashMap`	16	2× (doubles) at LF=0.75	Segmented Node array

▸HashMap Treeify Threshold: 8 (bucket converts linked list → red-black tree)

▸Untreeify Threshold: 6 (tree converts back to linked list)

▸Min Treeify Capacity: 64 (table must be ≥ 64 before treeification happens)

Full Collection Framework Hierarchy

Iterable (java.lang)
└── Collection (java.util)
├── List (ordered, index-based, duplicates allowed)
│ ├── ArrayList
│ ├── LinkedList (also implements Deque)
│ ├── Vector (legacy)
│ │ └── Stack (legacy)
│ └── CopyOnWriteArrayList
├── Set (no duplicates)
│ ├── HashSet
│ │ └── LinkedHashSet
│ ├── SortedSet (interface)
│ │ └── NavigableSet (interface)
│ │ └── TreeSet
│ └── EnumSet
└── Queue
├── PriorityQueue
├── ArrayBlockingQueue
└── Deque (interface)
├── ArrayDeque
└── LinkedList

Map (java.util — does NOT extend Collection)
├── HashMap
│ └── LinkedHashMap
├── Hashtable (legacy)
├── SortedMap (interface)
│ └── NavigableMap (interface)
│ └── TreeMap
├── EnumMap
├── WeakHashMap
├── IdentityHashMap
└── ConcurrentHashMap

Collection Interface Methods

add()remove()clear()size()contains()

Collections Utility Class (java.util)

▸Static toolbox — operates on/returns collections.

`addAll(col)`	Bulk add
`binarySearch(col, item)`	Binary search
`sort(list)`	Natural sort
`reverse(list)`	Reverse order
`shuffle(list)`	Randomize
`fill(list, obj)`	Fill with obj
`copy(dest, src)`	Overwrites dest
`frequency(col, obj)`	Count occurrences
`disjoint(c1, c2)`	true if no common elements
`emptyList / emptySet`	Immutable empty

equals() Contract

`a.equals(a)`	Reflexive → true
`a.equals(b) == b.equals(a)`	Symmetric
`a=b, b=c → a=c`	Transitive
`a.equals(null)`	Always false

▸hashCode rule: equals → same hashCode (not vice versa)

⚠️ Violation breaks HashMap, HashSet, ConcurrentHashMap

List

Implementations

Class	Notes
`ArrayList`	Dynamic array, random access O(1)
`Vector`	Legacy, synchronized (slow)
`LinkedList`	Doubly linked, slower access O(n)
`Stack`	extends Vector (legacy)

Creating Lists

`Arrays.toList(arr)`	Immutable
`Arrays.asList(arr)`	Fixed-size, set() allowed
`new ArrayList<>(Arrays.asList(arr))`	Fully mutable
`List.of(...)`	JDK 9+ unmodifiable
`Collections.unmodifiableList()`	JDK 8

ArrayList Growth

▸Grows by 1.5×: newCap = old + (old >> 1)

▸Not 2× (wasteful) · not smaller (frequent resize)

LinkedList Note

▸Scattered memory → cache-unfriendly → used less in practice

Queue

Hierarchy

Queue interface
├── PriorityQueue (min-heap)
└── Deque interface
├── ArrayDeque (preferred)
└── LinkedList

ArrayDeque

▸Circular buffer backed array, init size 16, doubles when full

▸Head & tail pointers. Not thread-safe. Faster than synchronized Stack.

Safe (returns false/null)	Throws Exception
`offerFirst / offerLast`	`addFirst / addLast`
`pollFirst / pollLast`	`removeFirst / removeLast`
`peekFirst / peekLast`	`getFirst / getLast`

▸As Stack: push() / pop()

▸As Queue: offer() / poll()

PriorityQueue

▸Default: natural ordering (min-heap). Binary heap: parent ≤ children → root = smallest

▸Auto-grows. add() / poll() / peek() / contains() / toArray()

▸remove(obj) is O(n) (linear search + rebalance)

▸Used in Dijkstra's & Prim's algorithms

Set

Implementations

Set interface
├── HashSet — hashtable, unordered, fastest O(1)
│ └── LinkedHashSet — hashtable + linkedlist, insertion-ordered
├── SortedSet
│ └── TreeSet — red-black tree, sorted O(log n)
└── EnumSet

Key Notes

▸add() returns true if new element, false if duplicate

▸HashSet internally uses HashMap — stores map.put(key, PRESENT)

▸LinkedHashSet slightly slower than HashSet (linked list overhead)

▸JDK 9: Set.of(...) → unmodifiable · JDK 8: Collections.unmodifiableSet()

Map

Hierarchy

Map interface (does NOT extend Collection)
├── HashMap
│ └── LinkedHashMap
├── HashTable — legacy, synchronized, slow
├── SortedMap → TreeMap
├── EnumMap
├── WeakHashMap
└── ConcurrentHashMap

HashMap Internals

▸Array of buckets (linked lists). Default capacity 16, load factor 0.75

▸Threshold = capacity × loadFactor → doubles capacity on exceed

▸index = (n-1) & hash — capacity always power of 2

▸Bucket ≥ 8 entries and capacity ≥ 64 → converts to red-black tree

▸Converts back to linked list at 6 entries

▸Hash spreading: hash ^ (hash >>> 16) (mixes high bits → reduces collisions)

⚠️ If key's hashCode changes after insertion → entry becomes unreachable

▸Null key → stored at bucket 0. Allows one null key + multiple null values.

▸Pre-size: new HashMap<>(expectedSize / 0.75f + 1)

HashMap Methods

put(k,v)remove(k)get(k)keySet()entrySet()containsKey()containsValue()putIfAbsent(k,v)isEmpty()size()equals()

Iteration Pattern

for (Map.Entry<Integer, String> entry : students.entrySet()) {entry.getKey();   // keyentry.getValue(); // value}

Map Comparison

Class	Order	Null Key	Thread-safe	Speed
`HashMap`	None	✓ (1)	✗	O(1)
`LinkedHashMap`	Insert/Access	✓ (1)	✗	O(1)
`TreeMap`	Sorted	✗ natural	✗	O(log n)
`HashTable`	None	✗	✓	Slow
`ConcurrentHashMap`	None	✗	✓	Fast
`EnumMap`	Enum ordinal	✗	✗	O(1)
`WeakHashMap`	None	✓	✗	O(1)

TreeMap

▸Red-black tree instead of buckets. Implements NavigableMap

▸No null key (natural ordering). Custom: new TreeMap<>(Comparator.reverseOrder())

LinkedHashMap

▸Hash table + doubly linked list for insertion order

▸new LinkedHashMap<>(16, 0.75f, true) → access-order mode

▸Override removeEldestEntry() → behaves as LRU Cache

WeakHashMap

▸Keys are WeakReference — GC'd when key set to null. Memory-saving cache.

Reference Type	GC Behavior
Strong `Integer i = 10`	Never GC'd while reachable
Soft `SoftReference<>`	GC'd only when JVM needs memory
Weak `WeakReference<>`	GC'd immediately when unreachable

NavigableMap Key Methods

Method	Returns
`lowerKey(k)`	Greatest key < k
`floorKey(k)`	Greatest key ≤ k
`ceilingKey(k)`	Smallest key ≥ k
`higherKey(k)`	Smallest key > k

▸Primary impl: TreeMap — designed for range queries & closest-match

EnumMap & IdentityHashMap

▸EnumMap: Fixed ordinals → array indexing values[ordinal] → no hashing, true O(1)

▸IdentityHashMap: Uses == instead of equals(). Use for object graphs, serialization frameworks.

Red-Black Tree Properties

▸BST + root & null leaves are black

▸Red node → only black children

▸Equal black-node count on every root-to-leaf path

Comparable & Comparator

Comparable (java.lang)

▸Class implements Comparable<T> and defines compareTo(T obj)

▸Returns neg (less), 0 (equal), pos (greater) → curr - param = ascending

▸Natural ordering. Modifies class source. Single strategy only.

Comparator

▸External. Implement Comparator<T>, override compare(a, b)

▸Multiple strategies possible. Pass to Collections.sort() or list.sort()

// Lambda comparatorComparator<Player> c = (p1, p2) -> p1.getRanking() - p2.getRanking();// Method reference chainstudents.sort(Comparator.comparing(Student::getName) .thenComparing(Student::getAge));// ReverseComparator.reverseOrder();

Iterators

Iterator Interface

▸Iterable (java.lang) → foreach, iterator()

▸Create: Iterator<T> it = list.iterator();

▸Methods: hasNext() · next() · remove()

▸Forward only. Safe removal. No modification (other than remove).

▸Uses modCount vs expectedModCount → ConcurrentModificationException on mismatch

▸remove() syncs expectedModCount so it's safe

ConcurrentModificationException Fix

▸Use iterator.remove() — not list.remove()

▸Or use list.removeIf(i → i == 2)

ListIterator

▸For List types (ArrayList, LinkedList, Vector, Stack). Extends Iterator.

▸Bidirectional. No current element — cursor between prev & next (n+1 positions)

▸Forward: hasNext() next() nextIndex()

▸Backward: hasPrevious() previous() previousIndex()

▸Both deletion & modification allowed

Fail-Fast vs Fail-Safe

Property	Fail-Fast	Fail-Safe
CME thrown	✓ Yes	✗ No
Works on	Original collection	Clone/snapshot
Reflects changes	✓	✗
Overhead	Low	Copy overhead
Example	`ArrayList`	`CopyOnWriteArrayList`

Spliterator

▸Designed for parallel processing of streams

Spliterator<String> s1 = names.spliterator();Spliterator<String> s2 = s1.trySplit();if (s2 != null) s2.forEachRemaining(System.out::println); s1.forEachRemaining(System.out::println);

Sequenced Collections

New Interfaces (JDK 21)

Interface	Extends	Implemented by
`SequencedCollection`	`Collection`	List, Deque, SequencedSet
`SequencedSet`	Set + SequencedCollection	SortedSet, LinkedHashSet
`SequencedMap`	`Map`	LinkedHashMap, TreeMap

Methods Added

addFirst()addLast()getFirst()getLast()removeFirst()removeLast()reversed()firstEntry()lastEntry()pollFirstEntry()pollLastEntry()putFirst()putLast()

Vector (Legacy)

▸JDK 1.0. Synchronizes every individual method → coarse-grained locking

▸Single-threaded apps still pay lock overhead → extremely slow

⚠️ Avoid. Use modern alternatives below.

Collections.synchronizedList()

▸Wraps ArrayList with a global lock. Better API than Vector.

▸Still single global lock. Has fail-fast iterators.

▸Use when writes are frequent and true concurrency isn't critical

Concurrent Collections

ConcurrentHashMap

▸Segment-level locking (not whole map) → parallel access

▸Implements ConcurrentNavigableMap + Serializable

Param	Default	Effect
initialCapacity	16	Initial array size
loadFactor	0.75	Resize threshold
concurrencyLevel	16	Expected concurrent writers

▸Resize when size > capacity × loadFactor

▸No null keys or values — ambiguity between absent key vs null value

▸size() is O(n) — sums counters across segments

▸High throughput, but higher memory overhead

▸vs HashTable: every op locks whole table → slow

▸vs synchronizedMap: global lock → no true parallelism

ConcurrentHashMap Constructors

new ConcurrentHashMap<>()new ConcurrentHashMap<>(initialCapacity)new ConcurrentHashMap<>(cap, loadFactor)new ConcurrentHashMap<>(cap, lf, concurrencyLevel)new ConcurrentHashMap<>(existingMap)

CopyOnWriteArrayList

▸Best for many reads, few writes

▸No lock on get(). Fail-safe iterators (work on snapshot)

▸On write: create copy → mutate → replace internal pointer

▸Iterator always points to immutable snapshot at creation time

Blocking Queue Family

▸ArrayBlockingQueue — bounded, array-backed

▸LinkedBlockingQueue — optionally bounded, linked

▸PriorityBlockingQueue — unbounded, priority-ordered

▸Wait when empty (retrieve) · Wait when full (insert)

Thread-Safety Comparison

Structure	Strategy	Performance
`Vector`	Method-level sync	Very slow
`synchronizedList`	Global lock	Slow
`CopyOnWriteArrayList`	Copy-on-write	Fast reads
`ConcurrentHashMap`	Segment lock	Fast
`HashTable`	Table-level lock	Slow

JAVA COLLECTIONS FRAMEWORK · JDK 8 – 21 · QUICK REFERENCE