Collections Architecture: ArrayList, HashSet, HashMap & Tree Structures
Deconstruct the Java Collections Framework. Understand array resizing, open-addressing vs separate chaining, and red-black tree bin conversion.
By the end, you’ll be able to…
- Map the core Collection hierarchy: List, Set, Queue, Deque, and Map.
- Contrast ArrayList dynamic resizing (1.5x amortized O(1)) with LinkedList overhead.
- Understand HashMap internals: hashing, bucket collisions, and Java 8 treeification.
01The Core Collection Hierarchy
The Java Collections Framework (JCF) provides a unified architecture for storing and manipulating groups of objects. At the root of the collection hierarchy is java.util.Collection, which bifurcates into List (ordered, indexed collections allowing duplicates), Set (unordered or sorted collections with strictly unique elements), and Queue/Deque (FIFO, LIFO, and double-ended buffers).
Notice that java.util.Map does NOT implement Collection! Maps represent key-value mappings with distinct mathematical characteristics (unique keys mapping to arbitrary values), possessing their own independent interface hierarchy (HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap).
+---------------------------------------------------+| Java Collections Framework |+---------------------------------------------------+| [Iterable] || ^ || [Collection] || / | \ || [List] [Set] [Queue] [Map] || ArrayList HashSet ArrayDeque HashMap|| LinkedList TreeSet PriorityQ TreeMap|02ArrayList Internals vs LinkedList
ArrayList is backed by a contiguous Object[] array. When initialized without capacity, it starts empty and expands to 10 elements on first insertion. When capacity is exceeded, ArrayList grows by 50% (newCapacity = oldCapacity + (oldCapacity >> 1)) by allocating a new array and performing a hardware-optimized System.arraycopy.
Because memory is contiguous, ArrayList provides instant O(1) random access (get(i)) and exceptional CPU cache locality. LinkedList, in contrast, allocates a separate Node object on the heap for every single element with two 8-byte reference pointers, destroying CPU cache performance and consuming 4x more memory. In 99.9% of production scenarios, ArrayList completely outperforms LinkedList.
03HashMap Internals and Treeification
A HashMap is an array of hash buckets (Node<K, V>[] table) initialized to size 16 with a load factor of 0.75. When put(key, value) is called, the key's hashCode() is passed through a bit-shifting spread function and mapped to a bucket index: index = (n - 1) & hash.
When two keys hash to the same bucket (collision), HashMap uses Separate Chaining. In Java 8+, if a single bucket exceeds 8 entries (TREEIFY_THRESHOLD) and the total table capacity is at least 64, the bucket is transformed from a singly linked list into a balanced Red-Black Tree (TreeNode). This guarantees that worst-case lookup degrades to O(log N) rather than O(N), defending against Hash Collision DoS attacks.
+---------------------------------------------------+| HashMap Bucket Architecture |+---------------------------------------------------+| Table Index 0: [ Node A ] -> [ Node B ] (List) || Table Index 1: null || Table Index 2: [ Red-Black Balanced Tree ] || (Converted when chain > 8 nodes!) |+---------------------------------------------------+04Why This Matters in Production
In enterprise Java, choosing the wrong collection or forgetting initial sizing causes severe CPU and memory pressure. If you know you will store 1,000,000 items in a HashMap, instantiating new HashMap<>() will trigger over 15 expensive array rehashings as the map expands from 16 to 1M.
By pre-sizing the map: new HashMap<>((int) (1_000_000 / 0.75f) + 1), all rehashes are eliminated, cutting memory allocations and latency by over 60%.
The ideas worth keeping.
- ArrayList provides O(1) random access and superior CPU cache locality over LinkedList.
- HashMap treeifies buckets with >8 collisions into Red-Black Trees for O(log N) worst-case lookup.
- Always pre-size collections when the expected item count is known to prevent costly resizing.
Make it yours.
Type and test your code right here in the interactive workspace. Run your solution, check the output, and compare with the worked guide when ready.
Exercise 1: Pre-sizing Collections Calculator
Write a helper method getOptimalMapCapacity(int expectedEntries) that calculates the exact capacity needed to hold expectedEntries without triggering a rehash.
Explore a worked solution
public static int getOptimalMapCapacity(int expectedEntries) { if (expectedEntries < 3) return expectedEntries + 1; return (int) Math.ceil(expectedEntries / 0.75f);}Accounting for the default 0.75 load factor prevents the internal table from exceeding the resize threshold.
Exercise 2: Proper equals() and hashCode() Contract
Explain why two objects that evaluate as equal via .equals(other) must return identical hashCode() values.
Explore a worked solution
HashMap uses hashCode() to determine bucket index. If two equal objects have different hash codes, the map will search the wrong bucket during get(), failing to find the entry.Failing the hashCode contract causes duplicate keys and lookup failures in hash-based collections.
What stayed with you?
Check the ideas while they’re fresh. Your answers stay in this page and feedback appears as you go.
Exercise 1: Pre-sizing Collections Calculator
Write a helper method getOptimalMapCapacity(int expectedEntries) that calculates the exact capacity needed to hold expectedEntries without triggering a rehash.
Build successful. (Java 15) [Process exited normally]
Keep exploring.
The official references behind this lesson, when you want a second angle or the full details.
One lesson closer.
Reading is a start. Trying it yourself makes the connection.