View source for Java collections framework

{{Short description|Collections in Java}}
[[File:Java.util.Collection hierarchy.svg|thumb|java.util.Collection class and interface hierarchy]]
[[File:Java.util.Map hierarchy.svg|thumb|Java's java.util.Map class and interface hierarchy]]
The '''[[Java (programming language)|Java]] collections framework''' is a set of [[class (computer science)|classes]] and [[interface (java)|interfaces]] that implement commonly reusable collection [[data structure]]s.<ref>{{cite web
| url=http://download.oracle.com/javase/tutorial/collections/intro/index.html
| title=Lesson: Introduction to Collections
| publisher=[[Oracle Corporation]]
| access-date=2010-12-22}}</ref>

Although referred to as a [[Software framework|framework]], it works in a manner of a [[Library (computing)|library]]. The collections framework provides both interfaces that define various collections and classes that implement them.

== Differences from Arrays==
<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>.{{sfn|Bloch|2018|loc=Chapter §5 Item 28: Prefer lists to arrays|pp=126-129}} Instead, <code>Collection</code>s can hold [[wrapper class]]es such as {{Javadoc|module=java.base|package=java.lang|class=Integer|monotype=y}}, {{Javadoc|module=java.base|package=java.lang|class=Long|monotype=y}}, or {{Javadoc|module=java.base|package=java.lang|class=Double|monotype=y}}.<ref name=":0">{{Cite book|title=Big Java Early Objects|last=Horstmann|first=Cay|year=2014}}</ref>

<code>Collection</code>s are generic and hence invariant, but arrays are [[Covariance and contravariance (computer science)|covariant]]. This can be considered an advantage of generic objects such as {{code|Collection}} when compared to arrays, because under circumstances, using the generic {{code|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 {{code|Object[]}} object, and assigns the {{code|Object[]}} object to the value returned by a new {{code|Long[]}} instance with a certain capacity, no compile-time exception will be thrown. If the developer attempts to add a {{code|String}} to this {{code|Long[]}} object, the java program will throw an {{code|ArrayStoreException}}. On the other hand, if the developer instead declared a new instance of a {{code|Collection<Object>}} as {{code|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 {{code|Collection<Object>}} as an {{code|ArrayList<Object>}} object. If the code is using Java SE7 or later versions, the developer can instantiate {{code|Collection<Object>}} as an {{code|ArrayList<>}} object by using the [[Generics in Java#Diamond operator|diamond operator]]{{sfn|Bloch|2018|loc=Chapter §5 Item 28: Prefer lists to arrays|pp=126-129}}

<code>Collection</code>s are generic and hence [[reification (computer science)|reified]], but arrays are not reified.{{sfn|Bloch|2018|loc=Chapter §5 Item 28: Prefer lists to arrays|pp=126-129}}

==History==
<code>Collection</code> implementations in pre-[[J2SE 1.2|JDK 1.2]] versions of the Java platform included few data structure classes, but did not contain a collections framework.<ref name="ibm">{{cite web
 |url=http://www.digilife.be/quickreferences/PT/Java%20Collections%20Framework.pdf
 |title=Java Collections Framework
 |publisher=[[IBM]]
 |url-status=dead
 |archive-url=https://web.archive.org/web/20110807042032/http://www.digilife.be/quickreferences/PT/Java%20Collections%20Framework.pdf
 |archive-date=2011-08-07
}}</ref> 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.<ref>{{cite web
 |last1=Becker |first1=Dan
 |date=1998-11-01 |df=mdy
 |url=https://www.infoworld.com/article/2076800/get-started-with-the-java-collections-framework.html
 |title=Get started with the Java Collections Framework
 |work=[[JavaWorld]]
 |access-date=2020-07-13
 |quote=''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 uses <code>get</code> and <code>put</code> methods.''
}}</ref>{{Better source needed|date=June 2023}}

To address the need for reusable collection [[data structure]]s, several independent frameworks were developed,<ref name="ibm"/> the most used being [[Doug Lea]]'s ''Collections package'',<ref name="douglea">{{cite web
 |author-link1=Doug Lea |last1=Lea |first1=Doug
 |url=http://gee.cs.oswego.edu/dl/classes/collections/index.html
 |title=Overview of the collections Package
 |access-date=2011-01-01
 |quote=''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''
}}</ref> and [[Recursion Software|ObjectSpace]] ''Generic Collection Library'' (JGL),<ref>{{cite web
 |url=http://www.stanford.edu/group/coursework/docsTech/jgl/
 |title=Generic Collection Library for Java™
 |access-date=2011-01-01
 |archive-date=2009-03-12
 |archive-url=https://web.archive.org/web/20090312075146/http://www.stanford.edu/group/coursework/docsTech/jgl/
 |url-status=dead
 }}</ref> whose main goal was consistency with the [[C++]] [[Standard Template Library]] (STL).<ref>{{cite web
 |last1=Vanhelsuwé |first1=Laurence
 |date=1997-06-01 |df=mdy
 |url=https://www.infoworld.com/article/2076958/need-a-good-set-of-abstract-data-structures--objectspace-s-jgl-packs-a-punch-.html
 |title=Need a good set of abstract data structures? ObjectSpace's JGL packs a punch!
 |work=[[JavaWorld]]
 |access-date=2020-07-13
 |quote=''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.''
}}</ref>{{Better source needed|date=June 2023}}

The collections framework was designed and developed primarily by [[Joshua Bloch]], and was introduced in [[J2SE 1.2|JDK 1.2]]. It reused many ideas and classes from Doug Lea's ''Collections package'', which was deprecated as a result.<ref name="douglea" /> [[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.<ref>{{cite web
 |last1=Vanhelsuwé |first1=Laurence
 |date=1999-01-01 |df=mdy
 |url=https://www.infoworld.com/article/2076326/the-battle-of-the-container-frameworks--which-should-you-use-.html
 |title=The battle of the container frameworks: which should you use?
 |work=[[JavaWorld]]
 |access-date=2020-07-13
 |quote=''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. ''
}}</ref>{{Better source needed|date=June 2023}}

Doug Lea later developed a [[Concurrency (computer science)|concurrency]] [[Java package|package]], comprising new Collection-related classes.<ref name="douglea2">{{cite web
 |author-link1=Doug Lea |last1=Lea |first1=Doug
 |url=http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html
 |title=Overview of package util.concurrent Release 1.3.4
 |access-date=2011-01-01
 |quote=''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.''
}}</ref> An updated version of these concurrency utilities was included in [[J2SE 5.0|JDK 5.0]] as of [[Java concurrency|JSR 166]].

==Architecture==
Almost all collections in Java are derived from the '''{{Javadoc:SE|module=java.base|package=java.util|java/util|Collection}}''' interface. <code>Collection</code> defines the basic parts of all collections. 

The interface has the {{Javadoc:SE|module=java.base|name=add(E e)|java/util|Collection|add(E)}} and {{Javadoc:SE|module=java.base|name=remove(E e)|java/util|Collection|remove(E)}} methods for adding to and removing from a <code>Collection</code> respectively. It also has the {{Javadoc:SE|module=java.base|name=toArray()|java/util|Collection|toArray()}} 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>).{{sfn|Bloch|2018|loc=Chapter §8 Item 8: Favor composition over inheritance|pp=87-92}} Finally, the 
{{Javadoc|module=java.base|package=java.util|class=Collection|member=contains(E)|text=contains(E e)|monotype=y}} method checks if a specified element exists in the <code>Collection</code>. 

The <code>Collection</code> interface is a subinterface of '''{{Javadoc|module=java.base|package=java.lang|class=Iterable|monotype=y}}''', so any <code>Collection</code> may be the target of a [[Foreach loop|for-each]] statement. (The <code>Iterable</code> interface provides the {{Javadoc|module=java.base|package=java.util|class=Iterable|member=iterator()|text=iterator()|monotype=y}} method used by for-each statements.) All <code>Collection</code>s implement '''{{Javadoc|module=java.base|package=java.util|class=Iterator|monotype=y}}''' to scan all of the elements in the <code>Collection</code>.

<code>Collection</code> is generic. Any <code>Collection</code> can store any {{code|Object}}. For example, any implementation of {{code|Collection<String>}} contains {{code|String}} objects. No casting is required when using the {{code|String}} objects from an implementation of <code>Collection<String></code>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/lang/Iterable.html |title=Iterable (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref> Note that the angled brackets {{code|< >}} can hold a type argument that specifies which type the <code>Collection</code> holds.{{sfn|Bloch|2018|loc=Chapter §5 Item 26: Don't use raw types|pp=117-122}}

=== Types of collection ===
There are several generic types of <code>Collection</code>: [[Queue (abstract data type)|Queue]]s, [[Map (computer science)|map]]s, [[List (abstract data type)|list]]s and [[Set (abstract data type)|set]]s.

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>.<ref name=":0" />

==List interface==
Lists are implemented in the collections framework via the '''{{Javadoc|module=java.base|package=java.util|class=List|monotype=y}}'''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.

===List implementations===
There are several concrete classes that implement <code>List</code>, including {{java|AbstractList}} and all of its corresponding subclasses, as well as {{java|CopyOnWriteArrayList}}.

====AbstractList class====
The direct subclasses of {{java|AbstractList}} class include {{java|AbstractSequentialList}}, {{java|ArrayList}} and {{java|Vector}}.

{{java|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.{{sfn|Bloch|2018|loc=Chapter §4 Item 20: Prefer interfaces to abstract classes|pp=99-103}}

=====ARRAYLIST CLASSES=====
The '''{{Javadoc|module=java.base|package=java.util|class=ArrayList|monotype=y}}''' 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.

=====LinkedList class=====
The '''{{Javadoc|module=java.base|package=java.util|class=LinkedList|monotype=y}}''' 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.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/List.html |title=List (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

=====Vector class=====
The {{java|Vector}} class has {{java|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 (data structure)|vector]] is generally not a [[Stack (abstract data type)|stack]].{{sfn|Bloch|2018|loc=Chapter §4 Item 18: Favor composition over inheritance|pp=87-92}} Composition would have been more appropriate in this scenario.{{sfn|Bloch|2018|loc=Chapter §4 Item 18: Favor composition over inheritance|pp=87-92}}

======Stack class======
The Stack class <code>[[inheritance (object-oriented programming)|extends]]</code> class '''{{Javadoc:SE|module=java.base|package=java.util|java/util|Vector}}''' with five operations that allow a <code>Vector</code> to be treated as a <code>Stack</code>.
Stacks are created using '''{{Javadoc|module=java.base|package=java.util|class=Stack|monotype=y}}'''. The <code>Stack</code> offers methods to put a new object on the <code>Stack</code> (method {{Javadoc:SE|module=java.base|name=push(E e)|java/util|Stack|push(E)}}) and to get objects from the <code>Stack</code> (method {{Javadoc:SE|module=java.base|name=pop()|java/util|Stack|pop()}}). A <code>Stack</code> returns the object according to [[Stack (abstract data type)|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 {{Javadoc:SE|module=java.base|name=push(E e)|java/util|Stack|push(E)}} and {{Javadoc:SE|module=java.base|name=pop()|java/util|Stack|pop()}} operations are provided, as well as a method ({{Javadoc:SE|module=java.base|name=peek()|java/util|Stack|peek()}}) to peek at the top item on the <code>Stack</code>, a method to test for whether the <code>Stack</code> is empty ({{Javadoc:SE|module=java.base|name=empty()|java/util|Stack|empty()}}), and a method to search the <code>Stack</code> for an item and discover how far it is from the top ({{Javadoc:SE|module=java.base|name=search(Object o)|java/util|Stack|search(java.lang.Object)}}). When a <code>Stack</code> is first created, it contains no items.

====CopyOnWriteArrayList class====
The {{code|CopyOnWriteArrayList}} extends the {{code|Object}} class, and does not extend any other classes. {{code|CopyOnWriteArrayList}} allows for thread-safety without performing excessive synchronization.{{sfn|Bloch|2018|loc=Chapter §11 Item 79: Avoid excessive synchronization|pp=317-322}} 

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 {{code|CopyOnWriteArrayList}} should not be used.{{sfn|Bloch|2018|loc=Chapter §11 Item 79: Avoid excessive synchronization|pp=317-322}} 

However synchronization can incur a performance overhead. For scenarios where synchronization is not mandatory, then the {{code|CopyOnWriteArrayList}} is a viable, thread-safe alternative to synchronization that leverages [[multi-core processor]]s and results in higher [[Central processing unit|CPU]] utilization.
{{sfn|Bloch|2018|loc=Chapter §11 Item 79: Avoid excessive synchronization|pp=317-322}}

==Queue interfaces==
The '''{{Javadoc|module=java.base|package=java.util|class=Queue|monotype=y}}''' 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 [[FIFO (computing and electronics)|first-in first-out]] system. This interface is implemented by <code>java.util.LinkedList</code>, '''{{Javadoc|module=java.base|package=java.util|class=ArrayDeque|monotype=y}}''', and '''{{Javadoc|module=java.base|package=java.util|class=PriorityQueue|monotype=y}}'''.

===Queue implementations===
====AbstractQueue class====
The direct subclasses of {{java|AbstractQueue}} class include {{java|ArrayBlockingQueue}}, {{java|ConcurrentLinkedQueue}}, {{java|DelayeQueue}}, {{java|LinkedBlockingDeque}},
{{java|LinkedBlockingQueue}}.
{{java|LinkedTransferQueue}} and 
{{java|PriorityBlockingQueue}}.

Note that {{java|ArrayDeque}} and {{java | 
ConcurrentLinkedDeque}} both extend {{java|AbstractCollection}} but do not extend any other abstract classes such as {{java|AbstractQueue}}.

{{java|AbstractQueue}} is an example of a ''skeletal implementation''.

=====PriorityQueue class=====
The <code>java.util.PriorityQueue</code> class implements <code>java.util.Queue</code>, but also alters it.{{sfn|Bloch|2018|loc=Chapter §9 Item 64: Refer to objects by their interfaces|pp=280-281}} <code>PriorityQueue</code> has an additional {{Javadoc|module=java.base|package=java.util.concurrent|class=PriorityQueue|member=comparator()|text=comparator()|monotype=y}} method.{{sfn|Bloch|2018|loc=Chapter §9 Item 64: Refer to objects by their interfaces|pp=280-281}} 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 {{Javadoc|module=java.base|package=java.lang|class=Comparable|member=compareTo(T)|monotype=y}} method in the elements, or a method given in the constructor. The class creates this by using a heap to keep the items sorted.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html |title=PriorityQueue (Java Platform SE 7) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

=====ConcurrentLinkedQueue class=====
The <code>java.util.concurrent.ConcurrentLinkedQueue</code> class extends {{java|java.util.AbstractQueue}}. <code>ConcurrentLinkedQueue</code> implements the {{java|java.util.Queue}} interface.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2 Concurrent collections|pp=84-85}}

The <code>ConcurrentLinkedQueue</code> class is a thread-safe collection, since for any an element placed inside a {{java|ConcurrentLinkedQueue}}, the Java Collection Library guarantees that the element is ''safely published'' by allowing any thread to get the element from the collection.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§3.5.3 Safe publication idioms|pp=52-53}} 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.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§3.5.3 Safe publication idioms|pp=52-53}} Safe publication usually requires synchronization of the publishing and consuming threads.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§3.5.3 Safe publication idioms|pp=52-53}}

===BlockingQueue interface===
The 
'''{{Javadoc|module=java.base|package=java.util.concurrent|class=BlockingQueue|monotype=y}}''' interface extends <code>Queue</code>.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2 Concurrent collections|pp=84-85}}

The {{java|BlockingQueue}} interface has the following direct sub-interfaces: {{java|BlockingDeque}} and {{java|TransferQueue}}. {{java|BlockingQueue}} works like a regular <code>Queue</code>, but additions to and removals from the <code>BlockingQueue</code> are blocking.{{sfn|Bloch|2018|loc=Chapter §11 Item 78: Synchronize access to shared mutable data|pp=325-329}} If 
{{Javadoc|module=java.base|package=java.util|class=Queue|member=remove(java.lang.Object)|text=remove(Object o)|monotype=y}} 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 {{Javadoc|module=java.base|package=java.util|class=Queue|member=add(java.lang.Object)|text=add(Object o)|monotype=y}} 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 {{Javadoc|module=java.base|package=java.util|class=BlockingQueue|member=take()|text=take()|monotype=y}} which removes and gets the head of the <code>BlockingQueue</code>, and waits until the <code>BlockingQueue</code> is no longer empty if required.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingQueue.html |title=BlockingQueue (Java Platform SE 7) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>{{sfn|Bloch|2018|loc=Chapter §11 Item 81: Prefer concurrency utilities to wait and notify|pp=325-329}}

===Double-ended queue (Deque) interfaces===
The {{java|Deque}} interface
extends the {{java|Queue}} interface.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.3.3 Deques and work stealing|p=92}} {{java|Deque}} creates a double-ended queue. While a regular {{java|Queue}} only allows insertions at the rear and removals at the front, the {{java|Deque}} allows insertions or removals to take place both at the front and the back. A {{java|Deque}} is like a {{java|Queue}} that can be used forwards or backwards, or both at once. Additionally, both a forwards and a backwards iterator can be generated. The {{java|Deque}} interface is implemented by <code>java.util.ArrayDeque</code> and <code>java.util.LinkedList</code>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html |title=Deque (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

====Deque implementations====
=====LinkedList class=====

<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 '''{{Javadoc|module=java.base|package=java.util|class=Deque|monotype=y}}''' interface, giving it more flexibility.<ref name="Queue Java Platform SE 7">{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Queue.html |title=Queue (Java Platform SE 7) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

=====ArrayDeque class=====

<code>ArrayDeque</code> implements the <code>Queue</code> as an array. Similar to <code>LinkedList</code>, <code>ArrayDeque</code> also implements the '''{{Javadoc|module=java.base|package=java.util|class=Deque|monotype=y}}''' interface.<ref name="Queue Java Platform SE 7"/>

====BlockingDeque interface====
The '''{{Javadoc:SE|module=java.base|package=java.util.concurrent|java/util/concurrent|BlockingDeque}}''' interface extends <code>java.util.concurrent.BlockingQueue</code>.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.3.3 Deques and work stealing|p=92}} {{java|BlockingDeque}} is similar to {{java|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 <code>Deque</code>. Insertions and removals can take place at both ends. The blocking function is combined with the <code>Deque</code> function.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingDeque.html |title=BlockingDeque (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

==Set interfaces==
Java's '''{{Javadoc|module=java.base|package=java.util|class=Set|monotype=y}}'''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 '''{{Javadoc|module=java.base|package=java.util|class=HashSet|monotype=y}}''', '''{{Javadoc|module=java.base|package=java.util|class=LinkedHashSet|monotype=y}}''', and '''{{Javadoc|module=java.base|package=java.util|class=TreeSet|monotype=y}}'''.

===Set interface implementations===
There are several implementations of the Set interface, including {{java|AbstractSet}} and its subclasses, and the final static inner class {{java|ConcurrentHashMap.KeySetView<K,V>}} (where {{java|K}} and {{java|V}} are formal type parameters).

==== AbstractSet ====
{{java|AbstractSet}} is a ''skeletal implementation'' for the {{java|Set}} interface.{{sfn|Bloch|2018|loc=Chapter §4 Item 20: Prefer interfaces to abstract classes|pp=99-103}}

Direct subclasses of {{java|AbstractSet}} include {{java|ConcurrentSkipListSet}}, {{java|CopyOnWriteArraySet}}, {{java|EnumSet}}, {{java|HashSet}} and {{java|TreeSet}}.

=====EnumSet class=====
The {{java|EnumSet}} class extends {{java|AbstractSet}}. The {{java|EnumSet}} class has no public constructors, and only contain static factory methods.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=5-9}} 

{{java|EnumSet}} contains the static factory method {{java|EnumSet.of()}}.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}} This method is an aggregation method.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=5-9}} It takes in several parameters, takes into account of the type of the parameters, then returns an instance with the appropriate type.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=5-9}} As of 2018, In Java SE8 OpenJDK implementation uses two implementations of {{java|EnumSet}} which are invisible to the client, which are {{java|RegularEnumSet}} and {{java|JumboEnumSet}}.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=5-9}} If the {{java|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.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=5-9}}

{{java|EnumSet}} is a good replacement for the ''bit fields'', which is a type of set, as described below.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}}

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.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}} 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.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}}

However, there are many problems with ''bit field representation'' approach. A bit field is less readable than an int enum constant.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}} Also, if the elements are represented by bit fields, it is impossible to iterate through all 
of these elements.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}}

A recommended alternative approach is to use an {{java|EnumSet}}, where an int enum is used instead of a ''bit field''.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}} This approach uses an {{java|EnumSet}} to represent the set of values that belong to the same {{java|Enum}} type.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}} Since the {{java|EnumSet}} implements the {{java|Set}} interface and no longer requires the use of bit-wise operations, this approach is more type-safe.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}} Furthermore, there are many static factories that allow for object instantiation, such as the method {{java|EnumSet.of()}} method.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}}

After the introduction of the {{java| EnumSet}}, the ''bit field representation'' approach is considered to be obsolete.{{sfn|Bloch|2018|loc=Chapter §5 Use EnumSet instead of bit fields|pp=169-170}}

=====HashSet class=====
<code>HashSet</code> uses a hash table. More specifically, it uses a '''{{Javadoc|module=java.base|package=java.util|class=LinkedHashMap|monotype=y}}''' to store the hashes and elements and to prevent duplicates.

======LinkedHashSet class======
The <code>java.util.LinkedHashSet</code> class extends {{java|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 <code>Set</code> is predictable.

=====CopyOnWriteArraySet class=====
{{code|CopyOnWriteArraySet}} is a concurrent replacement for a synchronized {{java|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 {{code|CopyOnWriteArrayList}} acts as the concurrent replacement for a synchronized {{java|List}}.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.3 CopyOnWriteArrayList|pp=86-89}}
On the other hand, similar to {{code|CopyOnWriteArrayList}}, {{code|CopyOnWriteArraySet}} should not be used when synchronization is mandatory.

===SortedSet interface===
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 {{Javadoc:SE|module=java.base|name=compareTo(T o)|java/lang|Comparable|compareTo(T)}} 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 {{Javadoc:SE|module=java.base|name=first()|java/util|SortedSet|first()}} and {{Javadoc:SE|module=java.base|name=last()|java/util|SortedSet|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 <code>SortedSet</code>. The <code>java.util.TreeSet</code> class implements the <code>SortedSet</code> interface.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html |title=SortedSet (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

====NavigableSet interface====
The '''{{Javadoc|module=java.base|package=java.util|class=NavigableSet|monotype=y}}''' interface extends the <code>java.util.SortedSet</code> interface and has a few additional methods. The {{Javadoc:SE|module=java.base|name=floor(E e)|java/util|NavigableSet|floor(E)}}, {{Javadoc:SE|module=java.base|name=ceiling(E e)|java/util|NavigableSet|ceiling(E)}}, {{Javadoc:SE|module=java.base|name=lower(E e)|java/util|NavigableSet|lower(E)}}, and {{Javadoc:SE|module=java.base|name=higher(E e)|java/util|NavigableSet|higher(E)}} 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>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/NavigableSet.html |title=NavigableSet (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06}}</ref>

=====TreeSet class=====
<code>java.util.TreeSet</code> uses a [[red–black tree]] implemented by a '''{{Javadoc|module=java.base|package=java.util|class=TreeMap|monotype=y}}'''. The red–black tree ensures that there are no duplicates. Additionally, it allows <code>TreeSet</code> to implement '''{{Javadoc|module=java.base|package=java.util|class=SortedSet|monotype=y}}'''.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Set.html |title=Set (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

=====ConcurrentSkipListSet class=====
{{code|ConcurrentSkipListSet}} acts as a concurrent replacement for implementations of a synchronized {{java|SortedSet}}. For example it replaces a {{java|TreeSet}} that has been wrapped by the {{java|synchronizedMap}} method. {{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2 ConcurrentCollections|pp=84-85}}

==Map interfaces==
Maps are defined by the '''{{Javadoc|module=java.base|package=java.util|class=Map|monotype=y}}''' interface in Java.

===Map interface implementations===
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 <code>Map</code> is essentially a <code>Set</code>. If it's just an increasing number, it becomes a list. 

Examples of {{java|Map}} implementations include '''{{Javadoc|module=java.base|package=java.util|class=HashMap|monotype=y}}''', '''{{Javadoc|module=java.base|package=java.util|class=LinkedHashMap|monotype=y}}''' , and '''{{Javadoc|module=java.base|package=java.util|class=TreeMap|monotype=y}}'''.

====AbstractMap class====

{{java|AbstractMap}} is an example of a ''skeletal implementation''.{{sfn|Bloch|2018|loc=Chapter §4 Item 20: Prefer interfaces to abstract classes|pp=99-103}} 

The direct subclasses of {{java|AbstractMap}} class include {{java|ConcurrentSkipListMap}}, {{java|EnumMap}}, {{java|HashMap}}, {{java|IdentityHashMap}}, {{java|TreeMap}} and {{java|WeakHashMap}}.

=====EnumMap=====
{{java|EnumMap}} extends {{java|AbstractMap}}. {{java|EnumMap}} has comparable speed with an ordinal-indexed array.{{sfn|Bloch|2018|loc=Chapter §6 Item 36: Use EnumMap instead of ordinal indexing|pp=171-175}} This is because {{java|EnumMap}} internally uses an array, with implementation details completely hidden from the developer.{{sfn|Bloch|2018|loc=Chapter §6 Item 36: Use EnumMap instead of ordinal indexing|pp=171-175}}  Hence, the EnumMap gets the type safety of a {{java|Map}} while the performance advantages of an array.{{sfn|Bloch|2018|loc=Chapter §6 Item 36: Use EnumMap instead of ordinal indexing|pp=171-175}}

=====HashMap=====
{{java|HashMap}} uses a [[hash table]]. The hashes of the keys are used to find the elements in various buckets. The {{java|HashMap}} is a hash-based collection. {{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}}

======LinkedHashMap======
{{java|LinkedHashMap}} extends {{java|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. {{java|LinkedHashMap}} 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>.{{sfn|Bloch|2018|loc=Chapter §44 Favor the use of standard functional interfaces|pp=199-202}} The <code>Map</code> removes its eldest entry whenever <code>removeEldestEntry</code> returns true.{{sfn|Bloch|2018|loc=Chapter §44 Favor the use of standard functional interfaces|pp=199-202}} The <code>removeEldestEntry</code> method can be overridden.{{sfn|Bloch|2018|loc=Chapter §44 Favor the use of standard functional interfaces|pp=199-202}}

=====TreeMap=====
{{java|TreeMap}}, in contrast to {{java|HashMap}} and {{java|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 <code>Map</code>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/Map.html |title=Map (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

=====ConcurrentHashMap=====
{{java|ConcurrentHashMap}} is similar to {{java|HashMap}} and is also a hash-based collection. {{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}} However, there are a number of differences, such as the differences in the locking strategy they use.

The {{java|ConcurrentHashMap}} uses a completely different locking strategy to provide improved scalability and concurrency.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}} {{java|ConcurrentHashMap}} does not synchronize every method using the same lock.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}} Instead, {{java|ConcurrentHashMap}} use a mechanism known as ''lock striping''.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}} This mechanism provides a finer-grained locking mechanism.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}} It also permits a higher degree of shared access.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2.1 ConcurrentHashMap|pp=85-86}}

=====ConcurrentSkipListMap class=====
{{code|ConcurrentSkipListMap }} acts as a concurrent replacement for implementations of a synchronized {{java|SortedMap}}. {{code|ConcurrentSkipListMap }} is very similar to {{code|ConcurrentSkipListSet}}, since {{code|ConcurrentSkipListMap }} replaces a {{java|TreeMap}} that has been wrapped by the {{java|synchronizedMap}} method.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2 ConcurrentCollections|pp=84-85}}

===Map subinterfaces===

====SortedMap interface====
The '''{{Javadoc|module=java.base|package=java.util|class=SortedMap|monotype=y}}''' 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 {{Javadoc:SE|module=java.base|name=firstKey()|java/util|SortedMap|firstKey()}} and {{Javadoc:SE|module=java.base|name=lastKey()|java/util|SortedMap|lastKey()}} methods respectively. Additionally, submaps can be created from minimum and maximum keys by using the {{Javadoc:SE|name=subMap(K fromKey, K toKey)|java/util|SortedMap|subMap(K,K)}} method. <code>SortedMap</code> is implemented by <code>java.util.TreeMap</code>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html |title=SortedMap (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

=====NavigableMap interface=====
The '''{{Javadoc|module=java.base|package=java.util|class=NavigableMap|monotype=y}}''' 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>.<ref>{{cite web|url=http://docs.oracle.com/javase/7/docs/api/java/util/NavigableMap.html |title=NavigableMap (Java Platform SE 7 ) |publisher=Docs.oracle.com |date=2013-06-06 |access-date=2013-08-16}}</ref>

====ConcurrentMap interface====
{{main article|Java ConcurrentMap}}
The '''{{Javadoc|module=java.base|package=java.util.concurrent|class=ConcurrentMap|monotype=y}}''' interface extends the <code>java.util.Map</code> interface. This interface a thread Safe {{java|Map}} interface, introduced as of Java programming language's [[Java Collections Framework]] version 1.5.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2 Concurrent collections|pp=84-85}}

==Extensions to the Java collections framework==
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.<ref>{{cite web|url=http://commons.apache.org/proper/commons-collections/ |title=Collections - Home |publisher=Commons.apache.org |date=2013-07-04 |access-date=2013-08-16}}</ref>

Google has released its own collections libraries as part of the [[Google Guava|guava libraries]].

==See also==
{{Portal|Computer programming}}
* [[Collection (abstract data type)|Collection]]
* [[Container (abstract data type)|Container]]
* [[Standard Template Library]]
* [[Java concurrency]]
* [[Java ConcurrentMap]]

==Citation==
{{Reflist|2}}

==References==
*{{cite book | title= "Effective Java: Programming Language Guide" |last=Bloch| first=Joshua| publisher=Addison-Wesley | edition=third | isbn=978-0134685991| year=2018}}
*{{cite book
 | last = Goetz
 | first = Brian
 | last2 = Peierls
 | first2 = Tim
 | last3 = Bloch
 | first3 = Joshua
 | last4 = Bowbeer
 | first4 = Joseph
 | last5 = Holmes
 | first5 = David
 | last6 = Lea
 | first6 = Doug
 | year = 2006
 | title = Java Concurrency in Practice
 | publisher = Addison Wesley
 | isbn = 0-321-34960-1
 |ol=OL25208908M
 | url=https://archive.org/details/javaconcurrencyi00goet
 }}

{{wikibooks|Java Programming|Collections}}
{{Java (Sun)}}

{{Prone to spam|date=November 2018}}
<!--     {{No more links}}

       Please be cautious adding more external links.

Wikipedia is not a collection of links and should not be used for advertising.

     Excessive or inappropriate links will be removed.

 See [[Wikipedia:External links]] and [[Wikipedia:Spam]] for details.

If there are already suitable links, propose additions or replacements on
the article's talk page.

-->

[[Category:JDK components]]
[[Category:Data structures libraries and frameworks]]