# HG changeset patch # User smarks # Date 1495230410 25200 # Node ID bec8ca52804cfae07b02f193aaa6e9b938d4d18e # Parent e23c712e1d9428e32241edb4255d1bfbcb1500d1 8177788: migrate collections technotes/guides into java/util/doc-files Reviewed-by: mchung, bchristi, martin diff -r e23c712e1d94 -r bec8ca52804c src/java.base/share/classes/java/util/doc-files/coll-designfaq.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/java.base/share/classes/java/util/doc-files/coll-designfaq.html Fri May 19 14:46:50 2017 -0700 @@ -0,0 +1,399 @@ + + + + + + + +Java Collections API Design FAQ + + +

Java Collections API Design FAQ

+ +
+This document answers frequently asked questions concerning the +design of the Java collections framework. It is derived from the +large volume of traffic on the collections-comments alias. It +serves as a design rationale for the collections framework. +

Core Interfaces - General Questions

+
    +
  1. Why don't you support immutability directly in +the core collection interfaces so that you can do away with +optional operations (and +UnsupportedOperationException)?
    2. +
  2. Won't programmers have to surround any code +that calls optional operations with a try-catch clause in case they +throw an UnsupportedOperationException?
    3. +
  3. Why isn't there a core interface for "bags" +(AKA multisets)?
    4. +
  4. Why didn't you use "Beans-style names" for +consistency?
    5. +
+

Collection Interface

+
    +
  1. Why doesn't Collection extend Cloneable and +Serializable?
    2. +
  2. Why don't you provide an "apply" method in +Collection to apply a given method ("upcall") to all the elements +of the Collection?
    3. +
  3. Why didn't you provide a "Predicate" interface, +and related methods (e.g., a method to find the first element in +the Collection satisfying the predicate)?
    4. +
  4. Why don't you provide a form of the addAll +method that takes an Enumeration (or an Iterator)?
    5. +
  5. Why don't the concrete implementations in the +JDK have Enumeration (or Iterator) constructors?
    6. +
  6. Why don't you provide an Iterator.add +method?
    7. +
+

List Interface

+
    +
  1. Why don't you rename the List interface to +Sequence; doesn't "list" generally suggest "linked list"? Also, +doesn't it conflict with java.awt.List?
    2. +
  2. Why don't you rename List's set method to +replace, to avoid confusion with Set.
    3. +
+

Map Interface

+
    +
  1. Why doesn't Map extend +Collection?
    2. +
+

Iterator Interface

+
    +
  1. Why doesn't Iterator extend +Enumeration?
    2. +
  2. Why don't you provide an Iterator.peek method +that allows you to look at the next element in an iteration without +advancing the iterator?
    3. +
+

Miscellaneous

+
    +
  1. Why did you write a new collections framework +instead of adopting JGL (a preexisting collections package from +ObjectSpace, Inc.) into the JDK?
    2. +
  2. Why don't you eliminate all of the methods and +classes that return "views" (Collections backed by other +collection-like objects). This would greatly reduce +aliasing.
    3. +
  3. Why don't you provide for "observable" +collections that send out Events when they're +modified?
    4. +
+
+

Core Interfaces - General Questions

