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