Master Java Collections: From ArrayList to ConcurrentHashMap Explained

Overview of the Collection Framework

The collection framework is a standardized architecture for storing and manipulating groups of objects. It consists of three core parts: external interfaces that define abstract data types, concrete implementations of those interfaces, and reusable algorithms (e.g., search, sort) that operate on the collections.

Key Benefits

By providing ready‑made data structures and algorithms, the framework lets developers focus on business logic rather than low‑level implementation details, improves code readability, and enhances performance.

Collections vs. Arrays

Arrays have fixed length; collections are dynamically resizable.

Arrays can store primitive types and references; collections store only reference types.

All elements in an array share the same type; a collection can hold heterogeneous objects.

Core Collection Types

List

Ordered, index‑based containers that allow duplicate elements and multiple null values. Common implementations:

ArrayList : backed by a plain Object array; provides fast random access (O(1)).

LinkedList : doubly‑linked list; efficient insertions/removals at ends or middle (O(1) for node link changes).

Vector : synchronized ArrayList; thread‑safe but slower.

Set

Unordered containers that enforce uniqueness (at most one null). Common implementations:

HashSet : built on HashMap; offers constant‑time basic operations.

LinkedHashSet : preserves insertion order using a linked hash map.

TreeSet : backed by a red‑black tree; maintains sorted order.

Map

Key‑value containers where keys are unique. Important implementations:

HashMap : array + linked list (or red‑black tree when a bucket exceeds 8 entries); not thread‑safe; allows one null key.

TreeMap : red‑black tree; provides sorted key iteration.

Hashtable : synchronized version of HashMap; disallows null keys/values.

ConcurrentHashMap : high‑concurrency map; JDK 1.7 uses segmented locks, JDK 1.8 uses node‑level CAS and fine‑grained synchronization; does not allow null keys/values.

Thread‑Safety and Performance

Collections such as Vector, Hashtable, and Collections.synchronizedList provide built‑in synchronization but incur overhead. ConcurrentHashMap achieves better scalability by locking only a portion of the bucket array (segment) in JDK 1.7 or by using lock‑free techniques in JDK 1.8.

Fail‑Fast Iteration

Iterators detect structural modifications and throw ConcurrentModificationException. To safely remove elements while iterating, use Iterator.remove(). ListIterator extends Iterator with bidirectional traversal and element‑addition capabilities.

Choosing an Iteration Strategy

If a List implements RandomAccess (e.g., ArrayList), a simple indexed for loop is fastest. Otherwise (e.g., LinkedList), prefer Iterator or enhanced for‑each loops.

Underlying Data Structures

ArrayList and Vector store elements in a contiguous array; they grow by allocating a larger array and copying existing elements. LinkedList uses a doubly‑linked list. HashSet and HashMap use an internal array of buckets; each bucket holds a linked list or, when the list length exceeds 8, a red‑black tree ( TreeNode). TreeMap and TreeSet are pure red‑black trees.

HashMap Internals

When inserting, the key’s hashCode() is transformed by a two‑step perturbation function ( h ^ (h >>> 16)) to produce a hash value. The bucket index is computed as hash & (capacity‑1), which works efficiently because capacity is always a power of two.

Collision handling:

Initially, entries with the same bucket are linked in a singly‑linked list.

If a bucket’s list length exceeds TREEIFY_THRESHOLD (8), it is converted into a red‑black tree, reducing lookup from O(n) to O(log n).

Resizing occurs when size > threshold (threshold = capacity × loadFactor). The array size doubles, and existing entries are redistributed either to the same index or to index + oldCapacity, preserving order for linked‑list buckets.

Red‑Black Tree Basics

A red‑black tree is a self‑balancing binary search tree with the following properties: every node is red or black; the root is black; all leaves (null) are black; red nodes cannot have red children; every path from a node to its descendant leaves contains the same number of black nodes. This guarantees O(log n) operations.

When to Use HashMap vs. TreeMap

Use HashMap for fastest insert, delete, and lookup when ordering is not required. Use TreeMap when you need a sorted view of keys.

Custom Objects as Map Keys

Any class can serve as a key, but you must override both equals() and hashCode(). Making the key class immutable is recommended to keep hash codes stable.

Summary of Map Implementations

HashMap : non‑synchronized, allows null key/value, uses array + linked list/red‑black tree.

Hashtable : synchronized, disallows null, similar internal structure to pre‑JDK 1.8 HashMap.

ConcurrentHashMap : high‑concurrency, no null, segment‑locking (JDK 1.7) or CAS‑based (JDK 1.8).

Additional Utilities

The Collections utility class provides static methods for sorting, searching, making collections unmodifiable ( Collections.unmodifiableCollection), and synchronizing collections ( Collections.synchronizedList).