+
    +
  1. Why don't you support immutability +directly in the core collection interfaces so that you can do away +with optional operations (and +UnsupportedOperationException)? +

    This is the most controversial design decision in the whole API. +Clearly, static (compile time) type checking is highly desirable, +and is the norm in Java. We would have supported it if we believed +it were feasible. Unfortunately, attempts to achieve this goal +cause an explosion in the size of the interface hierarchy, and do +not succeed in eliminating the need for runtime exceptions (though +they reduce it substantially).

    +

    Doug Lea, who wrote a popular Java collections package that did +reflect mutability distinctions in its interface hierarchy, no +longer believes it is a viable approach, based on user experience +with his collections package. In his words (from personal +correspondence) "Much as it pains me to say it, strong static +typing does not work for collection interfaces in Java."

    +

    To illustrate the problem in gory detail, suppose you want to +add the notion of modifiability to the Hierarchy. You need four new +interfaces: ModifiableCollection, ModifiableSet, ModifiableList, +and ModifiableMap. What was previously a simple hierarchy is now a +messy heterarchy. Also, you need a new Iterator interface for use +with unmodifiable Collections, that does not contain the remove +operation. Now can you do away with UnsupportedOperationException? +Unfortunately not.

    +

    Consider arrays. They implement most of the List operations, but +not remove and add. They are "fixed-size" Lists. If you want to +capture this notion in the hierarchy, you have to add two new +interfaces: VariableSizeList and VariableSizeMap. You don't have to +add VariableSizeCollection and VariableSizeSet, because they'd be +identical to ModifiableCollection and ModifiableSet, but you might +choose to add them anyway for consistency's sake. Also, you need a +new variety of ListIterator that doesn't support the add and remove +operations, to go along with unmodifiable List. Now we're up to ten +or twelve interfaces, plus two new Iterator interfaces, instead of +our original four. Are we done? No.

    +

    Consider logs (such as error logs, audit logs and journals for +recoverable data objects). They are natural append-only sequences, +that support all of the List operations except for remove and set +(replace). They require a new core interface, and a new +iterator.

    +

    And what about immutable Collections, as opposed to unmodifiable +ones? (i.e., Collections that cannot be changed by the client AND +will never change for any other reason). Many argue that this is +the most important distinction of all, because it allows multiple +threads to access a collection concurrently without the need for +synchronization. Adding this support to the type hierarchy requires +four more interfaces.

    +

    Now we're up to twenty or so interfaces and five iterators, and +it's almost certain that there are still collections arising in +practice that don't fit cleanly into any of the interfaces. For +example, the collection-views returned by Map are natural +delete-only collections. Also, there are collections that will +reject certain elements on the basis of their value, so we still +haven't done away with runtime exceptions.

    +

    When all was said and done, we felt that it was a sound +engineering compromise to sidestep the whole issue by providing a +very small set of core interfaces that can throw a runtime +exception.

    +
    2. +
  2. Won't programmers have to surround any +code that calls optional operations with a try-catch clause in case +they throw an UnsupportedOperationException? +

    It was never our intention that programs should catch these +exceptions: that's why they're unchecked (runtime) exceptions. They +should only arise as a result of programming errors, in which case, +your program will halt due to the uncaught exception.

    +
    3. +
  3. Why isn't there a core interface for +"bags" (AKA multisets)? +

    The Collection interface provides this functionality. We are not +providing any public implementations of this interface, as we think +that it wouldn't be used frequently enough to "pull its weight." We +occasionally return such Collections, which are implemented easily +atop AbstractCollection (for example, the Collection returned by +Map.values).

    +
    4. +
  4. Why didn't you use "Beans-style +names" for consistency? +

    While the names of the new collections methods do not adhere to +the "Beans naming conventions", we believe that they are +reasonable, consistent and appropriate to their purpose. It should +be remembered that the Beans naming conventions do not apply to the +JDK as a whole; the AWT did adopt these conventions, but that +decision was somewhat controversial. We suspect that the +collections APIs will be used quite pervasively, often with +multiple method calls on a single line of code, so it is important +that the names be short. Consider, for example, the Iterator +methods. Currently, a loop over a collection looks like this:

    +
    +    for (Iterator i = c.iterator(); i.hasNext(); )
+        System.out.println(i.next());
+
    +Everything fits neatly on one line, even if the Collection name is +a long expression. If we named the methods "getIterator", +"hasNextElement" and "getNextElement", this would no longer be the +case. Thus, we adopted the "traditional" JDK style rather than the +Beans style.
    5. +
+
+

Collection Interface

