Mercurial > hg > openjdk > jdk9 > jdk
view src/java.base/share/classes/java/util/doc-files/coll-overview.html @ 17229:bec8ca52804c
8177788: migrate collections technotes/guides into java/util/doc-files
Reviewed-by: mchung, bchristi, martin
author | smarks |
---|---|
date | Fri, 19 May 2017 14:46:50 -0700 |
parents | |
children |
line wrap: on
line source
<?xml version="1.0" encoding="utf-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <!-- Copyright (c) 1998, 2017, Oracle and/or its affiliates. All rights reserved. DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. This code is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License version 2 only, as published by the Free Software Foundation. Oracle designates this particular file as subject to the "Classpath" exception as provided by Oracle in the LICENSE file that accompanied this code. This code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License version 2 for more details (a copy is included in the LICENSE file that accompanied this code). You should have received a copy of the GNU General Public License version 2 along with this work; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA or visit www.oracle.com if you need additional information or have any questions. --> <html lang="en-US" xmlns="http://www.w3.org/1999/xhtml" xml:lang= "en-US"> <head> <title>Collections Framework Overview</title> </head> <body> <h1>Collections Framework Overview</h1> <!-- Body text begins here --> <h2>Introduction</h2> The Java platform includes a <i>collections framework</i>. A <i>collection</i> is an object that represents a group of objects (such as the classic <a href="../ArrayList.html">ArrayList</a> class). A collections framework is a unified architecture for representing and manipulating collections, enabling collections to be manipulated independently of implementation details. <p>The primary advantages of a collections framework are that it:</p> <ul> <li><strong>Reduces programming effort</strong> by providing data structures and algorithms so you don't have to write them yourself.</li> <li><strong>Increases performance</strong> by providing high-performance implementations of data structures and algorithms. Because the various implementations of each interface are interchangeable, programs can be tuned by switching implementations.</li> <li><strong>Provides interoperability between unrelated APIs</strong> by establishing a common language to pass collections back and forth.</li> <li><strong>Reduces the effort required to learn APIs</strong> by requiring you to learn multiple ad hoc collection APIs.</li> <li><strong>Reduces the effort required to design and implement APIs</strong> by not requiring you to produce ad hoc collections APIs.</li> <li><strong>Fosters software reuse</strong> by providing a standard interface for collections and algorithms with which to manipulate them.</li> </ul> <p>The collections framework consists of:</p> <ul> <li><strong>Collection interfaces</strong>. Represent different types of collections, such as sets, lists, and maps. These interfaces form the basis of the framework.</li> <li><strong>General-purpose implementations</strong>. Primary implementations of the collection interfaces.</li> <li><strong>Legacy implementations</strong>. The collection classes from earlier releases, <tt>Vector</tt> and <tt>Hashtable</tt>, were retrofitted to implement the collection interfaces.</li> <li><strong>Special-purpose implementations</strong>. Implementations designed for use in special situations. These implementations display nonstandard performance characteristics, usage restrictions, or behavior.</li> <li><strong>Concurrent implementations</strong>. Implementations designed for highly concurrent use.</li> <li><strong>Wrapper implementations</strong>. Add functionality, such as synchronization, to other implementations.</li> <li><strong>Convenience implementations</strong>. High-performance "mini-implementations" of the collection interfaces.</li> <li><strong>Abstract implementations</strong>. Partial implementations of the collection interfaces to facilitate custom implementations.</li> <li><strong>Algorithms</strong>. Static methods that perform useful functions on collections, such as sorting a list.</li> <li><strong>Infrastructure</strong>. Interfaces that provide essential support for the collection interfaces.</li> <li><strong>Array Utilities</strong>. Utility functions for arrays of primitive types and reference objects. Not, strictly speaking, a part of the collections framework, this feature was added to the Java platform at the same time as the collections framework and relies on some of the same infrastructure.</li> </ul> <hr /> <h2>Collection Interfaces</h2> <p>The <i>collection interfaces</i> are divided into two groups. The most basic interface, <tt><a href= "../Collection.html">java.util.Collection</a></tt>, has the following descendants:</p> <ul> <li><tt><a href= "../Set.html">java.util.Set</a></tt></li> <li><tt><a href= "../SortedSet.html">java.util.SortedSet</a></tt></li> <li><tt><a href= "../NavigableSet.html">java.util.NavigableSet</a></tt></li> <li><tt><a href= "../Queue.html">java.util.Queue</a></tt></li> <li><tt><a href= "../concurrent/BlockingQueue.html">java.util.concurrent.BlockingQueue</a></tt></li> <li><tt><a href= "../concurrent/TransferQueue.html">java.util.concurrent.TransferQueue</a></tt></li> <li><tt><a href= "../Deque.html">java.util.Deque</a></tt></li> <li><tt><a href= "../concurrent/BlockingDeque.html">java.util.concurrent.BlockingDeque</a></tt></li> </ul> <p>The other collection interfaces are based on <tt><a href= "../Map.html">java.util.Map</a></tt> and are not true collections. However, these interfaces contain <i>collection-view</i> operations, which enable them to be manipulated as collections. <tt>Map</tt> has the following offspring:</p> <ul> <li><tt><a href= "../SortedMap.html">java.util.SortedMap</a></tt></li> <li><tt><a href= "../NavigableMap.html">java.util.NavigableMap</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentMap.html">java.util.concurrent.ConcurrentMap</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentNavigableMap.html">java.util.concurrent.ConcurrentNavigableMap</a></tt></li> </ul> <p>Many of the modification methods in the collection interfaces are labeled <i>optional</i>. Implementations are permitted to not perform one or more of these operations, throwing a runtime exception (<tt>UnsupportedOperationException</tt>) if they are attempted. The documentation for each implementation must specify which optional operations are supported. Several terms are introduced to aid in this specification:</p> <ul> <li>Collections that do not support modification operations (such as <tt>add</tt>, <tt>remove</tt> and <tt>clear</tt>) are referred to as <i>unmodifiable</i>. Collections that are not unmodifiable are <i>modifiable.</i></li> <li>Collections that additionally guarantee that no change in the <tt>Collection</tt> object will be visible are referred to as <i>immutable</i>. Collections that are not immutable are <i>mutable</i>.</li> <li>Lists that guarantee that their size remains constant even though the elements can change are referred to as <i>fixed-size</i>. Lists that are not fixed-size are referred to as <i>variable-size</i>.</li> <li>Lists that support fast (generally constant time) indexed element access are known as <i>random access</i> lists. Lists that do not support fast indexed element access are known as <i>sequential access</i> lists. The <tt><a href= "../RandomAccess.html">RandomAccess</a></tt> marker interface enables lists to advertise the fact that they support random access. This enables generic algorithms to change their behavior to provide good performance when applied to either random or sequential access lists.</li> </ul> <p>Some implementations restrict what elements (or in the case of <tt>Maps</tt>, keys and values) can be stored. Possible restrictions include requiring elements to:</p> <ul> <li>Be of a particular type.</li> <li>Be not null.</li> <li>Obey some arbitrary predicate.</li> </ul> <p>Attempting to add an element that violates an implementation's restrictions results in a runtime exception, typically a <tt>ClassCastException</tt>, an <tt>IllegalArgumentException</tt>, or a <tt>NullPointerException</tt>. Attempting to remove or test for the presence of an element that violates an implementation's restrictions can result in an exception. Some restricted collections permit this usage.</p> <hr /> <h2>Collection Implementations</h2> <p>Classes that implement the collection interfaces typically have names in the form of <<em>Implementation-style</em>><<em>Interface</em>>. The general purpose implementations are summarized in the following table:</p> <table border="2" summary= "general purpose implementations and interfaces" align="center"> <thead> <tr> <th id="interfaces">Interface</th> <th id="hashtable">Hash Table</th> <th id="resizablearray">Resizable Array</th> <th id="balancedtree">Balanced Tree</th> <th id="linkedlist">Linked List</th> <th id="hashtableandlinkedlist">Hash Table + Linked List</th> </tr> <tr> <td headers="interfaces"><code>Set</code></td> <td headers="hashtable"><a href= "../HashSet.html"><tt>HashSet</tt></a></td> <td headers="resizablearray"> </td> <td headers="balancedtree"><a href= "../TreeSet.html"><tt>TreeSet</tt></a></td> <td headers="linkedlist"> </td> <td headers="hashtableandlinkedlist"><a href= "../LinkedHashSet.html"><tt>LinkedHashSet</tt></a></td> </tr> <tr> <td headers="interfaces"><code>List</code></td> <td headers="hashtable"> </td> <td headers="resizablearray"><a href= "../ArrayList.html"><tt>ArrayList</tt></a></td> <td headers="balancedtree"> </td> <td headers="linkedlist"><a href= "../LinkedList.html"><tt>LinkedList</tt></a></td> <td headers="hashtableandlinkedlist"> </td> </tr> <tr> <td headers="interfaces"><code>Deque</code></td> <td headers="hashtable"> </td> <td headers="resizablearray"><a href= "../ArrayDeque.html"><tt>ArrayDeque</tt></a></td> <td headers="balancedtree"> </td> <td headers="linkedlist"><a href= "../LinkedList.html"><tt>LinkedList</tt></a></td> <td headers="hashtableandlinkedlist"> </td> </tr> <tr> <td headers="interfaces"><code>Map</code></td> <td headers="hashtable"><a href= "../HashMap.html"><tt>HashMap</tt></a></td> <td headers="resizablearray"> </td> <td headers="balancedtree"><a href= "../TreeMap.html"><tt>TreeMap</tt></a></td> <td headers="linkedlist"> </td> <td headers="hashtableandlinkedlist"><a href= "../LinkedHashMap.html"><tt>LinkedHashMap</tt></a></td> </tr> </thead> </table> <p>The general-purpose implementations support all of the <i>optional operations</i> in the collection interfaces and have no restrictions on the elements they may contain. They are unsynchronized, but the <tt>Collections</tt> class contains static factories called <a href= "../Collections.html#synchronizedCollection-java.util.Collection-"> <em>synchronization wrappers</em></a> that can be used to add synchronization to many unsynchronized collections. All of the new implementations have <i>fail-fast iterators</i>, which detect invalid concurrent modification, and fail quickly and cleanly (rather than behaving erratically).</p> <p>The <tt>AbstractCollection</tt>, <tt>AbstractSet</tt>, <tt>AbstractList</tt>, <tt>AbstractSequentialList</tt> and <tt>AbstractMap</tt> classes provide basic implementations of the core collection interfaces, to minimize the effort required to implement them. The API documentation for these classes describes precisely how each method is implemented so the implementer knows which methods must be overridden, given the performance of the basic operations of a specific implementation.</p> <hr /> <h2>Concurrent Collections</h2> <p>Applications that use collections from more than one thread must be carefully programmed. In general, this is known as <i>concurrent programming</i>. The Java platform includes extensive support for concurrent programming. See <a href= "../concurrent/package-summary.html">Java Concurrency Utilities</a> for details.</p> <p>Collections are so frequently used that various concurrent friendly interfaces and implementations of collections are included in the APIs. These types go beyond the synchronization wrappers discussed previously to provide features that are frequently needed in concurrent programming.</p> <p>These concurrent-aware interfaces are available:</p> <ul> <li><tt><a href= "../concurrent/BlockingQueue.html">BlockingQueue</a></tt></li> <li><tt><a href= "../concurrent/TransferQueue.html">TransferQueue</a></tt></li> <li><tt><a href= "../concurrent/BlockingDeque.html">BlockingDeque</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentMap.html">ConcurrentMap</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentNavigableMap.html">ConcurrentNavigableMap</a></tt></li> </ul> <p>The following concurrent-aware implementation classes are available. See the API documentation for the correct usage of these implementations.</p> <ul> <li><tt><a href= "../concurrent/LinkedBlockingQueue.html">LinkedBlockingQueue</a></tt></li> <li><tt><a href= "../concurrent/ArrayBlockingQueue.html">ArrayBlockingQueue</a></tt></li> <li><tt><a href= "../concurrent/PriorityBlockingQueue.html">PriorityBlockingQueue</a></tt></li> <li><tt><a href= "../concurrent/DelayQueue.html">DelayQueue</a></tt></li> <li><tt><a href= "../concurrent/SynchronousQueue.html">SynchronousQueue</a></tt></li> <li><a href= "../concurrent/LinkedBlockingDeque.html"><tt>LinkedBlockingDeque</tt></a></li> <li><a href= "../concurrent/LinkedTransferQueue.html"><tt>LinkedTransferQueue</tt></a></li> <li><tt><a href= "../concurrent/CopyOnWriteArrayList.html">CopyOnWriteArrayList</a></tt></li> <li><tt><a href= "../concurrent/CopyOnWriteArraySet.html">CopyOnWriteArraySet</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentSkipListSet.html">ConcurrentSkipListSet</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentHashMap.html">ConcurrentHashMap</a></tt></li> <li><tt><a href= "../concurrent/ConcurrentSkipListMap.html">ConcurrentSkipListMap</a></tt></li> </ul> <hr /> <h2>Design Goals</h2> <p>The main design goal was to produce an API that was small in size and, more importantly, in "conceptual weight." It was critical that the new functionality not seem too different to current Java programmers; it had to augment current facilities, rather than replace them. At the same time, the new API had to be powerful enough to provide all the advantages described previously.</p> <p>To keep the number of core interfaces small, the interfaces do not attempt to capture such subtle distinctions as mutability, modifiability, and resizability. Instead, certain calls in the core interfaces are <i>optional</i>, enabling implementations to throw an <tt>UnsupportedOperationException</tt> to indicate that they do not support a specified optional operation. Collection implementers must clearly document which optional operations are supported by an implementation.</p> <p>To keep the number of methods in each core interface small, an interface contains a method only if either:</p> <ul> <li>It is a truly <i>fundamental operation</i>: a basic operations in terms of which others could be reasonably defined,</li> <li>There is a compelling performance reason why an important implementation would want to override it.</li> </ul> <p>It was critical that all reasonable representations of collections interoperate well. This included arrays, which cannot be made to implement the <tt>Collection</tt> interface directly without changing the language. Thus, the framework includes methods to enable collections to be moved into arrays, arrays to be viewed as collections, and maps to be viewed as collections.</p> <hr /> <p style="font-size:smaller"> Copyright © 1998, 2017, Oracle and/or its affiliates. 500 Oracle Parkway<br /> Redwood Shores, CA 94065 USA. All rights reserved.</p> <!-- Body text ends here --> </body> </html>