Java collections framework: Difference between revisions

Revision as of 13:01, 25 June 2023

Latest revision as of 07:37, 25 June 2025

(20 intermediate revisions by 12 users not shown)

Line 11:

== 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 instatiateinstantiate {{code|Collection<Object>}} as an {{code|ArrayList<>}} object by using the [[Generics in Java#Diamond_operatorDiamond 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}}

Line 84:

{{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 have animplement '''{{Javadoc|module=java.base|package=java.util|class=Iterator|monotype=y}}''' that goesto throughscan 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 ===

Line 100:

==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===

Line 110:

{{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}}

=====ArrayListARRAYLIST classCLASSES=====

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.

Line 134:

==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===

Line 144:

Note that {{java|ArrayDeque}} and {{java |

ConcurrentLinkedDeque}} both extend {{java|AbstractCollection}} but do not extend any other abstactabstract 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}}, Hence,. <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}}

Line 158:

===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}} and can be used more flexibly.

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

{{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

The {{java|java.util.Deque}} interface extends the {{java|Queue}} interface. {{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.3.3 Deques and work stealing|p=92}} {{java|java.util.Deque}} creates a double-ended queue. While a regular <code>{{java|Queue</code>}} 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 <code>{{java|Deque</code>}} is like a <code>{{java|Queue</code>}} 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>{{cite web|urlname=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>

====BlockingDeque interface====

The '''{{Javadoc:SE|module=java.base|package=java.util.concurrent|java/util/concurrent|BlockingDeque}}''' interface works similarly toextends <code>java.util.concurrent.BlockingQueue</code>.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.3.3 TheDeques 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 are provided. However, the interface also provides the flexibility of a {{java|<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).

Line 190:

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}}

Line 200:

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 sychronizationsynchronization is mandatory.

===SortedSet interface===

Line 227:

=====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|sychronizedMapsynchronizedMap}} 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===

Line 241:

{{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=====

Line 247 ⟶ 250:

======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=====

Line 255 ⟶ 258:

{{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|sychronizedMapsynchronizedMap}} method.{{sfn|Goetz|Peierls|Bloch|Bowbeer|2006|loc=§5.2 ConcurrentCollections|pp=84-85}}

===Map subinterfaces===

Line 287 ⟶ 290:

==Citation==

{{Reflist|2}}

==References==

Line 332 ⟶ 333:

-->

[[Category:JavaJDK (programming language)components]]

[[Category:Data structures libraries and frameworks]]