+
    +
  1. Why doesn't Collection extend Cloneable +and Serializable? +

    Many Collection implementations (including all of the ones +provided by the JDK) will have a public clone method, but it would +be mistake to require it of all Collections. For example, what does +it mean to clone a Collection that's backed by a terabyte SQL +database? Should the method call cause the company to requisition a +new disk farm? Similar arguments hold for serializable.

    +

    If the client doesn't know the actual type of a Collection, it's +much more flexible and less error prone to have the client decide +what type of Collection is desired, create an empty Collection of +this type, and use the addAll method to copy the elements of the +original collection into the new one.

    +
    2. +
  2. Why don't you provide an "apply" method +in Collection to apply a given method ("upcall") to all the +elements of the Collection? +

    This is what is referred to as an "Internal Iterator" in the +"Design Patterns" book (Gamma et al.). We considered providing it, +but decided not to as it seems somewhat redundant to support +internal and external iterators, and Java already has a precedent +for external iterators (with Enumerations). The "throw weight" of +this functionality is increased by the fact that it requires a +public interface to describe upcalls.

    +
    3. +
  3. Why didn't you provide a "Predicate" +interface, and related methods (e.g., a method to find the first +element in the Collection satisfying the predicate)? +

    It's easy to implement this functionality atop Iterators, and +the resulting code may actually look cleaner as the user can inline +the predicate. Thus, it's not clear whether this facility pulls its +weight. It could be added to the Collections class at a later date +(implemented atop Iterator), if it's deemed useful.

    +
    4. +
  4. Why don't you provide a form of the +addAll method that takes an Enumeration (or an Iterator)? +

    Because we don't believe in using Enumerations (or Iterators) as +"poor man's collections." This was occasionally done in prior +releases, but now that we have the Collection interface, it is the +preferred way to pass around abstract collections of objects.

    +
    5. +
  5. Why don't the concrete implementations +in the JDK have Enumeration (or Iterator) constructors? +

    Again, this is an instance of an Enumeration serving as a "poor +man's collection" and we're trying to discourage that. Note +however, that we strongly suggest that all concrete implementations +should have constructors that take a Collection (and create a new +Collection with the same elements).

    +
    6. +
  6. Why don't you provide an Iterator.add +method? +

    The semantics are unclear, given that the contract for Iterator +makes no guarantees about the order of iteration. Note, however, +that ListIterator does provide an add operation, as it does +guarantee the order of the iteration.

    +
    7. +
+
+

List Interface

+
    +
  1. Why don't you rename the List +interface to Sequence; doesn't "list" generally suggest "linked +list"? Also, doesn't it conflict with java.awt.List? +

    People were evenly divided as to whether List suggests linked +lists. Given the implementation naming convention, +<Implementation><Interface>, there +was a strong desire to keep the core interface names short. Also, +several existing names (AbstractSequentialList, LinkedList) would +have been decidedly worse if we changed List to Sequence. The +naming conflict can be dealt with by the following incantation:

    +
    +    import java.util.*;
+    import java.awt.*;
+    import java.util.List;   // Dictates interpretation of "List"
+
    2. +
  2. Why don't you rename List's set +method to replace, to avoid confusion with Set. +

    It was decided that the "set/get" naming convention was strongly +enough enshrined in the language that we'd stick with it.

    +
    3. +
+
+

Map Interface

+
    +
  1. Why doesn't Map extend +Collection? +

    This was by design. We feel that mappings are not collections +and collections are not mappings. Thus, it makes little sense for +Map to extend the Collection interface (or vice versa).

    +

    If a Map is a Collection, what are the elements? The only +reasonable answer is "Key-value pairs", but this provides a very +limited (and not particularly useful) Map abstraction. You can't +ask what value a given key maps to, nor can you delete the entry +for a given key without knowing what value it maps to.

    +

    Collection could be made to extend Map, but this raises the +question: what are the keys? There's no really satisfactory answer, +and forcing one leads to an unnatural interface.

    +

    Maps can be viewed as Collections (of keys, values, or +pairs), and this fact is reflected in the three "Collection view +operations" on Maps (keySet, entrySet, and values). While it is, in +principle, possible to view a List as a Map mapping indices to +elements, this has the nasty property that deleting an element from +the List changes the Key associated with every element before the +deleted element. That's why we don't have a map view operation on +Lists.

    +
    2. +
+
+

Iterator Interface

+
    +
  1. Why doesn't Iterator extend +Enumeration? +

    We view the method names for Enumeration as unfortunate. They're +very long, and very frequently used. Given that we were adding a +method and creating a whole new framework, we felt that it would be +foolish not to take advantage of the opportunity to improve the +names. Of course we could support the new and old names in +Iterator, but it doesn't seem worthwhile.

    +
    2. +
  2. Why don't you provide an +Iterator.peek method that allows you to look at the next element in +an iteration without advancing the iterator? +

    It can be implemented atop the current Iterators (a similar +pattern to java.io.PushbackInputStream). We believe that its use +would be rare enough that it isn't worth including in the interface +that everyone has to implement.

    +
    3. +
