Java collections framework: Difference between revisions

Revision as of 22:03, 25 June 2023

Revision as of 22:22, 25 June 2023

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>

Line 86:

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 an '''{{Javadoc|module=java.base|package=java.util|class=Iterator|monotype=y}}''' that goes through 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 149:

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

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

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

Line 199:

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

Line 240:

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

=====HashMap=====

Line 246:

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

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