001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: import java.io.IOException;
021: import java.io.ObjectInputStream;
022: import java.io.ObjectOutputStream;
023: import java.io.Serializable;
024:
025: /**
026: * HashSet is an implementation of Set. All optional operations are supported,
027: * adding and removing. The elements can be any objects.
028: */
029: public class HashSet<E> extends AbstractSet<E> implements Set<E>,
030: Cloneable, Serializable {
031:
032: private static final long serialVersionUID = -5024744406713321676L;
033:
034: transient HashMap<E, HashSet<E>> backingMap;
035:
036: /**
037: * Constructs a new empty instance of HashSet.
038: */
039: public HashSet() {
040: this (new HashMap<E, HashSet<E>>());
041: }
042:
043: /**
044: * Constructs a new instance of HashSet with the specified capacity.
045: *
046: * @param capacity
047: * the initial capacity of this HashSet
048: */
049: public HashSet(int capacity) {
050: this (new HashMap<E, HashSet<E>>(capacity));
051: }
052:
053: /**
054: * Constructs a new instance of HashSet with the specified capacity and load
055: * factor.
056: *
057: * @param capacity
058: * the initial capacity
059: * @param loadFactor
060: * the initial load factor
061: */
062: public HashSet(int capacity, float loadFactor) {
063: this (new HashMap<E, HashSet<E>>(capacity, loadFactor));
064: }
065:
066: /**
067: * Constructs a new instance of HashSet containing the unique elements in
068: * the specified collection.
069: *
070: * @param collection
071: * the collection of elements to add
072: */
073: public HashSet(Collection<? extends E> collection) {
074: this (new HashMap<E, HashSet<E>>(collection.size() < 6 ? 11
075: : collection.size() * 2));
076: for (E e : collection) {
077: add(e);
078: }
079: }
080:
081: HashSet(HashMap<E, HashSet<E>> backingMap) {
082: this .backingMap = backingMap;
083: }
084:
085: /**
086: * Adds the specified object to this HashSet.
087: *
088: * @param object
089: * the object to add
090: * @return true when this HashSet did not already contain the object, false
091: * otherwise
092: */
093: @Override
094: public boolean add(E object) {
095: return backingMap.put(object, this ) == null;
096: }
097:
098: /**
099: * Removes all elements from this 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: * Answers a new HashSet with the same elements and size as this HashSet.
111: *
112: * @return a shallow copy of this HashSet
113: *
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
122: .clone();
123: return clone;
124: } catch (CloneNotSupportedException e) {
125: return null;
126: }
127: }
128:
129: /**
130: * Searches this HashSet for the specified object.
131: *
132: * @param object
133: * the object to search for
134: * @return true if <code>object</code> is an element of this HashSet,
135: * false otherwise
136: */
137: @Override
138: public boolean contains(Object object) {
139: return backingMap.containsKey(object);
140: }
141:
142: /**
143: * Answers if this HashSet has no elements, a size of zero.
144: *
145: * @return true if this HashSet has no elements, false otherwise
146: *
147: * @see #size
148: */
149: @Override
150: public boolean isEmpty() {
151: return backingMap.isEmpty();
152: }
153:
154: /**
155: * Answers an Iterator on the elements of this HashSet.
156: *
157: * @return an Iterator on the elements of this HashSet
158: *
159: * @see Iterator
160: */
161: @Override
162: public Iterator<E> iterator() {
163: return backingMap.keySet().iterator();
164: }
165:
166: /**
167: * Removes an occurrence of the specified object from this HashSet.
168: *
169: * @param object
170: * the object to remove
171: * @return true if this HashSet is modified, false otherwise
172: */
173: @Override
174: public boolean remove(Object object) {
175: return backingMap.remove(object) != null;
176: }
177:
178: /**
179: * Answers the number of elements in this HashSet.
180: *
181: * @return the number of elements in this HashSet
182: */
183: @Override
184: public int size() {
185: return backingMap.size();
186: }
187:
188: private void writeObject(ObjectOutputStream stream)
189: throws IOException {
190: stream.defaultWriteObject();
191: stream.writeInt(backingMap.elementData.length);
192: stream.writeFloat(backingMap.loadFactor);
193: stream.writeInt(backingMap.elementCount);
194: for (int i = backingMap.elementData.length; --i >= 0;) {
195: HashMap.Entry<E, HashSet<E>> entry = backingMap.elementData[i];
196: while (entry != null) {
197: stream.writeObject(entry.key);
198: entry = entry.next;
199: }
200: }
201: }
202:
203: @SuppressWarnings("unchecked")
204: private void readObject(ObjectInputStream stream)
205: throws IOException, ClassNotFoundException {
206: stream.defaultReadObject();
207: int length = stream.readInt();
208: float loadFactor = stream.readFloat();
209: backingMap = createBackingMap(length, loadFactor);
210: int elementCount = stream.readInt();
211: for (int i = elementCount; --i >= 0;) {
212: E key = (E) stream.readObject();
213: backingMap.put(key, this );
214: }
215: }
216:
217: HashMap<E, HashSet<E>> createBackingMap(int capacity,
218: float loadFactor) {
219: return new HashMap<E, HashSet<E>>(capacity, loadFactor);
220: }
221: }
|