Comprehensive Overview of the Java Collections Framework

Arrays

Array is a Java‑specific array. It is very useful when you know the number of elements to process. java.util.Arrays contains many utility methods:

Arrays.asList: converts an Array to a List , which can be used as a constructor argument for other collection types.

Arrays.binarySearch: quickly searches a sorted array or a sub‑range.

Arrays.copyOf: expands an array’s capacity without changing its contents.

Arrays.copyOfRange: copies the whole array or a part of it.

Arrays.deepEquals, Arrays.deepHashCode, Arrays.equals/hashCode: advanced versions that support operations on sub‑arrays.

Arrays.equals: compares two arrays for content equality; it should be used instead of the default equals method, which only compares references.

Arrays.fill: fills the whole array or a portion with a given value.

Arrays.hashCode: computes a hash based on the array’s contents (the default hashCode() of an array object is not useful).

Arrays.sort: sorts the entire array or a sub‑range; a comparator can be supplied for object arrays.

Arrays.toString: returns a string representation of the array’s contents.

To copy an entire array or a part of it to another array you can use System.arraycopy, which copies a specified number of elements from a source position to a destination array. In some cases, using a ByteBuffer bulk copy can be faster.

All collections can be converted to an array with T[] Collection.toArray(T[] a). A typical usage is: return coll.toArray(new T[coll.size()]); This method allocates an array large enough to hold all elements, so the toArray call does not need to allocate additional space on return.

Single‑Threaded Collections

This section introduces collections that do not support multithreading. They reside in the java.util package. Some were introduced in Java 1.0 (now deprecated) and many were re‑released in Java 1.4. Enumerated collections were re‑released in Java 1.5, and from that version onward all collections support generics. PriorityQueue was added in Java 1.5, and the last non‑thread‑safe collection, ArrayDeque, was re‑released in Java 1.6.

List

ArrayList : the most commonly used List implementation. It stores the size and elements in an array, expands automatically, provides O(1) random access, cheap appends at the tail, but costly inserts at the head because all subsequent elements must be shifted.

LinkedList : implements Deque ; each node holds references to the previous and next node, giving linear‑time access and updates. For efficient linked‑list code you can use ListIterators . If you only need queue semantics, consider ArrayDeque instead.

Vector : a synchronized version of ArrayList ; nowadays it is usually replaced by ArrayList .

Queues/Deques

ArrayDeque : implements Deque using a circular buffer. Unlike LinkedList , it does not implement List , so it cannot be used when list‑style indexed access is required. It generates less garbage during expansion.

Stack : a legacy LIFO stack; it is deprecated and should be replaced by a Deque such as ArrayDeque .

PriorityQueue : a priority‑ordered queue that returns the smallest element via poll/peek/remove/element . It also implements Iterable , so iteration does not guarantee sorted order. It is often more convenient than TreeSet for sorted collections.

Maps

HashMap : the most common Map implementation; it simply maps keys to values and provides constant‑time basic operations.

EnumMap : uses an enum as the key type; internally it stores values in an array, offering higher performance than HashMap for a fixed set of keys.

Hashtable : the synchronized predecessor of HashMap ; modern code should use HashMap instead.

IdentityHashMap : compares keys by reference equality ( == ) instead of equals() . Useful for algorithms that need identity‑based lookup, such as graph traversal.

LinkedHashMap : combines a HashMap with a linked list to preserve insertion order; it is the most memory‑intensive map in the JDK.

TreeMap : a red‑black tree implementation that keeps keys sorted according to their natural order or a supplied comparator. It implements NavigableMap , providing methods to access entries before or after a given key, similar to SQL’s BETWEEN operator.

WeakHashMap : stores keys as WeakReference objects, allowing them to be garbage‑collected when no strong references exist; useful for caches.

Sets

HashSet : a Set backed by a HashMap ; all elements are dummy objects, giving hash‑set performance but higher memory usage.

EnumSet : a high‑performance Set for enum types, implemented either as a single long (up to 64 values) or as a long[] for larger enums.

BitSet : a set of bits that efficiently stores dense integer values using a long[] backing array.

LinkedHashSet : a Set that preserves insertion order, implemented on top of LinkedHashMap .

TreeSet : a sorted Set backed by a TreeMap ; the only sorted set in the single‑threaded section.

java.util.Collections

Just as java.util.Arrays provides utilities for arrays, java.util.Collections offers utilities for collections.

The first group of methods returns various collection views:

checkedCollection / checkedList / checkedMap / checkedSet / checkedSortedMap / checkedSortedSet – enforce runtime type checking and throw ClassCastException on illegal insertions.

emptyList / emptyMap / emptySet – return immutable empty collections.

singleton / singletonList / singletonMap – return a collection containing a single element.

synchronizedCollection / synchronizedList / synchronizedMap / synchronizedSet / synchronizedSortedMap / synchronizedSortedSet – provide thread‑safe wrappers (note that compound operations like put are not atomic).

unmodifiableCollection / unmodifiableList / unmodifiableMap / unmodifiableSet / unmodifiableSortedMap / unmodifiableSortedSet – return read‑only collections.

