Source for java.util.LinkedHashSet

   1: /* LinkedHashSet.java -- a set backed by a LinkedHashMap, for linked
   2:    list traversal.
   3:    Copyright (C) 2001, 2004, 2005 Free Software Foundation, Inc.
   4: 
   5: This file is part of GNU Classpath.
   6: 
   7: GNU Classpath is free software; you can redistribute it and/or modify
   8: it under the terms of the GNU General Public License as published by
   9: the Free Software Foundation; either version 2, or (at your option)
  10: any later version.
  11: 
  12: GNU Classpath is distributed in the hope that it will be useful, but
  13: WITHOUT ANY WARRANTY; without even the implied warranty of
  14: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15: General Public License for more details.
  16: 
  17: You should have received a copy of the GNU General Public License
  18: along with GNU Classpath; see the file COPYING.  If not, write to the
  19: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  20: 02110-1301 USA.
  21: 
  22: Linking this library statically or dynamically with other modules is
  23: making a combined work based on this library.  Thus, the terms and
  24: conditions of the GNU General Public License cover the whole
  25: combination.
  26: 
  27: As a special exception, the copyright holders of this library give you
  28: permission to link this library with independent modules to produce an
  29: executable, regardless of the license terms of these independent
  30: modules, and to copy and distribute the resulting executable under
  31: terms of your choice, provided that you also meet, for each linked
  32: independent module, the terms and conditions of the license of that
  33: module.  An independent module is a module which is not derived from
  34: or based on this library.  If you modify this library, you may extend
  35: this exception to your version of the library, but you are not
  36: obligated to do so.  If you do not wish to do so, delete this
  37: exception statement from your version. */
  38: 
  39: 
  40: package java.util;
  41: 
  42: import java.io.Serializable;
  43: 
  44: /**
  45:  * This class provides a hashtable-backed implementation of the
  46:  * Set interface, with predictable traversal order.
  47:  * <p>
  48:  *
  49:  * It uses a hash-bucket approach; that is, hash collisions are handled
  50:  * by linking the new node off of the pre-existing node (or list of
  51:  * nodes).  In this manner, techniques such as linear probing (which
  52:  * can cause primary clustering) and rehashing (which does not fit very
  53:  * well with Java's method of precomputing hash codes) are avoided.  In
  54:  * addition, this maintains a doubly-linked list which tracks insertion
  55:  * order.  Note that the insertion order is not modified if an
  56:  * <code>add</code> simply reinserts an element in the set.
  57:  * <p>
  58:  *
  59:  * One of the nice features of tracking insertion order is that you can
  60:  * copy a set, and regardless of the implementation of the original,
  61:  * produce the same results when iterating over the copy.  This is possible
  62:  * without needing the overhead of <code>TreeSet</code>.
  63:  * <p>
  64:  *
  65:  * Under ideal circumstances (no collisions), LinkedHashSet offers O(1) 
  66:  * performance on most operations.  In the worst case (all elements map
  67:  * to the same hash code -- very unlikely), most operations are O(n).
  68:  * <p>
  69:  *
  70:  * LinkedHashSet accepts the null entry.  It is not synchronized, so if
  71:  * you need multi-threaded access, consider using:<br>
  72:  * <code>Set s = Collections.synchronizedSet(new LinkedHashSet(...));</code>
  73:  * <p>
  74:  *
  75:  * The iterators are <i>fail-fast</i>, meaning that any structural
  76:  * modification, except for <code>remove()</code> called on the iterator
  77:  * itself, cause the iterator to throw a
  78:  * {@link ConcurrentModificationException} rather than exhibit
  79:  * non-deterministic behavior.
  80:  *
  81:  * @author Eric Blake (ebb9@email.byu.edu)
  82:  * @see Object#hashCode()
  83:  * @see Collection
  84:  * @see Set
  85:  * @see HashSet
  86:  * @see TreeSet
  87:  * @see Collections#synchronizedSet(Set)
  88:  * @since 1.4
  89:  * @status updated to 1.4
  90:  */
  91: public class LinkedHashSet<T> extends HashSet<T>
  92:   implements Set<T>, Cloneable, Serializable
  93: {
  94:   /**
  95:    * Compatible with JDK 1.4.
  96:    */
  97:   private static final long serialVersionUID = -2851667679971038690L;
  98: 
  99:   /**
 100:    * Construct a new, empty HashSet whose backing HashMap has the default
 101:    * capacity (11) and loadFacor (0.75).
 102:    */
 103:   public LinkedHashSet()
 104:   {
 105:     super();
 106:   }
 107: 
 108:   /**
 109:    * Construct a new, empty HashSet whose backing HashMap has the supplied
 110:    * capacity and the default load factor (0.75).
 111:    *
 112:    * @param initialCapacity the initial capacity of the backing HashMap
 113:    * @throws IllegalArgumentException if the capacity is negative
 114:    */
 115:   public LinkedHashSet(int initialCapacity)
 116:   {
 117:     super(initialCapacity);
 118:   }
 119: 
 120:   /**
 121:    * Construct a new, empty HashSet whose backing HashMap has the supplied
 122:    * capacity and load factor.
 123:    *
 124:    * @param initialCapacity the initial capacity of the backing HashMap
 125:    * @param loadFactor the load factor of the backing HashMap
 126:    * @throws IllegalArgumentException if either argument is negative, or
 127:    *         if loadFactor is POSITIVE_INFINITY or NaN
 128:    */
 129:   public LinkedHashSet(int initialCapacity, float loadFactor)
 130:   {
 131:     super(initialCapacity, loadFactor);
 132:   }
 133: 
 134:   /**
 135:    * Construct a new HashSet with the same elements as are in the supplied
 136:    * collection (eliminating any duplicates, of course). The backing storage
 137:    * has twice the size of the collection, or the default size of 11,
 138:    * whichever is greater; and the default load factor (0.75).
 139:    *
 140:    * @param c a collection of initial set elements
 141:    * @throws NullPointerException if c is null
 142:    */
 143:   public LinkedHashSet(Collection<? extends T> c)
 144:   {
 145:     super(c);
 146:   }
 147: 
 148:   /**
 149:    * Helper method which initializes the backing Map.
 150:    *
 151:    * @param capacity the initial capacity
 152:    * @param load the initial load factor
 153:    * @return the backing HashMap
 154:    */
 155:   HashMap<T, String> init(int capacity, float load)
 156:   {
 157:     return new LinkedHashMap<T, String>(capacity, load);
 158:   }
 159: }