The Java collections framework is a set of classes and interfaces that implement commonly reusable collection data structures. [1]
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.
Collection
s and arrays are similar in that they both hold references to objects and they can be managed as a group. However, unlike arrays, Collection
s do not need to be assigned a certain capacity when instantiated. Collection
s can grow and shrink in size automatically when objects are added or removed.
Collection
s cannot hold primitive data types such as int
, long
, or double
. [2] Instead, Collection
s can hold wrapper classes such as java.lang.Integer
, java.lang.Long
, or java.lang.Double
. [3]
Collection
s are generic and hence invariant, but arrays are covariant. This can be considered an advantage of generic objects such as Collection
when compared to arrays, because under circumstances, using the generic Collection
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[]
object, and assigns the Object[]
object to the value returned by a new Long[]
instance with a certain capacity, no compile-time exception will be thrown. If the developer attempts to add a String
to this Long[]
object, the java program will throw an ArrayStoreException
. On the other hand, if the developer instead declared a new instance of a Collection<Object>
as ArrayList<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 instantianting Collection<Object>
as an ArrayList<Object>
object. If the code is using Java SE7 or later versions, the developer can instatiate Collection<Object>
as an ArrayList<>
object by using the diamond operator [2]
Collection
s are generic and hence reified, 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, the Vector
, and the Hashtable
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 collection data structures, several independent frameworks were developed, [4] the most used being Doug Lea's Collections package, [6] and ObjectSpace Generic Collection Library (JGL), [7] whose main goal was consistency with the C++ Standard Template Library (STL). [8] [ better source needed ]
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. [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 a concurrency package, comprising new Collection-related classes. [10] An updated version of these concurrency utilities was included in JDK 5.0 as of JSR 166.
Almost all collections in Java are derived from the java.util.Collection
interface. Collection
defines the basic parts of all collections.
The interface has the add(E e)
and remove(E e)
methods for adding to and removing from a Collection
respectively. It also has the toArray()
method, which converts the Collection
into an array of Object
s in the Collection
(with return type of Object[]
). [11] Finally, the contains(E e)
method checks if a specified element exists in the Collection
.
The Collection
interface is a subinterface of java.lang.Iterable
, so any Collection
may be the target of a for-each statement. (The Iterable
interface provides the iterator()
method used by for-each statements.) All Collection
s have an java.util.Iterator
that goes through all of the elements in the Collection
.
Collection
is generic. Any Collection
can store any Object
. For example, any implementation of Collection<String>
contains String
objects. No casting is required when using the String
objects from an implementation of Collection<String>
. [12] Note that the angled brackets < >
can hold a type argument that specifies which type the Collection
holds. [13]
There are several generic types of Collection
: 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 Queue
.
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 Map
.
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 Set
. [3]
Lists are implemented in the collections framework via the java.util.List
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 List
, including AbstractList
and all of its corresponding subclasses, as well as CopyOnWriteArrayList
.
The direct subclasses of AbstractList
class include AbstractSequentialList
, ArrayList
and Vector
.
AbstractList
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. [14]
The java.util.ArrayList
class implements the List
as an array. Whenever functions specific to a List
are required, the class moves the elements around within the array in order to do it.
The java.util.LinkedList
class stores the elements in nodes that each have a pointer to the previous and next nodes in the List
. The List
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]
The Vector
class has Stack
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. [16] Composition would have been more appropriate in this scenario. [16]
The Stack class extends
class java.util.Vector
with five operations that allow a Vector
to be treated as a Stack
. Stacks are created using java.util.Stack
. The Stack
offers methods to put a new object on the Stack
(method push(E e)
) and to get objects from the Stack
(method pop()
). A Stack
returns the object according to last-in-first-out (LIFO), e.g. the object which was placed latest on the Stack
is returned first. java.util.Stack
is a standard implementation of a stack provided by Java.
The Stack
class represents a last-in-first-out (LIFO) stack of objects. The Stack class has five additional operations that allow a Vector
to be treated as a Stack
. The usual push(E e)
and pop()
operations are provided, as well as a method ( peek()
) to peek at the top item on the Stack
, a method to test for whether the Stack
is empty ( empty()
), and a method to search the Stack
for an item and discover how far it is from the top ( search(Object o)
). When a Stack
is first created, it contains no items.
The CopyOnWriteArrayList
extends the Object
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 as CopyOnWriteArrayList
should not be used. [17]
However synchronization can incur a performance overhead. For scenarios where synchronization is not mandatory, then the CopyOnWriteArrayList
is a viable, thread-safe alternative to synchronization that leverages multi-core processors and results in higher CPU utilization. [17]
The java.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 a first-in first-out system. This interface is implemented by java.util.LinkedList
, java.util.ArrayDeque
, and java.util.PriorityQueue
.
The direct subclasses of AbstractQueue
class include ArrayBlockingQueue
, ConcurrentLinkedQueue
, DelayeQueue
, LinkedBlockingDeque
, LinkedBlockingQueue
. LinkedTransferQueue
and PriorityBlockingQueue
.
Note that ArrayDeque
and ConcurrentLinkedDeque
both extend AbstractCollection
but do not extend any other abstract classes such as AbstractQueue
.
AbstractQueue
is an example of a skeletal implementation.
The java.util.PriorityQueue
class implements java.util.Queue
, but also alters it. [18] PriorityQueue
has an additional comparator()
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 the java.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]
The java.util.concurrent.ConcurrentLinkedQueue
class extends java.util.AbstractQueue
. ConcurrentLinkedQueue
implements the java.util.Queue
interface. [20]
The ConcurrentLinkedQueue
class is a thread-safe collection, since for any an element placed inside a ConcurrentLinkedQueue
, the Java Collection Library guarantees that the element is safely published by allowing any thread to get the element from the collection. [21] 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. [21] Safe publication usually requires synchronization of the publishing and consuming threads. [21]
The java.util.concurrent.BlockingQueue
interface extends Queue
. [20]
The BlockingQueue
interface has the following direct sub-interfaces: BlockingDeque
and TransferQueue
. BlockingQueue
works like a regular Queue
, but additions to and removals from the BlockingQueue
are blocking. [22] If remove(Object o)
is called on an empty BlockingQueue
, it can be set to wait either a specified time or indefinitely for an item to appear in the BlockingQueue
. Similarly, adding an item using the method add(Object o)
is subject to an optional capacity restriction on the BlockingQueue
, and the method can wait for space to become available in the BlockingQueue
before returning. BlockingQueue
interface introduces a method take()
which removes and gets the head of the BlockingQueue
, and waits until the BlockingQueue
is no longer empty if required. [23] [24]
The Deque
interface extends the Queue
interface. [25] Deque
creates a double-ended queue. While a regular Queue
only allows insertions at the rear and removals at the front, the Deque
allows insertions or removals to take place both at the front and the back. A Deque
is like a Queue
that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The Deque
interface is implemented by java.util.ArrayDeque
and java.util.LinkedList
. [26]
LinkedList
, of course, also implements the List
interface and can also be used as one. But it also has the Queue
methods. LinkedList
implements the java.util.Deque
interface, giving it more flexibility. [27]
ArrayDeque
implements the Queue
as an array. Similar to LinkedList
, ArrayDeque
also implements the java.util.Deque
interface. [27]
The java.util.concurrent.BlockingDeque
interface extends java.util.concurrent.BlockingQueue
. [25] BlockingDeque
is similar to BlockingQueue
. 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 Deque
. Insertions and removals can take place at both ends. The blocking function is combined with the Deque
function. [28]
Java's java.util.Set
interface defines the Set
. A Set
can't have any duplicate elements in it. Additionally, the Set
has no set order. As such, elements can't be found by index. Set
is implemented by java.util.HashSet
, java.util.LinkedHashSet
, and java.util.TreeSet
.
There are several implementations of the Set interface, including AbstractSet
and its subclasses, and the final static inner class ConcurrentHashMap.KeySetView<K,V>
(where K
and V
are formal type parameters).
AbstractSet
is a skeletal implementation for the Set
interface. [14]
Direct subclasses of AbstractSet
include ConcurrentSkipListSet
, CopyOnWriteArraySet
, EnumSet
, HashSet
and TreeSet
.
The EnumSet
class extends AbstractSet
. The EnumSet
class has no public constructors, and only contain static factory methods. [29]
EnumSet
contains the static factory method EnumSet.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 of EnumSet
which are invisible to the client, which are RegularEnumSet
and JumboEnumSet
. [29] If the RegularEnumSet
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 the bit 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 the int 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 a bit field. This bit 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 with bit 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 an EnumSet
, where an int enum is used instead of a bit field. [30] This approach uses an EnumSet
to represent the set of values that belong to the same Enum
type. [30] Since the EnumSet
implements the Set
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 method EnumSet.of()
method. [30]
After the introduction of the EnumSet
, the bit field representation approach is considered to be obsolete. [30]
HashSet
uses a hash table. More specifically, it uses a java.util.LinkedHashMap
to store the hashes and elements and to prevent duplicates.
The java.util.LinkedHashSet
class extends HashSet
by creating a doubly linked list that links all of the elements by their insertion order. This ensures that the iteration order over the Set
is predictable.
CopyOnWriteArraySet
is a concurrent replacement for a synchronized Set
. 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 CopyOnWriteArrayList
acts as the concurrent replacement for a synchronized List
. [31] On the other hand, similar to CopyOnWriteArrayList
, CopyOnWriteArraySet
should not be used when synchronization is mandatory.
The java.util.SortedSet
interface extends the java.util.Set
interface. Unlike a regular Set
, the elements in a SortedSet
are sorted, either by the element's compareTo(T o)
method, or a method provided to the constructor of the SortedSet
. The first and last elements of the SortedSet
can be retrieved using the first()
and last()
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 SortedSet
. The java.util.TreeSet
class implements the SortedSet
interface. [32]
The java.util.NavigableSet
interface extends the java.util.SortedSet
interface and has a few additional methods. The floor(E e)
, ceiling(E e)
, lower(E e)
, and higher(E e)
methods find an element in the set that's close to the parameter. Additionally, a descending iterator over the items in the Set
is provided. As with SortedSet
, java.util.TreeSet
implements NavigableSet
. [33]
java.util.TreeSet
uses a red–black tree implemented by a java.util.TreeMap
. The red–black tree ensures that there are no duplicates. Additionally, it allows TreeSet
to implement java.util.SortedSet
. [34]
ConcurrentSkipListSet
acts as a concurrent replacement for implementations of a synchronized SortedSet
. For example it replaces a TreeSet
that has been wrapped by the synchronizedMap
method. [35]
Maps are defined by the java.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, the Map
is essentially a Set
. If it's just an increasing number, it becomes a list.
Examples of Map
implementations include java.util.HashMap
, java.util.LinkedHashMap
, and java.util.TreeMap
.
AbstractMap
is an example of a skeletal implementation. [14]
The direct subclasses of AbstractMap
class include ConcurrentSkipListMap
, EnumMap
, HashMap
, IdentityHashMap
, TreeMap
and WeakHashMap
.
EnumMap
extends AbstractMap
. EnumMap
has comparable speed with an ordinal-indexed array. [36] This is because EnumMap
internally uses an array, with implementation details completely hidden from the developer. [36] Hence, the EnumMap gets the type safety of a Map
while the performance advantages of an array. [36]
HashMap
uses a hash table. The hashes of the keys are used to find the elements in various buckets. The HashMap
is a hash-based collection. [37]
LinkedHashMap
extends HashMap
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. LinkedHashMap
contains a protected
removeEldestEntry
method which is called by the put
method whenever a new key is added to the Map
. [38] The Map
removes its eldest entry whenever removeEldestEntry
returns true. [38] The removeEldestEntry
method can be overridden. [38]
TreeMap
, in contrast to HashMap
and LinkedHashMap
, 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 Map
. [39]
ConcurrentHashMap
is similar to HashMap
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.
The ConcurrentHashMap
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 as lock 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 synchronized SortedMap
. ConcurrentSkipListMap
is very similar to ConcurrentSkipListSet
, since ConcurrentSkipListMap
replaces a TreeMap
that has been wrapped by the synchronizedMap
method. [35]
The java.util.SortedMap
interface extends the java.util.Map
interface. This interface defines a Map
that's sorted by the keys provided. Using, once again, the compareTo()
method or a method provided in the constructor to the SortedMap
, the key-element pairs are sorted by the keys. The first and last keys in the Map
can be called by using the firstKey()
and lastKey()
methods respectively. Additionally, submaps can be created from minimum and maximum keys by using the subMap(K fromKey, K toKey)
method. SortedMap
is implemented by java.util.TreeMap
. [40]
The java.util.NavigableMap
interface extends java.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 by java.util.TreeMap
. [41]
The java.util.concurrent.ConcurrentMap
interface extends the java.util.Map
interface. This interface a thread Safe Map
interface, introduced as of Java programming language's Java Collections Framework version 1.5. [20]
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. [42]
Google has released its own collections libraries as part of the guava 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 usesget
andput
methods.
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.
In computer science, a data structure is a data organization, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i.e., it is an algebraic structure about data.
In computer science, a double-ended queue is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list, though properly this refers to a specific data structure implementation of a deque.
In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back, tail, or rear of the queue, and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.
Java Platform, Standard Edition is a computing platform for development and deployment of portable code for desktop and server environments. Java SE was formerly known as Java 2 Platform, Standard Edition (J2SE).
Java and C++ are two prominent object-oriented programming languages. By many language popularity metrics, the two languages have dominated object-oriented and high-performance software development for much of the 21st century, and are often directly compared and contrasted. Java's syntax was based on C/C++.
The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called algorithms, containers, functions, and iterators.
In software engineering, the mediator pattern defines an object that encapsulates how a set of objects interact. This pattern is considered to be a behavioral pattern due to the way it can alter the program's running behavior.
In computer programming, an iterator is an object that progressively provides access to each item of a collection, in order.
In computer science, a set is an abstract data type that can store unique values, without any particular order. It is a computer implementation of the mathematical concept of a finite set. Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.
This article compares two programming languages: C# with Java. While the focus of this article is mainly the languages and their features, such a comparison will necessarily also consider some features of platforms and libraries. For a more detailed comparison of the platforms, see Comparison of the Java and .NET platforms.
The syntax of Java is the set of rules defining how a Java program is written and interpreted.
java.nio is a collection of Java programming language APIs that offer features for intensive I/O operations. It was introduced with the J2SE 1.4 release of Java by Sun Microsystems to complement an existing standard I/O. NIO was developed under the Java Community Process as JSR 51. An extension to NIO that offers a new file system API, called NIO.2, was released with Java SE 7 ("Dolphin").
In computer science, a container is a class or a data structure whose instances are collections of other objects. In other words, they store objects in an organized way that follows specific access rules.
The active object design pattern decouples method execution from method invocation for objects that each reside in their own thread of control. The goal is to introduce concurrency, by using asynchronous method invocation and a scheduler for handling requests.
The Java programming language and the Java virtual machine (JVM) is designed to support concurrent programming. All execution takes place in the context of threads. Objects and resources can be accessed by many separate threads. Each thread has its own path of execution, but can potentially access any object in the program. The programmer must ensure read and write access to objects is properly coordinated between threads. Thread synchronization ensures that objects are modified by only one thread at a time and prevents threads from accessing partially updated objects during modification by another thread. The Java language has built-in constructs to support this coordination.
Generics are a facility of generic programming that were added to the Java programming language in 2004 within version J2SE 5.0. They were designed to extend Java's type system to allow "a type or method to operate on objects of various types while providing compile-time type safety". The aspect compile-time type safety required that parametrically polymorphic functions are not implemented in the Java virtual machine, since type safety is impossible in this case.
In computer programming, a collection is an abstract data type that is a grouping of items that can be used in a polymorphic way.
This comparison of programming languages (associative arrays) compares the features of associative array data structures or array-lookup processing for over 40 computer programming languages.
InfinityDB is an all-Java embedded database engine and client/server DBMS with an extended java.util.concurrent.ConcurrentNavigableMap interface that is deployed in handheld devices, on servers, on workstations, and in distributed settings. The design is based on a proprietary lockless, concurrent, B-tree architecture that enables client programmers to reach high levels of performance without risk of failures.
The Java programming language's Java Collections Framework version 1.5 and later defines and implements the original regular single-threaded Maps, and also new thread-safe Maps implementing the java.util.concurrent.ConcurrentMap
interface among other concurrent interfaces. In Java 1.6, the java.util.NavigableMap
interface was added, extending java.util.SortedMap
, and the java.util.concurrent.ConcurrentNavigableMap
interface was added as a subinterface combination.