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: }