The second group contains additional useful operations:

addAll – adds all elements of an array or another collection.

binarySearch – same as Arrays.binarySearch but works on lists.

disjoint – checks whether two collections have no elements in common.

fill – replaces all elements in a collection with a given value.

frequency – counts how many times a given element appears.

indexOfSubList / lastIndexOfSubList – locate the first/last occurrence of a sub‑list, analogous to String.indexOf .

max / min – return the maximum or minimum element according to natural order or a comparator.

replaceAll – replaces each occurrence of a specified element with another.

reverse – reverses the order of elements; when used after sorting, consider Collections.reverseOrder as the comparator.

rotate – rotates elements by a given distance.

shuffle – randomly permutes a list; a custom Random , ThreadLocalRandom , or SecureRandom can be supplied.

sort – sorts a list according to natural order or a supplied comparator.

swap – swaps the positions of two elements.

Concurrent Collections

This section covers thread‑safe collections in the java.util.concurrent package. Their operations are designed to be atomic, preventing inconsistent state during compound actions such as add‑then‑update.

Most concurrent collections were introduced in Java 1.5. ConcurrentSkipListMap, ConcurrentSkipListSet, and LinkedBlockingDeque were added in Java 1.6, while Java 1.7 added ConcurrentLinkedDeque and LinkedTransferQueue.

Lists

CopyOnWriteArrayList : creates a fresh copy of the underlying array on each mutating operation; suitable for scenarios with many reads and few writes, such as listener lists.

Queues/Deques

ArrayBlockingQueue : a bounded blocking queue backed by an array; producers block when the queue is full.

ConcurrentLinkedDeque / ConcurrentLinkedQueue : unbounded lock‑free queues based on linked nodes and CAS operations; consumers must keep up with producers to avoid memory exhaustion.

DelayQueue : an unbounded queue of Delayed elements; an element can be taken only after its delay has expired. Use it for delayed‑task scheduling instead of implementing your own.

LinkedBlockingDeque / LinkedBlockingQueue : optionally bounded queues backed by linked nodes; they use ReentrantLock for concurrency control.

LinkedTransferQueue : an unbounded queue that supports a transfer operation, allowing a producer to hand off an element directly to a waiting consumer without storing it.

PriorityBlockingQueue : an unbounded version of PriorityQueue for concurrent use.

SynchronousQueue : a zero‑capacity queue where each insert must wait for a corresponding remove; can be replaced by Exchanger when only queue semantics are needed.

Maps

ConcurrentHashMap : provides concurrent get operations and configurable concurrency level for put via internal partitioning; only the affected partition is locked during updates.

ConcurrentSkipListMap : a thread‑safe ConcurrentNavigableMap based on a skip‑list, effectively a concurrent version of TreeMap .

Sets

ConcurrentSkipListSet : a thread‑safe Set backed by ConcurrentSkipListMap .

CopyOnWriteArraySet : a set backed by CopyOnWriteArrayList ; ideal for read‑heavy scenarios.

Further Reading

Java primitive‑type collection library Trove – a library for collections of primitive types.

Java memory usage of common data types (1): memory footprints of enums, EnumMap, EnumSet, BitSet, ArrayList, LinkedList, ArrayDeque.

Java memory usage of common data types (2): memory footprints of HashMap, HashSet, LinkedHashMap, LinkedHashSet, TreeMap, TreeSet, and JDK 7 PriorityQueue, with Trove alternatives.

Recommended Books

Cay S. Horstmann, Core Java Volume I – Fundamentals (9th Edition), Chapter 13 covers Java collections.

Naftalin & Wadler, Java Generics and Collections, Part 2 (Chapters 10‑17) focuses on collections.

Goetz et al., Java Concurrency in Practice, Chapter 5 discusses the concurrent collections introduced in Java 1.5.

Summary Table

Single‑threaded

Concurrent

Lists ArrayList – array‑backed list LinkedList – not recommended Vector – deprecated CopyOnWriteArrayList – rarely updated, good for iteration

Queues / deques ArrayDeque – array‑backed deque Stack – deprecated PriorityQueue – sorted read access ArrayBlockingQueue – bounded blocking queue ConcurrentLinkedDeque / ConcurrentLinkedQueue – unbounded lock‑free queues DelayQueue – delayed elements LinkedBlockingDeque / LinkedBlockingQueue – optionally bounded linked queues LinkedTransferQueue – transfer without storage PriorityBlockingQueue – concurrent priority queue SynchronousQueue – zero‑capacity queue (or use Exchanger)

Maps HashMap – general purpose EnumMap – enum keys Hashtable – deprecated IdentityHashMap – reference equality LinkedHashMap – insertion order TreeMap – sorted keys WeakHashMap – cache‑friendly ConcurrentHashMap – general concurrent map ConcurrentSkipListMap – sorted concurrent map

Sets HashSet – general set EnumSet – enum set BitSet – dense integer set LinkedHashSet – insertion order TreeSet – sorted set ConcurrentSkipListSet – sorted concurrent set CopyOnWriteArraySet – read‑heavy set