0N/A/*
3909N/A * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
2362N/A * published by the Free Software Foundation. Oracle designates this
0N/A * particular file as subject to the "Classpath" exception as provided
2362N/A * by Oracle in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
2362N/A * or visit www.oracle.com if you need additional information or have any
2362N/A * questions.
0N/A */
0N/A
0N/Apackage java.util;
0N/A
0N/A/**
0N/A * This class implements the <tt>Set</tt> interface, backed by a hash table
0N/A * (actually a <tt>HashMap</tt> instance). It makes no guarantees as to the
0N/A * iteration order of the set; in particular, it does not guarantee that the
0N/A * order will remain constant over time. This class permits the <tt>null</tt>
0N/A * element.
0N/A *
0N/A * <p>This class offers constant time performance for the basic operations
0N/A * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
0N/A * assuming the hash function disperses the elements properly among the
0N/A * buckets. Iterating over this set requires time proportional to the sum of
0N/A * the <tt>HashSet</tt> instance's size (the number of elements) plus the
0N/A * "capacity" of the backing <tt>HashMap</tt> instance (the number of
0N/A * buckets). Thus, it's very important not to set the initial capacity too
0N/A * high (or the load factor too low) if iteration performance is important.
0N/A *
0N/A * <p><strong>Note that this implementation is not synchronized.</strong>
0N/A * If multiple threads access a hash set concurrently, and at least one of
0N/A * the threads modifies the set, it <i>must</i> be synchronized externally.
0N/A * This is typically accomplished by synchronizing on some object that
0N/A * naturally encapsulates the set.
0N/A *
0N/A * If no such object exists, the set should be "wrapped" using the
0N/A * {@link Collections#synchronizedSet Collections.synchronizedSet}
0N/A * method. This is best done at creation time, to prevent accidental
0N/A * unsynchronized access to the set:<pre>
0N/A * Set s = Collections.synchronizedSet(new HashSet(...));</pre>
0N/A *
0N/A * <p>The iterators returned by this class's <tt>iterator</tt> method are
0N/A * <i>fail-fast</i>: if the set is modified at any time after the iterator is
0N/A * created, in any way except through the iterator's own <tt>remove</tt>
0N/A * method, the Iterator throws a {@link ConcurrentModificationException}.
0N/A * Thus, in the face of concurrent modification, the iterator fails quickly
0N/A * and cleanly, rather than risking arbitrary, non-deterministic behavior at
0N/A * an undetermined time in the future.
0N/A *
0N/A * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
0N/A * as it is, generally speaking, impossible to make any hard guarantees in the
0N/A * presence of unsynchronized concurrent modification. Fail-fast iterators
0N/A * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
0N/A * Therefore, it would be wrong to write a program that depended on this
0N/A * exception for its correctness: <i>the fail-fast behavior of iterators
0N/A * should be used only to detect bugs.</i>
0N/A *
0N/A * <p>This class is a member of the
0N/A * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0N/A * Java Collections Framework</a>.
0N/A *
0N/A * @param <E> the type of elements maintained by this set
0N/A *
0N/A * @author Josh Bloch
0N/A * @author Neal Gafter
0N/A * @see Collection
0N/A * @see Set
0N/A * @see TreeSet
0N/A * @see HashMap
0N/A * @since 1.2
0N/A */
0N/A
0N/Apublic class HashSet<E>
0N/A extends AbstractSet<E>
0N/A implements Set<E>, Cloneable, java.io.Serializable
0N/A{
0N/A static final long serialVersionUID = -5024744406713321676L;
0N/A
0N/A private transient HashMap<E,Object> map;
0N/A
0N/A // Dummy value to associate with an Object in the backing Map
0N/A private static final Object PRESENT = new Object();
0N/A
0N/A /**
0N/A * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
0N/A * default initial capacity (16) and load factor (0.75).
0N/A */
0N/A public HashSet() {
3323N/A map = new HashMap<>();
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new set containing the elements in the specified
0N/A * collection. The <tt>HashMap</tt> is created with default load factor
0N/A * (0.75) and an initial capacity sufficient to contain the elements in
0N/A * the specified collection.
0N/A *
0N/A * @param c the collection whose elements are to be placed into this set
0N/A * @throws NullPointerException if the specified collection is null
0N/A */
0N/A public HashSet(Collection<? extends E> c) {
3323N/A map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
0N/A addAll(c);
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
0N/A * the specified initial capacity and the specified load factor.
0N/A *
0N/A * @param initialCapacity the initial capacity of the hash map
0N/A * @param loadFactor the load factor of the hash map
0N/A * @throws IllegalArgumentException if the initial capacity is less
0N/A * than zero, or if the load factor is nonpositive
0N/A */
0N/A public HashSet(int initialCapacity, float loadFactor) {
3323N/A map = new HashMap<>(initialCapacity, loadFactor);
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
0N/A * the specified initial capacity and default load factor (0.75).
0N/A *
0N/A * @param initialCapacity the initial capacity of the hash table
0N/A * @throws IllegalArgumentException if the initial capacity is less
0N/A * than zero
0N/A */
0N/A public HashSet(int initialCapacity) {
3323N/A map = new HashMap<>(initialCapacity);
0N/A }
0N/A
0N/A /**
0N/A * Constructs a new, empty linked hash set. (This package private
0N/A * constructor is only used by LinkedHashSet.) The backing
0N/A * HashMap instance is a LinkedHashMap with the specified initial
0N/A * capacity and the specified load factor.
0N/A *
0N/A * @param initialCapacity the initial capacity of the hash map
0N/A * @param loadFactor the load factor of the hash map
0N/A * @param dummy ignored (distinguishes this
0N/A * constructor from other int, float constructor.)
0N/A * @throws IllegalArgumentException if the initial capacity is less
0N/A * than zero, or if the load factor is nonpositive
0N/A */
0N/A HashSet(int initialCapacity, float loadFactor, boolean dummy) {
3323N/A map = new LinkedHashMap<>(initialCapacity, loadFactor);
0N/A }
0N/A
0N/A /**
0N/A * Returns an iterator over the elements in this set. The elements
0N/A * are returned in no particular order.
0N/A *
0N/A * @return an Iterator over the elements in this set
0N/A * @see ConcurrentModificationException
0N/A */
0N/A public Iterator<E> iterator() {
0N/A return map.keySet().iterator();
0N/A }
0N/A
0N/A /**
0N/A * Returns the number of elements in this set (its cardinality).
0N/A *
0N/A * @return the number of elements in this set (its cardinality)
0N/A */
0N/A public int size() {
0N/A return map.size();
0N/A }
0N/A
0N/A /**
0N/A * Returns <tt>true</tt> if this set contains no elements.
0N/A *
0N/A * @return <tt>true</tt> if this set contains no elements
0N/A */
0N/A public boolean isEmpty() {
0N/A return map.isEmpty();
0N/A }
0N/A
0N/A /**
0N/A * Returns <tt>true</tt> if this set contains the specified element.
0N/A * More formally, returns <tt>true</tt> if and only if this set
0N/A * contains an element <tt>e</tt> such that
0N/A * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
0N/A *
0N/A * @param o element whose presence in this set is to be tested
0N/A * @return <tt>true</tt> if this set contains the specified element
0N/A */
0N/A public boolean contains(Object o) {
0N/A return map.containsKey(o);
0N/A }
0N/A
0N/A /**
0N/A * Adds the specified element to this set if it is not already present.
0N/A * More formally, adds the specified element <tt>e</tt> to this set if
0N/A * this set contains no element <tt>e2</tt> such that
0N/A * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
0N/A * If this set already contains the element, the call leaves the set
0N/A * unchanged and returns <tt>false</tt>.
0N/A *
0N/A * @param e element to be added to this set
0N/A * @return <tt>true</tt> if this set did not already contain the specified
0N/A * element
0N/A */
0N/A public boolean add(E e) {
0N/A return map.put(e, PRESENT)==null;
0N/A }
0N/A
0N/A /**
0N/A * Removes the specified element from this set if it is present.
0N/A * More formally, removes an element <tt>e</tt> such that
0N/A * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>,
0N/A * if this set contains such an element. Returns <tt>true</tt> if
0N/A * this set contained the element (or equivalently, if this set
0N/A * changed as a result of the call). (This set will not contain the
0N/A * element once the call returns.)
0N/A *
0N/A * @param o object to be removed from this set, if present
0N/A * @return <tt>true</tt> if the set contained the specified element
0N/A */
0N/A public boolean remove(Object o) {
0N/A return map.remove(o)==PRESENT;
0N/A }
0N/A
0N/A /**
0N/A * Removes all of the elements from this set.
0N/A * The set will be empty after this call returns.
0N/A */
0N/A public void clear() {
0N/A map.clear();
0N/A }
0N/A
0N/A /**
0N/A * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
0N/A * themselves are not cloned.
0N/A *
0N/A * @return a shallow copy of this set
0N/A */
0N/A public Object clone() {
0N/A try {
0N/A HashSet<E> newSet = (HashSet<E>) super.clone();
0N/A newSet.map = (HashMap<E, Object>) map.clone();
0N/A return newSet;
0N/A } catch (CloneNotSupportedException e) {
0N/A throw new InternalError();
0N/A }
0N/A }
0N/A
0N/A /**
0N/A * Save the state of this <tt>HashSet</tt> instance to a stream (that is,
0N/A * serialize it).
0N/A *
0N/A * @serialData The capacity of the backing <tt>HashMap</tt> instance
0N/A * (int), and its load factor (float) are emitted, followed by
0N/A * the size of the set (the number of elements it contains)
0N/A * (int), followed by all of its elements (each an Object) in
0N/A * no particular order.
0N/A */
0N/A private void writeObject(java.io.ObjectOutputStream s)
0N/A throws java.io.IOException {
0N/A // Write out any hidden serialization magic
0N/A s.defaultWriteObject();
0N/A
0N/A // Write out HashMap capacity and load factor
0N/A s.writeInt(map.capacity());
0N/A s.writeFloat(map.loadFactor());
0N/A
0N/A // Write out size
0N/A s.writeInt(map.size());
0N/A
0N/A // Write out all elements in the proper order.
1771N/A for (E e : map.keySet())
1771N/A s.writeObject(e);
0N/A }
0N/A
0N/A /**
0N/A * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
0N/A * deserialize it).
0N/A */
0N/A private void readObject(java.io.ObjectInputStream s)
0N/A throws java.io.IOException, ClassNotFoundException {
0N/A // Read in any hidden serialization magic
0N/A s.defaultReadObject();
0N/A
0N/A // Read in HashMap capacity and load factor and create backing HashMap
0N/A int capacity = s.readInt();
0N/A float loadFactor = s.readFloat();
0N/A map = (((HashSet)this) instanceof LinkedHashSet ?
0N/A new LinkedHashMap<E,Object>(capacity, loadFactor) :
0N/A new HashMap<E,Object>(capacity, loadFactor));
0N/A
0N/A // Read in size
0N/A int size = s.readInt();
0N/A
0N/A // Read in all elements in the proper order.
0N/A for (int i=0; i<size; i++) {
0N/A E e = (E) s.readObject();
0N/A map.put(e, PRESENT);
0N/A }
0N/A }
0N/A}