1/* 2 * Licensed to the Apache Software Foundation (ASF) under one or more 3 * contributor license agreements. See the NOTICE file distributed with 4 * this work for additional information regarding copyright ownership. 5 * The ASF licenses this file to You under the Apache License, Version 2.0 6 * (the "License"); you may not use this file except in compliance with 7 * the License. You may obtain a copy of the License at 8 * 9 * http://www.apache.org/licenses/LICENSE-2.0 10 * 11 * Unless required by applicable law or agreed to in writing, software 12 * distributed under the License is distributed on an "AS IS" BASIS, 13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14 * See the License for the specific language governing permissions and 15 * limitations under the License. 16 */ 17 18package java.util; 19 20import java.io.IOException; 21import java.io.ObjectInputStream; 22import java.io.ObjectOutputStream; 23import java.io.Serializable; 24 25/** 26 * HashSet is an implementation of a Set. All optional operations (adding and 27 * removing) are supported. The elements can be any objects. 28 */ 29public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, 30 Serializable { 31 32 private static final long serialVersionUID = -5024744406713321676L; 33 34 transient HashMap<E, HashSet<E>> backingMap; 35 36 /** 37 * Constructs a new empty instance of {@code HashSet}. 38 */ 39 public HashSet() { 40 this(new HashMap<E, HashSet<E>>()); 41 } 42 43 /** 44 * Constructs a new instance of {@code HashSet} with the specified capacity. 45 * 46 * @param capacity 47 * the initial capacity of this {@code HashSet}. 48 */ 49 public HashSet(int capacity) { 50 this(new HashMap<E, HashSet<E>>(capacity)); 51 } 52 53 /** 54 * Constructs a new instance of {@code HashSet} with the specified capacity 55 * and load factor. 56 * 57 * @param capacity 58 * the initial capacity. 59 * @param loadFactor 60 * the initial load factor. 61 */ 62 public HashSet(int capacity, float loadFactor) { 63 this(new HashMap<E, HashSet<E>>(capacity, loadFactor)); 64 } 65 66 /** 67 * Constructs a new instance of {@code HashSet} containing the unique 68 * elements in the specified collection. 69 * 70 * @param collection 71 * the collection of elements to add. 72 */ 73 public HashSet(Collection<? extends E> collection) { 74 this(new HashMap<E, HashSet<E>>(collection.size() < 6 ? 11 : collection 75 .size() * 2)); 76 for (E e : collection) { 77 add(e); 78 } 79 } 80 81 HashSet(HashMap<E, HashSet<E>> backingMap) { 82 this.backingMap = backingMap; 83 } 84 85 /** 86 * Adds the specified object to this {@code HashSet} if not already present. 87 * 88 * @param object 89 * the object to add. 90 * @return {@code true} when this {@code HashSet} did not already contain 91 * the object, {@code false} otherwise 92 */ 93 @Override 94 public boolean add(E object) { 95 return backingMap.put(object, this) == null; 96 } 97 98 /** 99 * Removes all elements from this {@code HashSet}, leaving it empty. 100 * 101 * @see #isEmpty 102 * @see #size 103 */ 104 @Override 105 public void clear() { 106 backingMap.clear(); 107 } 108 109 /** 110 * Returns a new {@code HashSet} with the same elements and size as this 111 * {@code HashSet}. 112 * 113 * @return a shallow copy of this {@code HashSet}. 114 * @see java.lang.Cloneable 115 */ 116 @Override 117 @SuppressWarnings("unchecked") 118 public Object clone() { 119 try { 120 HashSet<E> clone = (HashSet<E>) super.clone(); 121 clone.backingMap = (HashMap<E, HashSet<E>>) backingMap.clone(); 122 return clone; 123 } catch (CloneNotSupportedException e) { 124 throw new AssertionError(e); 125 } 126 } 127 128 /** 129 * Searches this {@code HashSet} for the specified object. 130 * 131 * @param object 132 * the object to search for. 133 * @return {@code true} if {@code object} is an element of this 134 * {@code HashSet}, {@code false} otherwise. 135 */ 136 @Override 137 public boolean contains(Object object) { 138 return backingMap.containsKey(object); 139 } 140 141 /** 142 * Returns true if this {@code HashSet} has no elements, false otherwise. 143 * 144 * @return {@code true} if this {@code HashSet} has no elements, 145 * {@code false} otherwise. 146 * @see #size 147 */ 148 @Override 149 public boolean isEmpty() { 150 return backingMap.isEmpty(); 151 } 152 153 /** 154 * Returns an Iterator on the elements of this {@code HashSet}. 155 * 156 * @return an Iterator on the elements of this {@code HashSet}. 157 * @see Iterator 158 */ 159 @Override 160 public Iterator<E> iterator() { 161 return backingMap.keySet().iterator(); 162 } 163 164 /** 165 * Removes the specified object from this {@code HashSet}. 166 * 167 * @param object 168 * the object to remove. 169 * @return {@code true} if the object was removed, {@code false} otherwise. 170 */ 171 @Override 172 public boolean remove(Object object) { 173 return backingMap.remove(object) != null; 174 } 175 176 /** 177 * Returns the number of elements in this {@code HashSet}. 178 * 179 * @return the number of elements in this {@code HashSet}. 180 */ 181 @Override 182 public int size() { 183 return backingMap.size(); 184 } 185 186 private void writeObject(ObjectOutputStream stream) throws IOException { 187 stream.defaultWriteObject(); 188 stream.writeInt(backingMap.table.length); 189 stream.writeFloat(HashMap.DEFAULT_LOAD_FACTOR); 190 stream.writeInt(size()); 191 for (E e : this) { 192 stream.writeObject(e); 193 } 194 } 195 196 @SuppressWarnings("unchecked") 197 private void readObject(ObjectInputStream stream) throws IOException, 198 ClassNotFoundException { 199 stream.defaultReadObject(); 200 int length = stream.readInt(); 201 float loadFactor = stream.readFloat(); 202 backingMap = createBackingMap(length, loadFactor); 203 int elementCount = stream.readInt(); 204 for (int i = elementCount; --i >= 0;) { 205 E key = (E) stream.readObject(); 206 backingMap.put(key, this); 207 } 208 } 209 210 HashMap<E, HashSet<E>> createBackingMap(int capacity, float loadFactor) { 211 return new HashMap<E, HashSet<E>>(capacity, loadFactor); 212 } 213} 214