Java collections framework
| Company type | Software framework |
|---|---|
| Industry | Software development |
| Founded | 1998 |
| Founder | Joshua Bloch |
| Parent | Sun Microsystems |
The Java collections framework consists of a suite of classes and interfaces that implement widely reusable collection data structures.
Although it is referred to as a framework, it operates more like a library, offering interfaces that define collections alongside classes that provide their implementations.
Distinctions from Arrays
Both Collections and arrays store references to objects and manage groups of them. However, unlike arrays, Collections do not require a fixed size beforehand; they automatically expand or contract as elements are added or removed.
Primitive data types such as int, long, or double cannot be stored directly in Collections. Instead, wrapper classes like , , or are utilized.
While arrays are covariant, collections are generic and invariant. This generic structure enhances type safety by catching errors during compilation rather than at runtime. For instance, assigning a Long[] array to an Object[] variable allows incompatible types to be inserted at runtime, potentially causing an ArrayStoreException. Conversely, declaring a Collection<Object> as an ArrayList<Long> results in a compile-time error, enabling earlier error detection. Developers can address this by creating the collection with matching types or by using the diamond operator introduced in Java SE 7.
Moreover, collections employ reified generics, which arrays lack, thereby improving type safety and consistency across Java programs.
Historical Background
Prior to JDK 1.2, Java offered only a limited set of data structure classes without an integrated collections framework. Object grouping was handled primarily through arrays, Vector, and Hashtable, which did not provide extensibility or standardized interfaces.
To fulfill the demand for reusable collection data structures, several independent frameworks appeared, notably Doug Lea's Collections package and ObjectSpace's Generic Collection Library (JGL), which aimed for compatibility with the C++ Standard Template Library (STL).
The collections framework, chiefly designed by Joshua Bloch, debuted in JDK 1.2, incorporating many concepts from Doug Lea's package, which was later deprecated. Sun Microsystems chose not to adopt the JGL model to keep the framework concise and avoid emphasizing C++ compatibility.
Doug Lea subsequently developed a concurrency package introducing new Collection-related classes. An updated version of these utilities was incorporated into JDK 5.0 under JSR 166.
Framework Architecture
Nearly all Java collections implement the Template:Javadoc:SE interface, which outlines fundamental collection operations.
This interface provides methods such as for adding elements and for removing them. The method converts the collection into an array of Objects, while determines if a specific element exists within the collection.
As a subinterface of Template:Javadoc, the Collection interface supports iteration through the method, enabling its use in enhanced for-each loops. All collection implementations provide an Template:Javadoc to navigate through their elements.
Being generic allows Collections to store objects of any specified type without requiring casting. For example, a Collection<String> holds only String instances. The generic parameter defines the element type stored within the collection, promoting type safety and minimizing runtime exceptions.
Categories of collections
Fundamental collection categories encompass Queues, Maps, Lists, and Sets.
Queues organize elements in the sequence they are inserted, making them ideal for use cases like waiting queues. Their primary interface is Queue.
Maps maintain associations between keys and values to facilitate rapid retrieval, with keys often representing identifiers such as ID cards. Their core interface is Map.
Lists support ordered sequences allowing repeated entries.
Sets represent unordered groups that hold only distinct elements. Their foundational interface is Set.
List interface
Within the collections framework, lists are characterized by the Template:Javadoc interface, which models a versatile array-like data structure. Elements maintain a defined order, duplicates are permitted, and items can be inserted or located at specified indexes.
Implementations of List
Concrete implementations of List include and its derived classes, along with .
AbstractList class
Direct descendants of comprise , , and . The class offers a skeletal implementation that eases the creation of custom List variants.
ARRAYLIST CLASSES
The Template:Javadoc realizes the List interface through a resizable array structure, internally rearranging elements to optimize list operations.
LinkedList class
The Template:Javadoc organizes elements as nodes linked via references to both preceding and succeeding nodes, facilitating efficient insertions and deletions by pointer adjustments.
Vector class
serves as a synchronized list implementation, with directly inheriting from it. This approach contravenes the composition over inheritance principle because a vector conceptually differs from a stack; employing composition would have been more appropriate.
Stack class
The Template:Javadoc extends , introducing five operations tailored for stack behavior. It implements last-in-first-out (LIFO) semantics through methods such as for pushing and for popping elements. Additional functionalities include to peek at the top element, to verify emptiness, and to find elements relative to the stack's peak. The Stack class is a widely adopted Java stack model commonly utilized in enterprise applications requiring LIFO processing.
CopyOnWriteArrayList class
The CopyOnWriteArrayList inherits directly from Object and offers thread-safe operation without extensive synchronization overhead. It is well-suited for situations where strict synchronization is unnecessary, thereby enhancing CPU efficiency on multi-core systems. Nevertheless, if any method alters a static field accessed concurrently by multiple threads, synchronization remains essential, making concurrency utilities like CopyOnWriteArrayList unsuitable in such contexts.
Queue interfaces
The Queue interface defines a first-in-first-out (FIFO) structure where elements are enqueued at the rear and dequeued from the front. Implementing classes include LinkedList, ArrayDeque, and PriorityQueue.
AbstractQueue Class
The AbstractQueue class functions as a foundational framework for queue implementations. Its direct descendants encompass ArrayBlockingQueue, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, and PriorityBlockingQueue. Conversely, classes such as ArrayDeque and ConcurrentLinkedDeque inherit from AbstractCollection rather than AbstractQueue.
PriorityQueue Class
The PriorityQueue class adheres to the Queue interface but prioritizes elements based on their priority instead of their insertion sequence. This priority is established either through the elements' Comparable interface or via a comparator supplied during instantiation. Internally, it relies on a heap data structure to preserve order, enabling efficient processing based on priority.
ConcurrentLinkedQueue Class
The java.util.concurrent.ConcurrentLinkedQueue class both extends and implements the Queue interface.
Designed for thread-safe operations, ConcurrentLinkedQueue guarantees that any element added is safely published, ensuring consistent visibility of the element’s state across all threads. Safe publication involves synchronization mechanisms that make an object's state immediately accessible to multiple threads without inconsistency.
BlockingQueue Interface
The Template:Javadoc interface is a specialized extension of the Queue interface.
It has direct sub-interfaces such as and . Unlike standard queues, operations on a BlockingQueue may block: attempts to remove elements can wait if none are present, and insertion operations may block when capacity constraints are reached. This interface introduces methods like which retrieves and removes the queue's head, waiting if necessary until an element becomes available.
Double-ended Queue (Deque) Interfaces
The interface builds upon the interface to create a double-ended queue structure. This design permits adding and removing elements from both the front and rear ends, unlike a traditional where such operations are restricted to opposite ends only. A supports iteration in both directions and is implemented by classes including java.util.ArrayDeque and java.util.LinkedList.
LinkedList Class
LinkedList implements both the List and Queue interfaces, along with the Template:Javadoc interface, thereby offering enhanced support for double-ended queue functionality.[1]
ArrayDeque Class
ArrayDeque, implemented as an array-backed structure, supports the Queue interface as well as the Template:Javadoc interface.[1]
BlockingDeque Interface
The Template:Javadoc:SE interface extends java.util.concurrent.BlockingQueue, integrating blocking queue behavior with the double-ended flexibility of a Deque. It facilitates timed insertions and removals at both ends of the deque.[2]
Set interfaces
The Template:Javadoc interface in Java represents a collection type that forbids duplicate entries and does not guarantee any particular order, which means elements cannot be accessed by their position index. Implementations of this interface include Template:Javadoc, Template:Javadoc, and Template:Javadoc.
Implementations of the Set interface
The Set interface has multiple implementations, among them are AbstractSet and its derived classes, in addition to the final static inner class ConcurrentHashMap.KeySetView<K,V>, which uses generic types K and V.
AbstractSet
AbstractSet offers a foundational implementation for the Set interface.
Its direct subclasses include ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, and TreeSet.
EnumSet class
Extending from AbstractSet, the EnumSet class provides only static factory methods without any public constructors. One such method is EnumSet.of(), which generates instances based on specified parameters.
Within Java SE8 OpenJDK, there are two internal classes: RegularEnumSet and JumboEnumSet. Should the performance advantage of RegularEnumSet diminish for small enum types, it may be deprecated without affecting the overall Java Collection Framework.
The EnumSet class serves as an improved substitute for the traditional use of bit fields to represent sets of enum constants. Previously, developers employed the "int enum pattern," where constants were assigned powers of two to facilitate bitwise operations like OR for combining sets.
However, bit fields lack readability and do not allow iteration over their elements. By contrast, an EnumSet enhances type safety by implementing the Set interface without relying on bitwise manipulation. Its static factory methods such as EnumSet.of() simplify instance creation.
Since its introduction, the use of bit fields for enum sets has largely been replaced by EnumSet.
HashSet class
HashSet stores elements using a hash table structure, specifically backed by a Template:Javadoc, ensuring duplicates are prevented.
LinkedHashSet class
The java.util.LinkedHashSet subclass extends HashSet by preserving a doubly linked list that maintains insertion order, thereby providing consistent iteration order.
CopyOnWriteArraySet class
This class offers a concurrent alternative to synchronized sets by avoiding synchronization during iteration, similar to how it is applied in concurrent lists. However, it is not appropriate when strict synchronization guarantees are necessary.
SortedSet interface
Extending from Set, the java.util.SortedSet interface arranges elements according to their natural ordering via the Comparable interface or through a Comparator provided at construction time. It supports operations such as retrieving the first and last elements and generating subsets within specified ranges. The java.util.TreeSet class provides an implementation of this interface.
The Template:Javadoc interface builds upon SortedSet by introducing additional methods such as , , , and to locate elements adjacent to a specified value. It also includes functionality for iterating in descending order. This interface is implemented by java.util.TreeSet.
TreeSet class
The java.util.TreeSet class is backed by a red–black tree structure provided by Template:Javadoc. This data structure prevents duplicate entries and allows TreeSet to fulfill the contract of the Template:Javadoc interface.
ConcurrentSkipListSet class
acts as a thread-safe alternative to synchronized implementations, such as those created by synchronizing a .
Map interfaces
In Java, the concept of maps is formalized through the Template:Javadoc interface.
Map interface implementations
Maps link keys to corresponding values, providing versatility: when an element's hash code is used as a key, the map behaves similarly to a Set, whereas numeric keys give it list-like characteristics.
Prominent implementations of the Map interface include Template:Javadoc, Template:Javadoc, and Template:Javadoc.
AbstractMap class
provides a foundational partial implementation for maps. Its immediate subclasses encompass , , , , , and .
EnumMap
is a specialization of that achieves performance on par with ordinal-indexed arrays by internally utilizing an array. This design combines the type safety of a with the speed typically associated with arrays.
HashMap
employs a hash table data structure where keys' hash codes determine the bucket placement of entries.
LinkedHashMap
extends by maintaining a doubly linked list of its entries, which preserves the order in which elements were inserted. It includes a protected removeEldestEntry method invoked during each put, enabling automatic eviction of the oldest entry if overridden to return true.
TreeMap
differs from and by using a red–black tree for storage. Here, keys act as node identifiers, with each node linking to the associated Map entry.
ConcurrentHashMap
is similar to but adopts a distinct locking mechanism designed for enhanced concurrency and scalability. Instead of synchronizing all methods with a single lock, it utilizes lock striping, which applies finer-grained locks to allow more concurrent access.
ConcurrentSkipListMap class
provides a concurrent counterpart to synchronized implementations, analogous to . It replaces usage of a wrapped via the method.
SortedMap interface
The Template:Javadoc interface extends java.util.Map, defining maps whose keys are sorted either by their natural ordering through compareTo() or by a comparator specified at creation. It offers methods such as , , and for accessing subsets of keys within defined ranges. The interface is implemented by java.util.TreeMap.
The Template:Javadoc interface builds upon java.util.SortedMap by offering functionality to locate the nearest key or entry in either ascending or descending order. It allows the map to be viewed in reverse sequence and supports the creation of iterators that traverse in reverse. This interface is implemented by java.util.TreeMap.
ConcurrentMap Interface
Extending java.util.Map, the Template:Javadoc interface delivers a thread-safe map solution introduced with Java Collections Framework version 1.5.
Enhancements to the Java Collections Framework
The Apache Commons Collections library supplements the Java collections framework by introducing additional collection types such as bags and bidirectional maps, along with tools for performing unions and intersections.
Additionally, Google provides its own set of collection utilities through the Guava libraries.