1 /*

     2  * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package java.util;

    27 

    28 /**

    29  * <p>Hash table and linked list implementation of the {@code Set} interface,

    30  * with predictable iteration order.  This implementation differs from

    31  * {@code HashSet} in that it maintains a doubly-linked list running through

    32  * all of its entries.  This linked list defines the iteration ordering,

    33  * which is the order in which elements were inserted into the set

    34  * (<i>insertion-order</i>).  Note that insertion order is <i>not</i> affected

    35  * if an element is <i>re-inserted</i> into the set.  (An element {@code e}

    36  * is reinserted into a set {@code s} if {@code s.add(e)} is invoked when

    37  * {@code s.contains(e)} would return {@code true} immediately prior to

    38  * the invocation.)

    39  *

    40  * <p>This implementation spares its clients from the unspecified, generally

    41  * chaotic ordering provided by {@link HashSet}, without incurring the

    42  * increased cost associated with {@link TreeSet}.  It can be used to

    43  * produce a copy of a set that has the same order as the original, regardless

    44  * of the original set's implementation:

    45  * <pre>

    46  *     void foo(Set s) {

    47  *         Set copy = new LinkedHashSet(s);

    48  *         ...

    49  *     }

    50  * </pre>

    51  * This technique is particularly useful if a module takes a set on input,

    52  * copies it, and later returns results whose order is determined by that of

    53  * the copy.  (Clients generally appreciate having things returned in the same

    54  * order they were presented.)

    55  *

    56  * <p>This class provides all of the optional {@code Set} operations, and

    57  * permits null elements.  Like {@code HashSet}, it provides constant-time

    58  * performance for the basic operations ({@code add}, {@code contains} and

    59  * {@code remove}), assuming the hash function disperses elements

    60  * properly among the buckets.  Performance is likely to be just slightly

    61  * below that of {@code HashSet}, due to the added expense of maintaining the

    62  * linked list, with one exception: Iteration over a {@code LinkedHashSet}

    63  * requires time proportional to the <i>size</i> of the set, regardless of

    64  * its capacity.  Iteration over a {@code HashSet} is likely to be more

    65  * expensive, requiring time proportional to its <i>capacity</i>.

    66  *

    67  * <p>A linked hash set has two parameters that affect its performance:

    68  * <i>initial capacity</i> and <i>load factor</i>.  They are defined precisely

    69  * as for {@code HashSet}.  Note, however, that the penalty for choosing an

    70  * excessively high value for initial capacity is less severe for this class

    71  * than for {@code HashSet}, as iteration times for this class are unaffected

    72  * by capacity.

    73  *

    74  * <p><strong>Note that this implementation is not synchronized.</strong>

    75  * If multiple threads access a linked hash set concurrently, and at least

    76  * one of the threads modifies the set, it <em>must</em> be synchronized

    77  * externally.  This is typically accomplished by synchronizing on some

    78  * object that naturally encapsulates the set.

    79  *

    80  * If no such object exists, the set should be "wrapped" using the

    81  * {@link Collections#synchronizedSet Collections.synchronizedSet}

    82  * method.  This is best done at creation time, to prevent accidental

    83  * unsynchronized access to the set: <pre>

    84  *   Set s = Collections.synchronizedSet(new LinkedHashSet(...));</pre>

    85  *

    86  * <p>The iterators returned by this class's {@code iterator} method are

    87  * <em>fail-fast</em>: if the set is modified at any time after the iterator

    88  * is created, in any way except through the iterator's own {@code remove}

    89  * method, the iterator will throw a {@link ConcurrentModificationException}.

    90  * Thus, in the face of concurrent modification, the iterator fails quickly

    91  * and cleanly, rather than risking arbitrary, non-deterministic behavior at

    92  * an undetermined time in the future.

    93  *

    94  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

    95  * as it is, generally speaking, impossible to make any hard guarantees in the

    96  * presence of unsynchronized concurrent modification.  Fail-fast iterators

    97  * throw {@code ConcurrentModificationException} on a best-effort basis.

    98  * Therefore, it would be wrong to write a program that depended on this

    99  * exception for its correctness:   <i>the fail-fast behavior of iterators

   100  * should be used only to detect bugs.</i>

   101  *

   102  * <p>This class is a member of the

   103  * <a href="{@docRoot}/java/util/package-summary.html#CollectionsFramework">

   104  * Java Collections Framework</a>.

   105  *

   106  * @param <E> the type of elements maintained by this set

   107  *

   108  * @author  Josh Bloch

   109  * @see     Object#hashCode()

   110  * @see     Collection

   111  * @see     Set

   112  * @see     HashSet

   113  * @see     TreeSet

   114  * @see     Hashtable

   115  * @since   1.4

   116  */

   117 

   118 public class LinkedHashSet<E>

   119     extends HashSet<E>

   120     implements Set<E>, Cloneable, java.io.Serializable {

   121 

   122     private static final long serialVersionUID = -2851667679971038690L;

   123 

   124     /**

   125      * Constructs a new, empty linked hash set with the specified initial

   126      * capacity and load factor.

   127      *

   128      * @param      initialCapacity the initial capacity of the linked hash set

   129      * @param      loadFactor      the load factor of the linked hash set

   130      * @throws     IllegalArgumentException  if the initial capacity is less

   131      *               than zero, or if the load factor is nonpositive

   132      */

   133     public LinkedHashSet(int initialCapacity, float loadFactor) {

   134         super(initialCapacity, loadFactor, true);

   135     }

   136 

   137     /**

   138      * Constructs a new, empty linked hash set with the specified initial

   139      * capacity and the default load factor (0.75).

   140      *

   141      * @param   initialCapacity   the initial capacity of the LinkedHashSet

   142      * @throws  IllegalArgumentException if the initial capacity is less

   143      *              than zero

   144      */

   145     public LinkedHashSet(int initialCapacity) {

   146         super(initialCapacity, .75f, true);

   147     }

   148 

   149     /**

   150      * Constructs a new, empty linked hash set with the default initial

   151      * capacity (16) and load factor (0.75).

   152      */

   153     public LinkedHashSet() {

   154         super(16, .75f, true);

   155     }

   156 

   157     /**

   158      * Constructs a new linked hash set with the same elements as the

   159      * specified collection.  The linked hash set is created with an initial

   160      * capacity sufficient to hold the elements in the specified collection

   161      * and the default load factor (0.75).

   162      *

   163      * @param c  the collection whose elements are to be placed into

   164      *           this set

   165      * @throws NullPointerException if the specified collection is null

   166      */

   167     public LinkedHashSet(Collection<? extends E> c) {

   168         super(Math.max(2*c.size(), 11), .75f, true);

   169         addAll(c);

   170     }

   171 

   172     /**

   173      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>

   174      * and <em>fail-fast</em> {@code Spliterator} over the elements in this set.

   175      *

   176      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},

   177      * {@link Spliterator#DISTINCT}, and {@code ORDERED}.  Implementations

   178      * should document the reporting of additional characteristic values.

   179      *

   180      * @implNote

   181      * The implementation creates a

   182      * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator

   183      * from the set's {@code Iterator}.  The spliterator inherits the

   184      * <em>fail-fast</em> properties of the set's iterator.

   185      * The created {@code Spliterator} additionally reports

   186      * {@link Spliterator#SUBSIZED}.

   187      *

   188      * @return a {@code Spliterator} over the elements in this set

   189      * @since 1.8

   190      */

   191     @Override

   192     public Spliterator<E> spliterator() {

   193         return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);

   194     }

   195 }