KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > LinkedHashSet


1 /*
2  * @(#)LinkedHashSet.java 1.14 04/02/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package java.util;
9
10 /**
11  * <p>Hash table and linked list implementation of the <tt>Set</tt> interface,
12  * with predictable iteration order. This implementation differs from
13  * <tt>HashSet</tt> in that it maintains a doubly-linked list running through
14  * all of its entries. This linked list defines the iteration ordering,
15  * which is the order in which elements were inserted into the set
16  * (<i>insertion-order</i>). Note that insertion order is <i>not</i> affected
17  * if an element is <i>re-inserted</i> into the set. (An element <tt>e</tt>
18  * is reinserted into a set <tt>s</tt> if <tt>s.add(e)</tt> is invoked when
19  * <tt>s.contains(e)</tt> would return <tt>true</tt> immediately prior to
20  * the invocation.)
21  *
22  * <p>This implementation spares its clients from the unspecified, generally
23  * chaotic ordering provided by {@link HashSet}, without incurring the
24  * increased cost associated with {@link TreeSet}. It can be used to
25  * produce a copy of a set that has the same order as the original, regardless
26  * of the original set's implementation:
27  * <pre>
28  * void foo(Set m) {
29  * Set copy = new LinkedHashSet(m);
30  * ...
31  * }
32  * </pre>
33  * This technique is particularly useful if a module takes a set on input,
34  * copies it, and later returns results whose order is determined by that of
35  * the copy. (Clients generally appreciate having things returned in the same
36  * order they were presented.)
37  *
38  * <p>This class provides all of the optional <tt>Set</tt> operations, and
39  * permits null elements. Like <tt>HashSet</tt>, it provides constant-time
40  * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and
41  * <tt>remove</tt>), assuming the hash function disperses elements
42  * properly among the buckets. Performance is likely to be just slightly
43  * below that of <tt>HashSet</tt>, due to the added expense of maintaining the
44  * linked list, with one exception: Iteration over a <tt>LinkedHashSet</tt>
45  * requires time proportional to the <i>size</i> of the set, regardless of
46  * its capacity. Iteration over a <tt>HashSet</tt> is likely to be more
47  * expensive, requiring time proportional to its <i>capacity</i>.
48  *
49  * <p>A linked hash set has two parameters that affect its performance:
50  * <i>initial capacity</i> and <i>load factor</i>. They are defined precisely
51  * as for <tt>HashSet</tt>. Note, however, that the penalty for choosing an
52  * excessively high value for initial capacity is less severe for this class
53  * than for <tt>HashSet</tt>, as iteration times for this class are unaffected
54  * by capacity.
55  *
56  * <p><strong>Note that this implementation is not synchronized.</strong> If
57  * multiple threads access a linked hash set concurrently, and at least one of
58  * the threads modifies the set, it <em>must</em> be synchronized externally.
59  * This is typically accomplished by synchronizing on some object that
60  * naturally encapsulates the set. If no such object exists, the set should
61  * be "wrapped" using the <tt>Collections.synchronizedSet</tt>method. This is
62  * best done at creation time, to prevent accidental unsynchronized access:
63  * <pre>
64  * Set s = Collections.synchronizedSet(new LinkedHashSet(...));
65  * </pre>
66  *
67  * <p>The iterators returned by the this class's <tt>iterator</tt> method are
68  * <em>fail-fast</em>: if the set is modified at any time after the iterator
69  * is created, in any way except through the iterator's own remove method, the
70  * iterator will throw a <tt>ConcurrentModificationException</tt>. Thus, in
71  * the face of concurrent modification, the Iterator fails quickly and
72  * cleanly, rather than risking arbitrary, non-deterministic behavior at an
73  * undetermined time in the future.
74  *
75  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
76  * as it is, generally speaking, impossible to make any hard guarantees in the
77  * presence of unsynchronized concurrent modification. Fail-fast iterators
78  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
79  * Therefore, it would be wrong to write a program that depended on this
80  * exception for its correctness: <i>the fail-fast behavior of iterators
81  * should be used only to detect bugs.</i>
82  *
83  * <p>This class is a member of the
84  * <a HREF="{@docRoot}/../guide/collections/index.html">
85  * Java Collections Framework</a>.
86  *
87  * @author Josh Bloch
88  * @version 1.14 04/02/19
89  * @see Object#hashCode()
90  * @see Collection
91  * @see Set
92  * @see HashSet
93  * @see TreeSet
94  * @see Hashtable
95  * @since 1.4
96  */
97
98 public class LinkedHashSet<E>
99     extends HashSet JavaDoc<E>
100     implements Set JavaDoc<E>, Cloneable JavaDoc, java.io.Serializable JavaDoc {
101
102     private static final long serialVersionUID = -2851667679971038690L;
103
104     /**
105      * Constructs a new, empty linked hash set with the specified initial
106      * capacity and load factor.
107      *
108      * @param initialCapacity the initial capacity of the linked hash set
109      * @param loadFactor the load factor of the linked hash set.
110      * @throws IllegalArgumentException if the initial capacity is less
111      * than zero, or if the load factor is nonpositive.
112      */
113     public LinkedHashSet(int initialCapacity, float loadFactor) {
114         super(initialCapacity, loadFactor, true);
115     }
116
117     /**
118      * Constructs a new, empty linked hash set with the specified initial
119      * capacity and the default load factor (0.75).
120      *
121      * @param initialCapacity the initial capacity of the LinkedHashSet.
122      * @throws IllegalArgumentException if the initial capacity is less
123      * than zero.
124      */
125     public LinkedHashSet(int initialCapacity) {
126         super(initialCapacity, .75f, true);
127     }
128
129     /**
130      * Constructs a new, empty linked hash set with the default initial
131      * capacity (16) and load factor (0.75).
132      */
133     public LinkedHashSet() {
134         super(16, .75f, true);
135     }
136
137     /**
138      * Constructs a new linked hash set with the same elements as the
139      * specified collection. The linked hash set is created with an initial
140      * capacity sufficient to hold the elements in the specified collection
141      * and the default load factor (0.75).
142      *
143      * @param c the collection whose elements are to be placed into
144      * this set.
145      * @throws NullPointerException if the specified collection is null.
146      */
147     public LinkedHashSet(Collection JavaDoc<? extends E> c) {
148         super(Math.max(2*c.size(), 11), .75f, true);
149         addAll(c);
150     }
151 }
152
Popular Tags