TheJava collections framework is a set ofclasses andinterfaces that implement commonly reusable collectiondata structures (collections).[1]
Although referred to as aframework, it works in a manner of alibrary. The collections framework provides both interfaces that define various collections and classes that implement them.
Collections and arrays are similar in that they both hold references to objects and they can be managed as a group. However, unlike arrays,Collections do not need to be assigned a certain capacity when instantiated.Collections can grow and shrink in size automatically when objects are added or removed.
Collections cannot hold primitive data types such asint,long, ordouble.[2] Instead,Collections can holdwrapper classes such asjava.lang.Integer,java.lang.Long, orjava.lang.Double.[3]
Collections are generic and hence invariant, but arrays arecovariant. This can be considered an advantage of generic objects such asCollection when compared to arrays, because under circumstances, using the genericCollection 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 anObject[] object, and assigns theObject[] object to the value returned by a newLong[] instance with a certain capacity, no compile-time exception will be thrown. If the developer attempts to add aString to thisLong[] object, the java program will throw anArrayStoreException. On the other hand, if the developer instead declared a new instance of aCollection<Object> asArrayList<Long>, 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 instantiantingCollection<Object> as anArrayList<Object> object. If the code is using Java SE7 or later versions, the developer can instantiateCollection<Object> as anArrayList<> object by using thediamond operator[2]
Collections are generic and hencereified, but arrays are not reified.[2]
Collection implementations in pre-JDK 1.2 versions of the Java platform included few data structure classes, but did not contain a collections framework.[4] The standard methods for grouping Java objects were via the array, theVector, and theHashtable classes, which unfortunately were not easy to extend, and did not implement a standard member interface.[5][better source needed]
To address the need for reusable collectiondata structures, several independent frameworks were developed,[4] the most used beingDoug Lea'sCollections package,[6] andObjectSpaceGeneric Collection Library (JGL),[7] whose main goal was consistency with theC++Standard Template Library (STL).[8][better source needed]
The collections framework was designed and developed primarily byJoshua Bloch, and was introduced inJDK 1.2. It reused many ideas and classes from Doug Lea'sCollections package, which was deprecated as a result.[6]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.[9][better source needed]
Doug Lea later developed aconcurrencypackage, comprising new Collection-related classes.[10] An updated version of these concurrency utilities was included inJDK 5.0 as ofJSR 166.
Most collections in Java that are not maps are derived from thejava.util.Collection interface.Collection defines the basic parts of all collections.
The interface has theadd(E e) andremove(E e) methods for adding to and removing from aCollection respectively. It also has thetoArray() method, which converts theCollection into an array ofObjects in theCollection (with return type ofObject[]).[11] Finally, thecontains(E e) method checks if a specified element exists in theCollection.
TheCollection interface is a subinterface ofjava.lang.Iterable, so anyCollection may be the target of afor-each statement. (TheIterable interface provides theiterator() method used by for-each statements.) AllCollections implementjava.util.Iterator to scan all of the elements in theCollection.
Collection is generic. AnyCollection can store anyObject. For example, any implementation ofCollection<String> containsString objects. No casting is required when using theString objects from an implementation ofCollection<String>.[12] Note that the angled brackets< > can hold a type argument that specifies which type theCollection holds.[13]
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 andsets.
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 calledQueue.
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 calledMap.
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 calledSet.[3]
Lists are implemented in the collections framework via thejava.util.Listinterface. 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 implementList, includingAbstractList and all of its corresponding subclasses, as well asCopyOnWriteArrayList.
The direct subclasses ofAbstractList class includeAbstractSequentialList,ArrayList andVector.
AbstractList is an example of askeletal 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.[14]
Thejava.util.ArrayList class implements theList as an array. Whenever functions specific to aList are required, the class moves the elements around within the array in order to do it.
Thejava.util.LinkedList class stores the elements in nodes that each have a pointer to the previous and next nodes in theList. TheList 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.[15]
TheVector class hasStack as its direct subclass. This is an example of a violation of thecomposition over inheritance principle in the Java platform libraries, since incomputer science, avector is generally not astack.[16] Composition would have been more appropriate in this scenario.[16]
TheStack classextends classjava.util.Vector with five operations that allow aVector to be treated as aStack.Stacks are created usingjava.util.Stack. TheStack offers methods to put a new object on theStack (methodpush(E e)) and to get objects from theStack (methodpop()). AStack returns the object according tolast-in-first-out (LIFO), e.g. the object which was placed latest on theStack is returned first.java.util.Stack is a standard implementation of a stack provided by Java.
TheStack class represents a last-in-first-out (LIFO) stack of objects. The Stack class has five additional operations that allow aVector to be treated as aStack. The usualpush(E e) andpop() operations are provided, as well as a method (peek()) to peek at the top item on theStack, a method to test for whether theStack is empty (empty()), and a method to search theStack for an item and discover how far it is from the top (search(Object o)). When aStack is first created, it contains no items.
TheCopyOnWriteArrayList extends theObject class, and does not extend any other classes.CopyOnWriteArrayList allows for thread-safety without performing excessive synchronization.[17]
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 asCopyOnWriteArrayList should not be used.[17]
However synchronization can incur a performance overhead. For scenarios where synchronization is not mandatory, then theCopyOnWriteArrayList is a viable, thread-safe alternative to synchronization that leveragesmulti-core processors and results in higherCPU utilization.[17]
Thejava.util.Queue 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 afirst-in first-out system. This interface is implemented byjava.util.LinkedList,java.util.ArrayDeque, andjava.util.PriorityQueue.
The direct subclasses ofAbstractQueue class includeArrayBlockingQueue,ConcurrentLinkedQueue,DelayeQueue,LinkedBlockingDeque,LinkedBlockingQueue.LinkedTransferQueue andPriorityBlockingQueue.
Note thatArrayDeque andConcurrentLinkedDeque both extendAbstractCollection but do not extend any other abstract classes such asAbstractQueue.
AbstractQueue is an example of askeletal implementation.
Thejava.util.PriorityQueue class implementsjava.util.Queue, but also alters it.[18]PriorityQueue has an additionalcomparator() method.[18] 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 thejava.lang.Comparable#compareTo(T) method in the elements, or a method given in the constructor. The class creates this by using a heap to keep the items sorted.[19]
Thejava.util.concurrent.ConcurrentLinkedQueue class extendsjava.util.AbstractQueue.ConcurrentLinkedQueue implements thejava.util.Queue interface.[20]
TheConcurrentLinkedQueue class is a thread-safe collection, since for any an element placed inside aConcurrentLinkedQueue, the Java Collection Library guarantees that the element issafely published by allowing any thread to get the element from the collection.[21] An object is said to besafely published if the object's state is made visible to all other thread at the same point in time.[21] Safe publication usually requires synchronization of the publishing and consuming threads.[21]
Thejava.util.concurrent.BlockingQueue interface extendsQueue.[20]
TheBlockingQueue interface has the following direct sub-interfaces:BlockingDeque andTransferQueue.BlockingQueue works like a regularQueue, but additions to and removals from theBlockingQueue are blocking.[22] Ifremove(Object o) is called on an emptyBlockingQueue, it can be set to wait either a specified time or indefinitely for an item to appear in theBlockingQueue. Similarly, adding an item using the methodadd(Object o) is subject to an optional capacity restriction on theBlockingQueue, and the method can wait for space to become available in theBlockingQueue before returning.BlockingQueue interface introduces a methodtake() which removes and gets the head of theBlockingQueue, and waits until theBlockingQueue is no longer empty if required.[23][24]
TheDeque interfaceextends theQueue interface.[25]Deque creates a double-ended queue. While a regularQueue only allows insertions at the rear and removals at the front, theDeque allows insertions or removals to take place both at the front and the back. ADeque is like aQueue that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. TheDeque interface is implemented byjava.util.ArrayDeque andjava.util.LinkedList.[26]
LinkedList, of course, also implements theList interface and can also be used as one. But it also has theQueue methods.LinkedList implements thejava.util.Deque interface, giving it more flexibility.[27]
ArrayDeque implements theQueue as an array. Similar toLinkedList,ArrayDeque also implements thejava.util.Deque interface.[27]
Thejava.util.concurrent.BlockingDeque interface extendsjava.util.concurrent.BlockingQueue.[25]BlockingDeque is similar toBlockingQueue. 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 aDeque. Insertions and removals can take place at both ends. The blocking function is combined with theDeque function.[28]
Java'sjava.util.Setinterface defines theSet. ASet can't have any duplicate elements in it. Additionally, theSet has no set order. As such, elements can't be found by index.Set is implemented byjava.util.HashSet,java.util.LinkedHashSet, andjava.util.TreeSet.
There are several implementations of the Set interface, includingAbstractSet and its subclasses, and the final static inner classConcurrentHashMap.KeySetView<K,V> (whereK andV are formal type parameters).
AbstractSet is askeletal implementation for theSet interface.[14]
Direct subclasses ofAbstractSet includeConcurrentSkipListSet,CopyOnWriteArraySet,EnumSet,HashSet andTreeSet.
TheEnumSet class extendsAbstractSet. TheEnumSet class has no public constructors, and only contain static factory methods.[29]
EnumSet contains the static factory methodEnumSet.of().[30] This method is an aggregation method.[29] It takes in several parameters, takes into account of the type of the parameters, then returns an instance with the appropriate type.[29] As of 2018, In Java SE8 OpenJDK implementation uses two implementations ofEnumSet which are invisible to the client, which areRegularEnumSet andJumboEnumSet.[29] If theRegularEnumSet no longer provided any performance benefits for small enum types, it could be removed from the library without negatively impacting the Java Collection Library.[29]
EnumSet is a good replacement for thebit fields, which is a type of set, as described below.[30]
Traditionally, whenever developers encountered elements of an enumerated type that needs to be placed in a set, the developer would use theint enum pattern in which every constant is assigned a different power of 2.[30] 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 abit field. Thisbit field representation enables the developer to make efficient set-based operations and bitwise arithmetic such as intersection and unions.[30]
However, there are many problems withbit field representation approach. A bit field is less readable than an int enum constant.[30] Also, if the elements are represented by bit fields, it is impossible to iterate through all of these elements.[30]
A recommended alternative approach is to use anEnumSet, where an int enum is used instead of abit field.[30] This approach uses anEnumSet to represent the set of values that belong to the sameEnum type.[30] Since theEnumSet implements theSet interface and no longer requires the use of bit-wise operations, this approach is more type-safe.[30] Furthermore, there are many static factories that allow for object instantiation, such as the methodEnumSet.of() method.[30]
After the introduction of theEnumSet, thebit field representation approach is considered to be obsolete.[30]
HashSet uses a hash table. More specifically, it uses ajava.util.LinkedHashMap to store the hashes and elements and to prevent duplicates.
Thejava.util.LinkedHashSet class extendsHashSet by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over theSet is predictable.
CopyOnWriteArraySet is a concurrent replacement for a synchronizedSet. 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 howCopyOnWriteArrayList acts as the concurrent replacement for a synchronizedList.[31]On the other hand, similar toCopyOnWriteArrayList,CopyOnWriteArraySet should not be used when synchronization is mandatory.
Thejava.util.SortedSet interface extends thejava.util.Set interface. Unlike a regularSet, the elements in aSortedSet are sorted, either by the element'scompareTo(T o) method, or a method provided to the constructor of theSortedSet. The first and last elements of theSortedSet can be retrieved using thefirst() andlast() methods respectively, and subsets can be created via minimum and maximum values, as well as beginning or ending at the beginning or ending of theSortedSet. Thejava.util.TreeSet class implements theSortedSet interface.[32]
Thejava.util.NavigableSet interface extends thejava.util.SortedSet interface and has a few additional methods. Thefloor(E e),ceiling(E e),lower(E e), andhigher(E e) methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in theSet is provided. As withSortedSet,java.util.TreeSet implementsNavigableSet.[33]
java.util.TreeSet uses ared–black tree implemented by ajava.util.TreeMap. The red–black tree ensures that there are no duplicates. Additionally, it allowsTreeSet to implementjava.util.SortedSet.[34]
ConcurrentSkipListSet acts as a concurrent replacement for implementations of a synchronizedSortedSet. For example it replaces aTreeSet that has been wrapped by thesynchronizedMap method.[35]
Maps are defined by thejava.util.Map interface in Java.
Maps 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, theMap is essentially aSet. If it's just an increasing number, it becomes a list.
Examples ofMap implementations includejava.util.HashMap,java.util.LinkedHashMap, andjava.util.TreeMap.
AbstractMap is an example of askeletal implementation.[14]
The direct subclasses ofAbstractMap class includeConcurrentSkipListMap,EnumMap,HashMap,IdentityHashMap,TreeMap andWeakHashMap.
EnumMap extendsAbstractMap.EnumMap has comparable speed with an ordinal-indexed array.[36] This is becauseEnumMap internally uses an array, with implementation details completely hidden from the developer.[36] Hence, the EnumMap gets the type safety of aMap while the performance advantages of an array.[36]
HashMap uses ahash table. The hashes of the keys are used to find the elements in various buckets. TheHashMap is a hash-based collection.[37]
LinkedHashMap extendsHashMap by creating adoubly linked list between the elements, allowing them to be accessed in the order in which they were inserted into the map.LinkedHashMap contains aprotectedremoveEldestEntry method which is called by theput method whenever a new key is added to theMap.[38] TheMap removes its eldest entry wheneverremoveEldestEntry returns true.[38] TheremoveEldestEntry method can be overridden.[38]
TreeMap, in contrast toHashMap andLinkedHashMap, 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 theMap.[39]
ConcurrentHashMap is similar toHashMap and is also a hash-based collection.[37] However, there are a number of differences, such as the differences in the locking strategy they use.
TheConcurrentHashMap uses a completely different locking strategy to provide improved scalability and concurrency.[37]ConcurrentHashMap does not synchronize every method using the same lock.[37] Instead,ConcurrentHashMap use a mechanism known aslock striping.[37] This mechanism provides a finer-grained locking mechanism.[37] It also permits a higher degree of shared access.[37]
ConcurrentSkipListMap acts as a concurrent replacement for implementations of a synchronizedSortedMap.ConcurrentSkipListMap is very similar toConcurrentSkipListSet, sinceConcurrentSkipListMap replaces aTreeMap that has been wrapped by thesynchronizedMap method.[35]
Thejava.util.SortedMap interface extends thejava.util.Map interface. This interface defines aMap that's sorted by the keys provided. Using, once again, thecompareTo() method or a method provided in the constructor to theSortedMap, the key-element pairs are sorted by the keys. The first and last keys in theMap can be called by using thefirstKey() andlastKey() methods respectively. Additionally, submaps can be created from minimum and maximum keys by using theK) subMap(K fromKey, K toKey) method.SortedMap is implemented byjava.util.TreeMap.[40]
Thejava.util.NavigableMap interface extendsjava.util.SortedMap 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 byjava.util.TreeMap.[41]
Thejava.util.concurrent.ConcurrentMap interface extends thejava.util.Map interface. This interface a thread SafeMap interface, introduced as of Java programming language'sJava Collections Framework version 1.5.[20]
Java collections framework is extended by theApache Commons Collections library, which adds collection types such as a bag and bidirectional map, as well as utilities for creating unions and intersections.[42]
Google has released its own collections libraries as part of theguava libraries.
Before Collections made its most welcome debut, the standard methods for grouping Java objects were via the array, the Vector, and the Hashtable. All three of these collections have different methods and syntax for accessing members: arrays use the square bracket ([]) symbols, Vector uses the elementAt method, and Hashtable usesgetandputmethods.
The Sun Java Development Kit JDK1.2 finally includes a standard set of collection classes. While there are some design and implementation differences, the JDK1.2 package contains most of the same basic abstractions, structure, and functionality as this package. For this reason, this collections package will NOT be further updated
As with Java itself, the Java Generic Library borrows heavily from the C++ camp: It takes the best from C++'s STL, while leaving the C++ warts behind. Most C++ programmers today will know of their STL, but few are managing to exploit its potential.
Comparing ObjectSpace Inc.'s JGL and Sun's Collections Framework turns out to be like comparing apples and kiwi fruits. At first sight, the two frameworks seem to be competing for the same developers, but after a closer inspection it is clear that the two cannot be compared fairly without acknowledging first that the two frameworks have different goals. If, like Sun's documentation states, Collections is going to homogenize Sun's own APIs (core API, extensions, etc.), then clearly Collections has to be great news, and a good thing, even to the most fanatic JGL addict. Provided Sun doesn't break its promise in this area, I'll be happy to invest my resources in adopting Collections in earnest.
Note: Upon release of J2SE 5.0, this package enters maintenance mode: Only essential corrections will be released. J2SE5 package java.util.concurrent includes improved, more efficient, standardized versions of the main components in this package.
| Platforms |
| _waving.svg) | |||||
|---|---|---|---|---|---|---|---|
| Technologies |
| ||||||
| History | |||||||
| JVM languages | |||||||
| Community |
| ||||||