+
+

Miscellaneous

+
    +
  1. Why did you write a new collections +framework instead of adopting JGL (a preexisting collections +package from ObjectSpace, Inc.) into the JDK? +

    If you examine the goals for our Collections framework (in the +Overview), you'll see that we are not really "playing in the same +space" as JGL. Quoting from the "Design Goals" Section of the Java +Collections Overview: "Our main design goal was to produce an API +that was reasonably small, both in size, and (more importantly) in +'conceptual weight.'"

    +

    JGL consists of approximately 130 classes and interfaces; its +main goal was consistency with the C++ Standard Template Library +(STL). This was not one of our goals. Java has +traditionally stayed away from C++'s more complex features (e.g., +multiple inheritance, operator overloading). Our entire framework, +including all infrastructure, contains approximately 25 classes and +interfaces.

    +

    While this may cause some discomfort for some C++ programmers, +we feel that it will be good for Java in the long run. As the Java +libraries mature, they inevitably grow, but we are trying as hard +as we can to keep them small and manageable, so that Java continues +to be an easy, fun language to learn and to use.

    +
    2. +
  2. Why don't you eliminate all of the +methods and classes that return "views" (Collections backed by +other collection-like objects). This would greatly reduce +aliasing. +

    Given that we provide core collection interfaces behind which +programmers can "hide" their own implementations, there will be +aliased collections whether the JDK provides them or not. +Eliminating all views from the JDK would greatly increase the cost +of common operations like making a Collection out of an array, and +would do away with many useful facilities (like synchronizing +wrappers). One view that we see as being particularly useful is +List.subList. +The existence of this method means that people who write methods +taking List on input do not have to write secondary forms taking an +offset and a length (as they do for arrays).

    +
    3. +
  3. Why don't you provide for +"observable" collections that send out Events when they're +modified? +

    Primarily, resource constraints. If we're going to commit to +such an API, it has to be something that works for everyone, that +we can live with for the long haul. We may provide such a facility +some day. In the meantime, it's not difficult to implement such a +facility on top of the public APIs.

    +
    4. +
+
+

+Copyright © 1998, 2017, Oracle and/or its affiliates. 500 Oracle Parkway
+ Redwood Shores, CA 94065 USA. All rights reserved.

+ + + diff -r e23c712e1d94 -r bec8ca52804c src/java.base/share/classes/java/util/doc-files/coll-index.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/java.base/share/classes/java/util/doc-files/coll-index.html Fri May 19 14:46:50 2017 -0700 @@ -0,0 +1,80 @@ + + + + + + + + +The Collections Framework + + + + +

The Collections Framework

+ +

The collections framework is a unified architecture for +representing and manipulating collections, enabling them to be +manipulated independently of the details of their representation. +It reduces programming effort while increasing performance. It +enables interoperability among unrelated APIs, reduces effort in +designing and learning new APIs, and fosters software reuse. The +framework is based on more than a dozen collection interfaces. It +includes implementations of these interfaces and algorithms to +manipulate them.

+

The documents in this section are non-normative portions of +the Java™ Platform, Standard Edition API Specification.

+ + + +
+

+Copyright © 1998, 2017, Oracle and/or its affiliates. 500 Oracle Parkway
+ Redwood Shores, CA 94065 USA. All rights reserved.

+ + + diff -r e23c712e1d94 -r bec8ca52804c src/java.base/share/classes/java/util/doc-files/coll-overview.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/java.base/share/classes/java/util/doc-files/coll-overview.html Fri May 19 14:46:50 2017 -0700 @@ -0,0 +1,359 @@ + + + + + + + +Collections Framework Overview + + +

Collections Framework Overview

+ +

Introduction

+The Java platform includes a collections framework. A +collection is an object that represents a group of objects +(such as the classic ArrayList class). +A collections framework is a unified architecture for representing +and manipulating collections, enabling collections to be +manipulated independently of implementation details. +

The primary advantages of a collections framework are that +it:

+ +

The collections framework consists of:

+ +
+

Collection Interfaces

+

The collection interfaces are divided into two groups. +The most basic interface, java.util.Collection, +has the following descendants:

+ +

The other collection interfaces are based on java.util.Map and are +not true collections. However, these interfaces contain +collection-view operations, which enable them to be +manipulated as collections. Map has the following +offspring:

