jdk/src/java.base/share/classes/java/util/LinkedHashSet.java
author mchung
Fri, 22 May 2015 16:43:39 -0700
changeset 30789 9eca83469588
parent 25859 3317bb8137f4
child 32108 aa5490a167ee
permissions -rw-r--r--
8074431: Remove native2ascii tool Reviewed-by: erikj, alanb, okutsu, mfang, naoto
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     1
/*
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
     2
 * Copyright (c) 2000, 2013, Oracle and/or its affiliates. All rights reserved.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     3
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
90ce3da70b43 Initial load
duke
parents:
diff changeset
     4
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
     5
 * This code is free software; you can redistribute it and/or modify it
90ce3da70b43 Initial load
duke
parents:
diff changeset
     6
 * under the terms of the GNU General Public License version 2 only, as
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     7
 * published by the Free Software Foundation.  Oracle designates this
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
     8
 * particular file as subject to the "Classpath" exception as provided
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
     9
 * by Oracle in the LICENSE file that accompanied this code.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    10
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    11
 * This code is distributed in the hope that it will be useful, but WITHOUT
90ce3da70b43 Initial load
duke
parents:
diff changeset
    12
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
90ce3da70b43 Initial load
duke
parents:
diff changeset
    13
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
90ce3da70b43 Initial load
duke
parents:
diff changeset
    14
 * version 2 for more details (a copy is included in the LICENSE file that
90ce3da70b43 Initial load
duke
parents:
diff changeset
    15
 * accompanied this code).
90ce3da70b43 Initial load
duke
parents:
diff changeset
    16
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    17
 * You should have received a copy of the GNU General Public License version
90ce3da70b43 Initial load
duke
parents:
diff changeset
    18
 * 2 along with this work; if not, write to the Free Software Foundation,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    19
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    20
 *
5506
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    21
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    22
 * or visit www.oracle.com if you need additional information or have any
202f599c92aa 6943119: Rebrand source copyright notices
ohair
parents: 2
diff changeset
    23
 * questions.
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
    24
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
    25
90ce3da70b43 Initial load
duke
parents:
diff changeset
    26
package java.util;
90ce3da70b43 Initial load
duke
parents:
diff changeset
    27
90ce3da70b43 Initial load
duke
parents:
diff changeset
    28
/**
90ce3da70b43 Initial load
duke
parents:
diff changeset
    29
 * <p>Hash table and linked list implementation of the <tt>Set</tt> interface,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    30
 * with predictable iteration order.  This implementation differs from
90ce3da70b43 Initial load
duke
parents:
diff changeset
    31
 * <tt>HashSet</tt> in that it maintains a doubly-linked list running through
90ce3da70b43 Initial load
duke
parents:
diff changeset
    32
 * all of its entries.  This linked list defines the iteration ordering,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    33
 * which is the order in which elements were inserted into the set
90ce3da70b43 Initial load
duke
parents:
diff changeset
    34
 * (<i>insertion-order</i>).  Note that insertion order is <i>not</i> affected
90ce3da70b43 Initial load
duke
parents:
diff changeset
    35
 * if an element is <i>re-inserted</i> into the set.  (An element <tt>e</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    36
 * is reinserted into a set <tt>s</tt> if <tt>s.add(e)</tt> is invoked when
90ce3da70b43 Initial load
duke
parents:
diff changeset
    37
 * <tt>s.contains(e)</tt> would return <tt>true</tt> immediately prior to
90ce3da70b43 Initial load
duke
parents:
diff changeset
    38
 * the invocation.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
    39
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    40
 * <p>This implementation spares its clients from the unspecified, generally
90ce3da70b43 Initial load
duke
parents:
diff changeset
    41
 * chaotic ordering provided by {@link HashSet}, without incurring the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    42
 * increased cost associated with {@link TreeSet}.  It can be used to
90ce3da70b43 Initial load
duke
parents:
diff changeset
    43
 * produce a copy of a set that has the same order as the original, regardless
90ce3da70b43 Initial load
duke
parents:
diff changeset
    44
 * of the original set's implementation:
90ce3da70b43 Initial load
duke
parents:
diff changeset
    45
 * <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    46
 *     void foo(Set s) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
    47
 *         Set copy = new LinkedHashSet(s);
90ce3da70b43 Initial load
duke
parents:
diff changeset
    48
 *         ...
90ce3da70b43 Initial load
duke
parents:
diff changeset
    49
 *     }
90ce3da70b43 Initial load
duke
parents:
diff changeset
    50
 * </pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    51
 * This technique is particularly useful if a module takes a set on input,
90ce3da70b43 Initial load
duke
parents:
diff changeset
    52
 * copies it, and later returns results whose order is determined by that of
90ce3da70b43 Initial load
duke
parents:
diff changeset
    53
 * the copy.  (Clients generally appreciate having things returned in the same
90ce3da70b43 Initial load
duke
parents:
diff changeset
    54
 * order they were presented.)
90ce3da70b43 Initial load
duke
parents:
diff changeset
    55
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    56
 * <p>This class provides all of the optional <tt>Set</tt> operations, and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    57
 * permits null elements.  Like <tt>HashSet</tt>, it provides constant-time
90ce3da70b43 Initial load
duke
parents:
diff changeset
    58
 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
90ce3da70b43 Initial load
duke
parents:
diff changeset
    59
 * <tt>remove</tt>), assuming the hash function disperses elements
90ce3da70b43 Initial load
duke
parents:
diff changeset
    60
 * properly among the buckets.  Performance is likely to be just slightly
90ce3da70b43 Initial load
duke
parents:
diff changeset
    61
 * below that of <tt>HashSet</tt>, due to the added expense of maintaining the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    62
 * linked list, with one exception: Iteration over a <tt>LinkedHashSet</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    63
 * requires time proportional to the <i>size</i> of the set, regardless of
90ce3da70b43 Initial load
duke
parents:
diff changeset
    64
 * its capacity.  Iteration over a <tt>HashSet</tt> is likely to be more
90ce3da70b43 Initial load
duke
parents:
diff changeset
    65
 * expensive, requiring time proportional to its <i>capacity</i>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    66
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    67
 * <p>A linked hash set has two parameters that affect its performance:
90ce3da70b43 Initial load
duke
parents:
diff changeset
    68
 * <i>initial capacity</i> and <i>load factor</i>.  They are defined precisely
90ce3da70b43 Initial load
duke
parents:
diff changeset
    69
 * as for <tt>HashSet</tt>.  Note, however, that the penalty for choosing an
90ce3da70b43 Initial load
duke
parents:
diff changeset
    70
 * excessively high value for initial capacity is less severe for this class
90ce3da70b43 Initial load
duke
parents:
diff changeset
    71
 * than for <tt>HashSet</tt>, as iteration times for this class are unaffected
90ce3da70b43 Initial load
duke
parents:
diff changeset
    72
 * by capacity.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    73
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    74
 * <p><strong>Note that this implementation is not synchronized.</strong>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    75
 * If multiple threads access a linked hash set concurrently, and at least
90ce3da70b43 Initial load
duke
parents:
diff changeset
    76
 * one of the threads modifies the set, it <em>must</em> be synchronized
90ce3da70b43 Initial load
duke
parents:
diff changeset
    77
 * externally.  This is typically accomplished by synchronizing on some
90ce3da70b43 Initial load
duke
parents:
diff changeset
    78
 * object that naturally encapsulates the set.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    79
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    80
 * If no such object exists, the set should be "wrapped" using the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    81
 * {@link Collections#synchronizedSet Collections.synchronizedSet}
90ce3da70b43 Initial load
duke
parents:
diff changeset
    82
 * method.  This is best done at creation time, to prevent accidental
90ce3da70b43 Initial load
duke
parents:
diff changeset
    83
 * unsynchronized access to the set: <pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    84
 *   Set s = Collections.synchronizedSet(new LinkedHashSet(...));</pre>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    85
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    86
 * <p>The iterators returned by this class's <tt>iterator</tt> method are
90ce3da70b43 Initial load
duke
parents:
diff changeset
    87
 * <em>fail-fast</em>: if the set is modified at any time after the iterator
90ce3da70b43 Initial load
duke
parents:
diff changeset
    88
 * is created, in any way except through the iterator's own <tt>remove</tt>
90ce3da70b43 Initial load
duke
parents:
diff changeset
    89
 * method, the iterator will throw a {@link ConcurrentModificationException}.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    90
 * Thus, in the face of concurrent modification, the iterator fails quickly
90ce3da70b43 Initial load
duke
parents:
diff changeset
    91
 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
90ce3da70b43 Initial load
duke
parents:
diff changeset
    92
 * an undetermined time in the future.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    93
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
    94
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
90ce3da70b43 Initial load
duke
parents:
diff changeset
    95
 * as it is, generally speaking, impossible to make any hard guarantees in the
90ce3da70b43 Initial load
duke
parents:
diff changeset
    96
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
    97
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
90ce3da70b43 Initial load
duke
parents:
diff changeset
    98
 * Therefore, it would be wrong to write a program that depended on this
90ce3da70b43 Initial load
duke
parents:
diff changeset
    99
 * exception for its correctness:   <i>the fail-fast behavior of iterators
90ce3da70b43 Initial load
duke
parents:
diff changeset
   100
 * should be used only to detect bugs.</i>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   101
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   102
 * <p>This class is a member of the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   103
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
90ce3da70b43 Initial load
duke
parents:
diff changeset
   104
 * Java Collections Framework</a>.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   105
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   106
 * @param <E> the type of elements maintained by this set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   107
 *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   108
 * @author  Josh Bloch
90ce3da70b43 Initial load
duke
parents:
diff changeset
   109
 * @see     Object#hashCode()
90ce3da70b43 Initial load
duke
parents:
diff changeset
   110
 * @see     Collection
90ce3da70b43 Initial load
duke
parents:
diff changeset
   111
 * @see     Set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   112
 * @see     HashSet
90ce3da70b43 Initial load
duke
parents:
diff changeset
   113
 * @see     TreeSet
90ce3da70b43 Initial load
duke
parents:
diff changeset
   114
 * @see     Hashtable
90ce3da70b43 Initial load
duke
parents:
diff changeset
   115
 * @since   1.4
90ce3da70b43 Initial load
duke
parents:
diff changeset
   116
 */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   117
