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>