1 <!DOCTYPE html>
2 <!--
3 Copyright (c) 1998, 2017, Oracle and/or its affiliates. All rights reserved.
4 DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5
6 This code is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License version 2 only, as
8 published by the Free Software Foundation. Oracle designates this
9 particular file as subject to the "Classpath" exception as provided
10 by Oracle in the LICENSE file that accompanied this code.
11
12 This code is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 version 2 for more details (a copy is included in the LICENSE file that
16 accompanied this code).
17
18 You should have received a copy of the GNU General Public License version
19 2 along with this work; if not, write to the Free Software Foundation,
20 Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21
22 Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
23 or visit www.oracle.com if you need additional information or have any
24 questions.
25 -->
26 <html lang="en-US">
27 <head>
28 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
29 <title>Collections Framework Overview</title>
30 <style>
31 #impls {
32 border: 1px solid black;
33 border-collapse: collapse;
34 margin: 0 auto;
35 }
36 #impls caption {
37 font-weight: bold;
38 font-size: smaller;
39 }
40 #impls, #impls th, #impls td {
41 border: 1px solid black;
42 padding: 2px .5em;
43 }
44 #impls tbody th {
45 font-weight: normal;
46 text-align:left;
47 }
48 </style>
49 </head>
50 <body>
51 <h1>Collections Framework Overview</h1>
52 <!-- Body text begins here -->
53 <h2>Introduction</h2>
54 The Java platform includes a <i>collections framework</i>. A
55 <i>collection</i> is an object that represents a group of objects
56 (such as the classic <a href="../ArrayList.html">ArrayList</a> class).
57 A collections framework is a unified architecture for representing
58 and manipulating collections, enabling collections to be
59 manipulated independently of implementation details.
60 <p>The primary advantages of a collections framework are that
61 it:</p>
62 <ul>
63 <li><strong>Reduces programming effort</strong> by providing data
64 structures and algorithms so you don't have to write them
65 yourself.</li>
66 <li><strong>Increases performance</strong> by providing
67 high-performance implementations of data structures and algorithms.
68 Because the various implementations of each interface are
69 interchangeable, programs can be tuned by switching
70 implementations.</li>
71 <li><strong>Provides interoperability between unrelated
72 APIs</strong> by establishing a common language to pass collections
73 back and forth.</li>
74 <li><strong>Reduces the effort required to learn APIs</strong> by
75 requiring you to learn multiple ad hoc collection APIs.</li>
76 <li><strong>Reduces the effort required to design and implement
77 APIs</strong> by not requiring you to produce ad hoc collections
78 APIs.</li>
79 <li><strong>Fosters software reuse</strong> by providing a standard
80 interface for collections and algorithms with which to manipulate
81 them.</li>
82 </ul>
83 <p>The collections framework consists of:</p>
84 <ul>
85 <li><strong>Collection interfaces</strong>. Represent different
86 types of collections, such as sets, lists, and maps. These
87 interfaces form the basis of the framework.</li>
88 <li><strong>General-purpose implementations</strong>. Primary
89 implementations of the collection interfaces.</li>
90 <li><strong>Legacy implementations</strong>. The collection classes
91 from earlier releases, <code>Vector</code> and <code>Hashtable</code>, were
92 retrofitted to implement the collection interfaces.</li>
93 <li><strong>Special-purpose implementations</strong>.
94 Implementations designed for use in special situations. These
95 implementations display nonstandard performance characteristics,
96 usage restrictions, or behavior.</li>
97 <li><strong>Concurrent implementations</strong>. Implementations
98 designed for highly concurrent use.</li>
99 <li><strong>Wrapper implementations</strong>. Add functionality,
100 such as synchronization, to other implementations.</li>
101 <li><strong>Convenience implementations</strong>. High-performance
102 "mini-implementations" of the collection interfaces.</li>
103 <li><strong>Abstract implementations</strong>. Partial
104 implementations of the collection interfaces to facilitate custom
105 implementations.</li>
106 <li><strong>Algorithms</strong>. Static methods that perform useful
107 functions on collections, such as sorting a list.</li>
108 <li><strong>Infrastructure</strong>. Interfaces that provide
109 essential support for the collection interfaces.</li>
110 <li><strong>Array Utilities</strong>. Utility functions for arrays
111 of primitive types and reference objects. Not, strictly speaking, a
112 part of the collections framework, this feature was added to the
113 Java platform at the same time as the collections framework and
114 relies on some of the same infrastructure.</li>
115 </ul>
116 <hr />
117 <h2>Collection Interfaces</h2>
118 <p>The <i>collection interfaces</i> are divided into two groups.
119 The most basic interface, <code><a href=
120 "../Collection.html">java.util.Collection</a></code>,
121 has the following descendants:</p>
122 <ul>
123 <li><code><a href=
124 "../Set.html">java.util.Set</a></code></li>
125 <li><code><a href=
126 "../SortedSet.html">java.util.SortedSet</a></code></li>
127 <li><code><a href=
128 "../NavigableSet.html">java.util.NavigableSet</a></code></li>
129 <li><code><a href=
130 "../Queue.html">java.util.Queue</a></code></li>
131 <li><code><a href=
132 "../concurrent/BlockingQueue.html">java.util.concurrent.BlockingQueue</a></code></li>
133 <li><code><a href=
134 "../concurrent/TransferQueue.html">java.util.concurrent.TransferQueue</a></code></li>
135 <li><code><a href=
136 "../Deque.html">java.util.Deque</a></code></li>
137 <li><code><a href=
138 "../concurrent/BlockingDeque.html">java.util.concurrent.BlockingDeque</a></code></li>
139 </ul>
140 <p>The other collection interfaces are based on <code><a href=
141 "../Map.html">java.util.Map</a></code> and are
142 not true collections. However, these interfaces contain
143 <i>collection-view</i> operations, which enable them to be
144 manipulated as collections. <code>Map</code> has the following
145 offspring:</p>
146 <ul>
147 <li><code><a href=
148 "../SortedMap.html">java.util.SortedMap</a></code></li>
149 <li><code><a href=
150 "../NavigableMap.html">java.util.NavigableMap</a></code></li>
151 <li><code><a href=
152 "../concurrent/ConcurrentMap.html">java.util.concurrent.ConcurrentMap</a></code></li>
153 <li><code><a href=
154 "../concurrent/ConcurrentNavigableMap.html">java.util.concurrent.ConcurrentNavigableMap</a></code></li>
155 </ul>
156 <p>Many of the modification methods in the collection interfaces
157 are labeled <i>optional</i>. Implementations are permitted to not
158 perform one or more of these operations, throwing a runtime
159 exception (<code>UnsupportedOperationException</code>) if they are
160 attempted. The documentation for each implementation must specify
161 which optional operations are supported. Several terms are
162 introduced to aid in this specification:</p>
163 <ul>
164 <li>Collections that do not support modification operations (such
165 as <code>add</code>, <code>remove</code> and <code>clear</code>) are referred
166 to as <i>unmodifiable</i>. Collections that are not unmodifiable
167 are <i>modifiable.</i></li>
168 <li>Collections that additionally guarantee that no change in the
169 <code>Collection</code> object will be visible are referred to as
170 <i>immutable</i>. Collections that are not immutable are
171 <i>mutable</i>.</li>
172 <li>Lists that guarantee that their size remains constant even
173 though the elements can change are referred to as
174 <i>fixed-size</i>. Lists that are not fixed-size are referred to as
175 <i>variable-size</i>.</li>
176 <li>Lists that support fast (generally constant time) indexed
177 element access are known as <i>random access</i> lists. Lists that
178 do not support fast indexed element access are known as
179 <i>sequential access</i> lists. The <code><a href=
180 "../RandomAccess.html">RandomAccess</a></code>
181 marker interface enables lists to advertise the fact that they
182 support random access. This enables generic algorithms to change
183 their behavior to provide good performance when applied to either
184 random or sequential access lists.</li>
185 </ul>
186 <p>Some implementations restrict what elements (or in the case of
187 <code>Maps</code>, keys and values) can be stored. Possible
188 restrictions include requiring elements to:</p>
189 <ul>
190 <li>Be of a particular type.</li>
191 <li>Be not null.</li>
192 <li>Obey some arbitrary predicate.</li>
193 </ul>
194 <p>Attempting to add an element that violates an implementation's
195 restrictions results in a runtime exception, typically a
196 <code>ClassCastException</code>, an <code>IllegalArgumentException</code>,
197 or a <code>NullPointerException</code>. Attempting to remove or test
198 for the presence of an element that violates an implementation's
199 restrictions can result in an exception. Some restricted
200 collections permit this usage.</p>
201 <hr>
202 <h2>Collection Implementations</h2>
203 <p>Classes that implement the collection interfaces typically have
204 names in the form of
205 <<em>Implementation-style</em>><<em>Interface</em>>.
206 The general purpose implementations are summarized in the following
207 table:</p>
208 <table id="impls">
209 <caption>General purpose implementations</caption>
210 <thead>
211 <tr>
212 <th scope="col">Interface</th>
213 <th scope="col">Hash Table</th>
214 <th scope="col">Resizable Array</th>
215 <th scope="col">Balanced Tree</th>
216 <th scope="col">Linked List</th>
217 <th scope="col">Hash Table + Linked List</th>
218 </tr>
219 </thead>
220 <tbody>
221 <tr>
222 <th scope="row"><code>Set</code></th>
223 <td><a href="../HashSet.html"><code>HashSet</code></a></td>
224 <td> </td>
225 <td><a href="../TreeSet.html"><code>TreeSet</code></a></td>
226 <td> </td>
227 <td><a href=
228 "../LinkedHashSet.html"><code>LinkedHashSet</code></a></td>
229 </tr>
230 <tr>
231 <th scope="row"><code>List</code></th>
232 <td> </td>
233 <td><a href="../ArrayList.html"><code>ArrayList</code></a></td>
234 <td> </td>
235 <td><a href="../LinkedList.html"><code>LinkedList</code></a></td>
236 <td> </td>
237 </tr>
238 <tr>
239 <th scope="row"><code>Deque</code></th>
240 <td> </td>
241 <td><a href="../ArrayDeque.html"><code>ArrayDeque</code></a></td>
242 <td> </td>
243 <td><a href="../LinkedList.html"><code>LinkedList</code></a></td>
244 <td> </td>
245 </tr>
246 <tr>
247 <th scope="row"><code>Map</code></th>
248 <td><a href="../HashMap.html"><code>HashMap</code></a></td>
249 <td> </td>
250 <td><a href="../TreeMap.html"><code>TreeMap</code></a></td>
251 <td> </td>
252 <td><a href="../LinkedHashMap.html"><code>LinkedHashMap</code></a></td>
253 </tr>
254 </tbody>
255 </table>
256 <p>The general-purpose implementations support all of the
257 <i>optional operations</i> in the collection interfaces and have no
258 restrictions on the elements they may contain. They are
259 unsynchronized, but the <code>Collections</code> class contains static
260 factories called <a href=
261 "../Collections.html#synchronizedCollection-java.util.Collection-">
262 <em>synchronization wrappers</em></a> that can be used to add
263 synchronization to many unsynchronized collections. All of the new
264 implementations have <i>fail-fast iterators</i>, which detect
265 invalid concurrent modification, and fail quickly and cleanly
266 (rather than behaving erratically).</p>
267 <p>The <code>AbstractCollection</code>, <code>AbstractSet</code>,
268 <code>AbstractList</code>, <code>AbstractSequentialList</code> and
269 <code>AbstractMap</code> classes provide basic implementations of the
270 core collection interfaces, to minimize the effort required to
271 implement them. The API documentation for these classes describes
272 precisely how each method is implemented so the implementer knows
273 which methods must be overridden, given the performance of the
274 basic operations of a specific implementation.</p>
275 <hr>
276 <h2>Concurrent Collections</h2>
277 <p>Applications that use collections from more than one thread must
278 be carefully programmed. In general, this is known as <i>concurrent
279 programming</i>. The Java platform includes extensive support for
280 concurrent programming. See <a href=
281 "../concurrent/package-summary.html">Java Concurrency
282 Utilities</a> for details.</p>
283 <p>Collections are so frequently used that various concurrent
284 friendly interfaces and implementations of collections are included
285 in the APIs. These types go beyond the synchronization wrappers
286 discussed previously to provide features that are frequently needed
287 in concurrent programming.</p>
288 <p>These concurrent-aware interfaces are available:</p>
289 <ul>
290 <li><code><a href=
291 "../concurrent/BlockingQueue.html">BlockingQueue</a></code></li>
292 <li><code><a href=
293 "../concurrent/TransferQueue.html">TransferQueue</a></code></li>
294 <li><code><a href=
295 "../concurrent/BlockingDeque.html">BlockingDeque</a></code></li>
296 <li><code><a href=
297 "../concurrent/ConcurrentMap.html">ConcurrentMap</a></code></li>
298 <li><code><a href=
299 "../concurrent/ConcurrentNavigableMap.html">ConcurrentNavigableMap</a></code></li>
300 </ul>
301 <p>The following concurrent-aware implementation classes are
302 available. See the API documentation for the correct usage of these
303 implementations.</p>
304 <ul>
305 <li><code><a href=
306 "../concurrent/LinkedBlockingQueue.html">LinkedBlockingQueue</a></code></li>
307 <li><code><a href=
308 "../concurrent/ArrayBlockingQueue.html">ArrayBlockingQueue</a></code></li>
309 <li><code><a href=
310 "../concurrent/PriorityBlockingQueue.html">PriorityBlockingQueue</a></code></li>
311 <li><code><a href=
312 "../concurrent/DelayQueue.html">DelayQueue</a></code></li>
313 <li><code><a href=
314 "../concurrent/SynchronousQueue.html">SynchronousQueue</a></code></li>
315 <li><a href=
316 "../concurrent/LinkedBlockingDeque.html"><code>LinkedBlockingDeque</code></a></li>
317 <li><a href=
318 "../concurrent/LinkedTransferQueue.html"><code>LinkedTransferQueue</code></a></li>
319 <li><code><a href=
320 "../concurrent/CopyOnWriteArrayList.html">CopyOnWriteArrayList</a></code></li>
321 <li><code><a href=
322 "../concurrent/CopyOnWriteArraySet.html">CopyOnWriteArraySet</a></code></li>
323 <li><code><a href=
324 "../concurrent/ConcurrentSkipListSet.html">ConcurrentSkipListSet</a></code></li>
325 <li><code><a href=
326 "../concurrent/ConcurrentHashMap.html">ConcurrentHashMap</a></code></li>
327 <li><code><a href=
328 "../concurrent/ConcurrentSkipListMap.html">ConcurrentSkipListMap</a></code></li>
329 </ul>
330 <hr>
331 <h2>Design Goals</h2>
332 <p>The main design goal was to produce an API that was small in
333 size and, more importantly, in "conceptual weight." It
334 was critical that the new functionality not seem too different to
335 current Java programmers; it had to augment current facilities,
336 rather than replace them. At the same time, the new API had to be
337 powerful enough to provide all the advantages described
338 previously.</p>
339 <p>To keep the number of core interfaces small, the interfaces do
340 not attempt to capture such subtle distinctions as mutability,
341 modifiability, and resizability. Instead, certain calls in the core
342 interfaces are <i>optional</i>, enabling implementations to throw
343 an <code>UnsupportedOperationException</code> to indicate that they do
344 not support a specified optional operation. Collection implementers
345 must clearly document which optional operations are supported by an
346 implementation.</p>
347 <p>To keep the number of methods in each core interface small, an
348 interface contains a method only if either:</p>
349 <ul>
350 <li>It is a truly <i>fundamental operation</i>: a basic operations
351 in terms of which others could be reasonably defined,</li>
352 <li>There is a compelling performance reason why an important
353 implementation would want to override it.</li>
354 </ul>
355 <p>It was critical that all reasonable representations of
356 collections interoperate well. This included arrays, which cannot
357 be made to implement the <code>Collection</code> interface directly
358 without changing the language. Thus, the framework includes methods
359 to enable collections to be moved into arrays, arrays to be viewed
360 as collections, and maps to be viewed as collections.</p>
361 <hr>
362 <p style="font-size:smaller">
363 Copyright © 1998, 2017, Oracle and/or its affiliates. 500 Oracle Parkway<br>
364 Redwood Shores, CA 94065 USA. All rights reserved.</p>
365 <!-- Body text ends here -->
366 </body>
367 </html>