90ce3da70b43 Initial load
duke
parents:
diff changeset
   118
public class LinkedHashSet<E>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   119
    extends HashSet<E>
90ce3da70b43 Initial load
duke
parents:
diff changeset
   120
    implements Set<E>, Cloneable, java.io.Serializable {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   121
90ce3da70b43 Initial load
duke
parents:
diff changeset
   122
    private static final long serialVersionUID = -2851667679971038690L;
90ce3da70b43 Initial load
duke
parents:
diff changeset
   123
90ce3da70b43 Initial load
duke
parents:
diff changeset
   124
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   125
     * Constructs a new, empty linked hash set with the specified initial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   126
     * capacity and load factor.
90ce3da70b43 Initial load
duke
parents:
diff changeset
   127
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   128
     * @param      initialCapacity the initial capacity of the linked hash set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   129
     * @param      loadFactor      the load factor of the linked hash set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   130
     * @throws     IllegalArgumentException  if the initial capacity is less
90ce3da70b43 Initial load
duke
parents:
diff changeset
   131
     *               than zero, or if the load factor is nonpositive
90ce3da70b43 Initial load
duke
parents:
diff changeset
   132
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   133
    public LinkedHashSet(int initialCapacity, float loadFactor) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   134
        super(initialCapacity, loadFactor, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   135
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   136
90ce3da70b43 Initial load
duke
parents:
diff changeset
   137
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   138
     * Constructs a new, empty linked hash set with the specified initial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   139
     * capacity and the default load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   140
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   141
     * @param   initialCapacity   the initial capacity of the LinkedHashSet
90ce3da70b43 Initial load
duke
parents:
diff changeset
   142
     * @throws  IllegalArgumentException if the initial capacity is less
90ce3da70b43 Initial load
duke
parents:
diff changeset
   143
     *              than zero
90ce3da70b43 Initial load
duke
parents:
diff changeset
   144
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   145
    public LinkedHashSet(int initialCapacity) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   146
        super(initialCapacity, .75f, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   147
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   148
90ce3da70b43 Initial load
duke
parents:
diff changeset
   149
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   150
     * Constructs a new, empty linked hash set with the default initial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   151
     * capacity (16) and load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   152
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   153
    public LinkedHashSet() {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   154
        super(16, .75f, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   155
    }
90ce3da70b43 Initial load
duke
parents:
diff changeset
   156
90ce3da70b43 Initial load
duke
parents:
diff changeset
   157
    /**
90ce3da70b43 Initial load
duke
parents:
diff changeset
   158
     * Constructs a new linked hash set with the same elements as the
90ce3da70b43 Initial load
duke
parents:
diff changeset
   159
     * specified collection.  The linked hash set is created with an initial
90ce3da70b43 Initial load
duke
parents:
diff changeset
   160
     * capacity sufficient to hold the elements in the specified collection
90ce3da70b43 Initial load
duke
parents:
diff changeset
   161
     * and the default load factor (0.75).
90ce3da70b43 Initial load
duke
parents:
diff changeset
   162
     *
90ce3da70b43 Initial load
duke
parents:
diff changeset
   163
     * @param c  the collection whose elements are to be placed into
90ce3da70b43 Initial load
duke
parents:
diff changeset
   164
     *           this set
90ce3da70b43 Initial load
duke
parents:
diff changeset
   165
     * @throws NullPointerException if the specified collection is null
90ce3da70b43 Initial load
duke
parents:
diff changeset
   166
     */
90ce3da70b43 Initial load
duke
parents:
diff changeset
   167
    public LinkedHashSet(Collection<? extends E> c) {
90ce3da70b43 Initial load
duke
parents:
diff changeset
   168
        super(Math.max(2*c.size(), 11), .75f, true);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   169
        addAll(c);
90ce3da70b43 Initial load
duke
parents:
diff changeset
   170
    }
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   171
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   172
    /**
19435
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   173
     * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   174
     * and <em>fail-fast</em> {@code Spliterator} over the elements in this set.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   175
     *
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   176
     * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   177
     * {@link Spliterator#DISTINCT}, and {@code ORDERED}.  Implementations
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   178
     * should document the reporting of additional characteristic values.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   179
     *
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   180
     * @implNote
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   181
     * The implementation creates a
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   182
     * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   183
     * from the set's {@code Iterator}.  The spliterator inherits the
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   184
     * <em>fail-fast</em> properties of the set's iterator.
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   185
     * The created {@code Spliterator} additionally reports
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   186
     * {@link Spliterator#SUBSIZED}.
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   187
     *
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   188
     * @return a {@code Spliterator} over the elements in this set
19435
9d7530ff42cb 8014824: Document Spliterator characteristics and binding policy of java util collection impls
psandoz
parents: 17168
diff changeset
   189
     * @since 1.8
17168
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   190
     */
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   191
    @Override
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   192
    public Spliterator<E> spliterator() {
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   193
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
b7d3500f2516 8011426: java.util collection Spliterator implementations
psandoz
parents: 5506
diff changeset
   194
    }
2
90ce3da70b43 Initial load
duke
parents:
diff changeset
   195
}