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 }