+ +

Many of the modification methods in the collection interfaces +are labeled optional. Implementations are permitted to not +perform one or more of these operations, throwing a runtime +exception (UnsupportedOperationException) 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:

+ +

Some implementations restrict what elements (or in the case of +Maps, keys and values) can be stored. Possible +restrictions include requiring elements to:

+ +

Attempting to add an element that violates an implementation's +restrictions results in a runtime exception, typically a +ClassCastException, an IllegalArgumentException, +or a NullPointerException. 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.

+
+

Collection Implementations

+

Classes that implement the collection interfaces typically have +names in the form of +<Implementation-style><Interface>. +The general purpose implementations are summarized in the following +table:

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
InterfaceHash TableResizable ArrayBalanced TreeLinked ListHash Table + Linked List
SetHashSet TreeSet LinkedHashSet
List ArrayList LinkedList 
Deque ArrayDeque LinkedList 
MapHashMap TreeMap LinkedHashMap
+

The general-purpose implementations support all of the +optional operations in the collection interfaces and have no +restrictions on the elements they may contain. They are +unsynchronized, but the Collections class contains static +factories called +synchronization wrappers that can be used to add +synchronization to many unsynchronized collections. All of the new +implementations have fail-fast iterators, which detect +invalid concurrent modification, and fail quickly and cleanly +(rather than behaving erratically).

+

The AbstractCollection, AbstractSet, +AbstractList, AbstractSequentialList and +AbstractMap 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.

+
+

Concurrent Collections

+

Applications that use collections from more than one thread must +be carefully programmed. In general, this is known as concurrent +programming. The Java platform includes extensive support for +concurrent programming. See Java Concurrency +Utilities for details.

+

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.

+

These concurrent-aware interfaces are available:

+ +

The following concurrent-aware implementation classes are +available. See the API documentation for the correct usage of these +implementations.

+ +
+

Design Goals

+

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.

+

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 optional, enabling implementations to throw +an UnsupportedOperationException to indicate that they do +not support a specified optional operation. Collection implementers +must clearly document which optional operations are supported by an +implementation.

+

To keep the number of methods in each core interface small, an +interface contains a method only if either:

+ +

It was critical that all reasonable representations of +collections interoperate well. This included arrays, which cannot +be made to implement the Collection 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.

+
+

+Copyright © 1998, 2017, Oracle and/or its affiliates. 500 Oracle Parkway
+ Redwood Shores, CA 94065 USA. All rights reserved.

+ + + diff -r e23c712e1d94 -r bec8ca52804c src/java.base/share/classes/java/util/doc-files/coll-reference.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/java.base/share/classes/java/util/doc-files/coll-reference.html Fri May 19 14:46:50 2017 -0700 @@ -0,0 +1,564 @@ + + + + + + + +Outline of the Collections Framework + + +

Outline of the Collections Framework

+ +The collections framework consists of: + +
+

+Copyright © 1998, 2017, Oracle and/or its affiliates. 500 Oracle Parkway
+ Redwood Shores, CA 94065 USA. All rights reserved.

+ + + diff -r e23c712e1d94 -r bec8ca52804c src/java.base/share/classes/java/util/package-info.java --- a/src/java.base/share/classes/java/util/package-info.java Fri Jun 16 22:10:20 2017 +0000 +++ b/src/java.base/share/classes/java/util/package-info.java Fri May 19 14:46:50 2017 -0700 @@ -24,27 +24,24 @@ */ /** - * Contains the collections framework, legacy collection classes, - * event model, date and time facilities, internationalization, and - * miscellaneous utility classes (a string tokenizer, a random-number - * generator, and a bit array). + * Contains the collections framework, some internationalization support classes, + * a service loader, properties, random number generation, string parsing + * and scanning classes, base64 encoding and decoding, a bit array, and + * several miscellaneous utility classes. This package also contains + * legacy collection classes and legacy date and time classes. * *

{@index "Java Collections Framework"}

+ *

For an overview, API outline, and design rationale, please see: *

* - *

Related Documentation

- * For overviews, tutorials, examples, guides, and tool documentation, - * please see: + *

For a tutorial and programming guide with examples of use + * of the collections framework, please see: *

* * @since 1.0