The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures (collections).
Although referred to as a framework, it works in a manner of a library. The collections framework provides both interfaces that define various collections and classes that implement them.
<code>Collection</code>s and arrays are similar in that they both hold references to objects and they can be managed as a group. However, unlike arrays, <code>Collection</code>s do not need to be assigned a certain capacity when instantiated. <code>Collection</code>s can grow and shrink in size automatically when objects are added or removed.
<code>Collection</code>s cannot hold primitive data types such as <code>int</code>, <code>long</code>, or <code>double</code>. Instead, <code>Collection</code>s can hold wrapper classes such as , , or .
<code>Collection</code>s are generic and hence invariant, but arrays are covariant. This can be considered an advantage of generic objects such as when compared to arrays, because under circumstances, using the generic instead of an array prevents run time exceptions by instead throwing a compile-time exception to inform the developer to fix the code. For example, if a developer declares an object, and assigns the object to the value returned by a new instance with a certain capacity, no compile-time exception will be thrown. If the developer attempts to add a to this object, the java program will throw an . On the other hand, if the developer instead declared a new instance of a as , the Java compiler will (correctly) throw a compile-time exception to indicate that the code is written with incompatible and incorrect type, thus preventing any potential run-time exceptions.The developer can fix the code by instantianting as an object. If the code is using Java SE7 or later versions, the developer can instantiate as an object by using the diamond operator
<code>Collection</code>s are generic and hence reified, but arrays are not reified.
Collection implementations in pre-JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections framework. The standard methods for grouping Java objects were via the array, the <code>Vector</code>, and the <code>Hashtable</code> classes, which unfortunately were not easy to extend, and did not implement a standard member interface.
To address the need for reusable collection data structures, several independent frameworks were developed, the most used being Doug Lea's Collections package, and ObjectSpace Generic Collection Library (JGL), whose main goal was consistency with the C++ Standard Template Library (STL).
The collections framework was designed and developed primarily by Joshua Bloch, and was introduced in JDK 1.2. It reused many ideas and classes from Doug Lea's Collections package, which was deprecated as a result. Sun Microsystems chose not to use the ideas of JGL, because they wanted a compact framework, and consistency with C++ was not one of their goals.
Doug Lea later developed a concurrency package, comprising new Collection-related classes. An updated version of these concurrency utilities was included in JDK 5.0 as of JSR 166.
Most collections in Java that are not maps are derived from the interface. <code>Collection</code> defines the basic parts of all collections.
The interface has the and methods for adding to and removing from a <code>Collection</code> respectively. It also has the method, which converts the <code>Collection</code> into an array of <code>Object</code>s in the <code>Collection</code> (with return type of <code>Object[]</code>). Finally, the method checks if a specified element exists in the <code>Collection</code>.
The <code>Collection</code> interface is a subinterface of , so any <code>Collection</code> may be the target of a for-each statement. (The <code>Iterable</code> interface provides the method used by for-each statements.) All <code>Collection</code>s implement to scan all of the elements in the <code>Collection</code>.
<code>Collection</code> is generic. Any <code>Collection</code> can store any . For example, any implementation of contains objects. No casting is required when using the objects from an implementation of <code>Collection<String></code>. Note that the angled brackets can hold a type argument that specifies which type the <code>Collection</code> holds.
Collection Framework
Collection Framework just holds all the collections (general concept) like list etc, which follows collection interface.
Types of collection
There are several kinds of collections: queues, maps, lists and sets.
Queues allow the programmer to insert items in a certain order and retrieve those items in the same order. An example is a waiting list. The base interfaces for queues are called <code>Queue</code>.
Dictionaries/Maps store references to objects with a lookup key to access the object's values. One example of a key is an identification card. The base interface for dictionaries/maps is called <code>Map</code>.
Lists are finite collections where it can store the same value multiple times.
Sets are unordered collections that can be iterated and contain each element at most once. The base interface for sets is called <code>Set</code>.
Lists are implemented in the collections framework via the interface. It defines a list as essentially a more flexible version of an array. Elements have a specific order, and duplicate elements are allowed. Elements can be placed in a specific position. They can also be searched for within the list.
There are several concrete classes that implement <code>List</code>, including and all of its corresponding subclasses, as well as .
The direct subclasses of class include , and .
is an example of a skeletal implementation, which leverages and combines the advantages of interfaces and abstract classes by making it easy for the developer to develop their own implementation for the given interface.
The class implements the <code>List</code> as an array. Whenever functions specific to a <code>List</code> are required, the class moves the elements around within the array in order to do it.
The class stores the elements in nodes that each have a pointer to the previous and next nodes in the <code>List</code>. The <code>List</code> can be traversed by following the pointers, and elements can be added or removed simply by changing the pointers around to place the node in its proper place.
The class has as its direct subclass. This is an example of a violation of the composition over inheritance principle in the Java platform libraries, since in computer science, a vector is generally not a stack. Composition would have been more appropriate in this scenario.
The class <code>extends</code> class with five operations that allow a <code>Vector</code> to be treated as a <code>Stack</code>. Stacks are created using . The <code>Stack</code> offers methods to put a new object on the <code>Stack</code> (method ) and to get objects from the <code>Stack</code> (method ). A <code>Stack</code> returns the object according to last-in-first-out (LIFO), e.g. the object which was placed latest on the <code>Stack</code> is returned first. <code>java.util.Stack</code> is a standard implementation of a stack provided by Java.
The <code>Stack</code> class represents a last-in-first-out (LIFO) stack of objects. The Stack class has five additional operations that allow a <code>Vector</code> to be treated as a <code>Stack</code>. The usual and operations are provided, as well as a method () to peek at the top item on the <code>Stack</code>, a method to test for whether the <code>Stack</code> is empty (), and a method to search the <code>Stack</code> for an item and discover how far it is from the top (). When a <code>Stack</code> is first created, it contains no items.
The extends the class, and does not extend any other classes. allows for thread-safety without performing excessive synchronization.
In some scenarios, synchronization is mandatory. For example, if a method modifies a static field, and the method must be called by multiple threads, then synchronization is mandatory and concurrency utilities such as should not be used.
However synchronization can incur a performance overhead. For scenarios where synchronization is not mandatory, then the is a viable, thread-safe alternative to synchronization that leverages multi-core processors and results in higher CPU utilization.
The interface defines the queue data structure, which stores elements in the order in which they are inserted. New additions go to the end of the line, and elements are removed from the front. It creates a first-in first-out system. This interface is implemented by <code>java.util.LinkedList</code>, , and .
The direct subclasses of class include , , , , . and .
Note that and both extend but do not extend any other abstract classes such as .
is an example of a skeletal implementation.
The <code>java.util.PriorityQueue</code> class implements <code>java.util.Queue</code>, but also alters it. <code>PriorityQueue</code> has an additional method. Instead of elements being ordered in the order in which they are inserted, they are ordered by priority. The method used to determine priority is either the method in the elements, or a method given in the constructor. The class creates this by using a heap to keep the items sorted.
The <code>java.util.concurrent.ConcurrentLinkedQueue</code> class extends . <code>ConcurrentLinkedQueue</code> implements the interface.
The <code>ConcurrentLinkedQueue</code> class is a thread-safe collection, since for any an element placed inside a , the Java Collection Library guarantees that the element is safely published by allowing any thread to get the element from the collection. An object is said to be safely published if the object's state is made visible to all other thread at the same point in time. Safe publication usually requires synchronization of the publishing and consuming threads.
The interface extends <code>Queue</code>.
The interface has the following direct sub-interfaces: and . works like a regular <code>Queue</code>, but additions to and removals from the <code>BlockingQueue</code> are blocking. If is called on an empty <code>BlockingQueue</code>, it can be set to wait either a specified time or indefinitely for an item to appear in the <code>BlockingQueue</code>. Similarly, adding an item using the method is subject to an optional capacity restriction on the <code>BlockingQueue</code>, and the method can wait for space to become available in the <code>BlockingQueue</code> before returning. <code>BlockingQueue</code> interface introduces a method which removes and gets the head of the <code>BlockingQueue</code>, and waits until the <code>BlockingQueue</code> is no longer empty if required.
The interface extends the interface. creates a double-ended queue. While a regular only allows insertions at the rear and removals at the front, the allows insertions or removals to take place both at the front and the back. A is like a that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The interface is implemented by <code>java.util.ArrayDeque</code> and <code>java.util.LinkedList</code>.
<code>LinkedList</code>, of course, also implements the <code>List</code> interface and can also be used as one. But it also has the <code>Queue</code> methods. <code>LinkedList</code> implements the interface, giving it more flexibility.
<code>ArrayDeque</code> implements the <code>Queue</code> as an array. Similar to <code>LinkedList</code>, <code>ArrayDeque</code> also implements the interface.
The interface extends <code>java.util.concurrent.BlockingQueue</code>. is similar to . It provides the same methods for insertion and removal with time limits for waiting for the insertion or removal to become possible. However, the interface also provides the flexibility of a <code>Deque</code>. Insertions and removals can take place at both ends. The blocking function is combined with the <code>Deque</code> function.
Java's interface defines the <code>Set</code>. A <code>Set</code> can't have any duplicate elements in it. Additionally, the <code>Set</code> has no set order. As such, elements can't be found by index. <code>Set</code> is implemented by , , and .
There are several implementations of the Set interface, including and its subclasses, and the final static inner class (where and are formal type parameters).
======== is a skeletal implementation for the interface.
Direct subclasses of include , , , and .
The class extends . The class has no public constructors, and only contain static factory methods.
contains the static factory method . This method is an aggregation method. It takes in several parameters, takes into account of the type of the parameters, then returns an instance with the appropriate type. As of 2018, In Java SE8 OpenJDK implementation uses two implementations of which are invisible to the client, which are and . If the no longer provided any performance benefits for small enum types, it could be removed from the library without negatively impacting the Java Collection Library.
is a good replacement for the bit fields, which is a type of set, as described below.
Traditionally, whenever developers encountered elements of an enumerated type that needs to be placed in a set, the developer would use the int enum pattern in which every constant is assigned a different power of 2. This bit representation enables the developer to use the bitwise OR operation, so that the constants can be combined into a set, also known as a bit field. This bit field representation enables the developer to make efficient set-based operations and bitwise arithmetic such as intersection and unions.
However, there are many problems with bit field representation approach. A bit field is less readable than an int enum constant. Also, if the elements are represented by bit fields, it is impossible to iterate through all of these elements.
A recommended alternative approach is to use an , where an int enum is used instead of a bit field. This approach uses an to represent the set of values that belong to the same type. Since the implements the interface and no longer requires the use of bit-wise operations, this approach is more type-safe. Furthermore, there are many static factories that allow for object instantiation, such as the method method.
After the introduction of the , the bit field representation approach is considered to be obsolete.
<code>HashSet</code> uses a hash table. More specifically, it uses a to store the hashes and elements and to prevent duplicates.
The <code>java.util.LinkedHashSet</code> class extends by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over the <code>Set</code> is predictable.
is a concurrent replacement for a synchronized . It provides improved concurrency in many situations by removing the need to perform synchronization or making a copy of the object during iteration, similar to how acts as the concurrent replacement for a synchronized . On the other hand, similar to , should not be used when synchronization is mandatory.
The <code>java.util.SortedSet</code> interface extends the <code>java.util.Set</code> interface. Unlike a regular <code>Set</code>, the elements in a <code>SortedSet</code> are sorted, either by the element's method, or a method provided to the constructor of the <code>SortedSet</code>. The first and last elements of the <code>SortedSet</code> can be retrieved using the and methods respectively, and subsets can be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of the <code>SortedSet</code>. The <code>java.util.TreeSet</code> class implements the <code>SortedSet</code> interface.
The interface extends the <code>java.util.SortedSet</code> interface and has a few additional methods. The , , , and methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the <code>Set</code> is provided. As with <code>SortedSet</code>, <code>java.util.TreeSet</code> implements <code>NavigableSet</code>.
<code>java.util.TreeSet</code> uses a redâÂÂblack tree implemented by a . The redâÂÂblack tree ensures that there are no duplicates. Additionally, it allows <code>TreeSet</code> to implement .
acts as a concurrent replacement for implementations of a synchronized . For example it replaces a that has been wrapped by the method.
Maps are defined by the interface in Java.
s are data structures that associate a key with an element. This lets the map be very flexible. If the key is the hash code of the element, the <code>Map</code> is essentially a <code>Set</code>. If it's just an increasing number, it becomes a list.
Examples of implementations include , , and .
is an example of a skeletal implementation.
The direct subclasses of class include , , , , and .
========== extends . has comparable speed with an ordinal-indexed array. This is because internally uses an array, with implementation details completely hidden from the developer. Hence, the EnumMap gets the type safety of a while the performance advantages of an array.
========== uses a hash table. The hashes of the keys are used to find the elements in various buckets. The is a hash-based collection.
============ extends by creating a doubly linked list between the elements, allowing them to be accessed in the order in which they were inserted into the map. contains a <code>protected</code> <code>removeEldestEntry</code> method which is called by the <code>put</code> method whenever a new key is added to the <code>Map</code>. The <code>Map</code> removes its eldest entry whenever <code>removeEldestEntry</code> returns true. The <code>removeEldestEntry</code> method can be overridden.
========== , in contrast to and , uses a redâÂÂblack tree. The keys are used as the values for the nodes in the tree, and the nodes point to the elements in the <code>Map</code>.
========== is similar to and is also a hash-based collection. However, there are a number of differences, such as the differences in the locking strategy they use.
The uses a completely different locking strategy to provide improved scalability and concurrency. does not synchronize every method using the same lock. Instead, use a mechanism known as lock striping. This mechanism provides a finer-grained locking mechanism. It also permits a higher degree of shared access.
acts as a concurrent replacement for implementations of a synchronized . is very similar to , since replaces a that has been wrapped by the method.
The interface extends the <code>java.util.Map</code> interface. This interface defines a <code>Map</code> that's sorted by the keys provided. Using, once again, the <code>compareTo()</code> method or a method provided in the constructor to the <code>SortedMap</code>, the key-element pairs are sorted by the keys. The first and last keys in the <code>Map</code> can be called by using the and methods respectively. Additionally, submaps can be created from minimum and maximum keys by using the method. <code>SortedMap</code> is implemented by <code>java.util.TreeMap</code>.
The interface extends <code>java.util.SortedMap</code> in various ways. Methods can be called that find the key or map entry that's closest to the given key in either direction. The map can also be reversed, and an iterator in reverse order can be generated from it. It's implemented by <code>java.util.TreeMap</code>.
The interface extends the <code>java.util.Map</code> interface. This interface a thread Safe interface, introduced as of Java programming language's Java Collections Framework version 1.5.
Java collections framework is extended by the Apache Commons Collections library, which adds collection types such as a bag and bidirectional map, as well as utilities for creating unions and intersections.
Google has released its own collections libraries as part of the guava libraries.