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