< prev index next >
src/java.base/share/classes/java/util/HashSet.java
Print this page
*** 26,47 ****
package java.util;
import java.io.InvalidObjectException;
/**
! * This class implements the <tt>Set</tt> interface, backed by a hash table
! * (actually a <tt>HashMap</tt> 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 <tt>null</tt>
* element.
*
* <p>This class offers constant time performance for the basic operations
! * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
* assuming the hash function disperses the elements properly among the
* buckets. Iterating over this set requires time proportional to the sum of
! * the <tt>HashSet</tt> instance's size (the number of elements) plus the
! * "capacity" of the backing <tt>HashMap</tt> 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.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a hash set concurrently, and at least one of
--- 26,47 ----
package java.util;
import java.io.InvalidObjectException;
/**
! * This class implements the {@code Set} interface, backed by a hash table
! * (actually a {@code 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 {@code null}
* element.
*
* <p>This class offers constant time performance for the basic operations
! * ({@code add}, {@code remove}, {@code contains} and {@code size}),
* assuming the hash function disperses the elements properly among the
* buckets. Iterating over this set requires time proportional to the sum of
! * the {@code HashSet} instance's size (the number of elements) plus the
! * "capacity" of the backing {@code 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.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a hash set concurrently, and at least one of
*** 53,74 ****
* {@link Collections#synchronizedSet Collections.synchronizedSet}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the set:<pre>
* Set s = Collections.synchronizedSet(new HashSet(...));</pre>
*
! * <p>The iterators returned by this class's <tt>iterator</tt> method are
* <i>fail-fast</i>: if the set is modified at any time after the iterator is
! * created, in any way except through the iterator's own <tt>remove</tt>
* 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.
*
* <p>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 <tt>ConcurrentModificationException</tt> on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
* <p>This class is a member of the
--- 53,74 ----
* {@link Collections#synchronizedSet Collections.synchronizedSet}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the set:<pre>
* Set s = Collections.synchronizedSet(new HashSet(...));</pre>
*
! * <p>The iterators returned by this class's {@code iterator} method are
* <i>fail-fast</i>: if the set is modified at any time after the iterator is
! * created, in any way except through the iterator's own {@code 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.
*
* <p>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 {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
* <p>This class is a member of the
*** 96,115 ****
// 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 <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
! * collection. The <tt>HashMap</tt> 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
--- 96,115 ----
// 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 {@code HashMap} instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
/**
* Constructs a new set containing the elements in the specified
! * collection. The {@code 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
*** 118,128 ****
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
! * Constructs a new, empty set; the backing <tt>HashMap</tt> 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
--- 118,128 ----
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
! * Constructs a new, empty set; the backing {@code 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
*** 131,141 ****
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
! * Constructs a new, empty set; the backing <tt>HashMap</tt> 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
--- 131,141 ----
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
/**
! * Constructs a new, empty set; the backing {@code 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
*** 180,237 ****
public int size() {
return map.size();
}
/**
! * Returns <tt>true</tt> if this set contains no elements.
*
! * @return <tt>true</tt> if this set contains no elements
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
! * Returns <tt>true</tt> if this set contains the specified element.
! * More formally, returns <tt>true</tt> if and only if this set
! * contains an element <tt>e</tt> such that
! * <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this set is to be tested
! * @return <tt>true</tt> if this set contains the specified element
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* Adds the specified element to this set if it is not already present.
! * More formally, adds the specified element <tt>e</tt> to this set if
! * this set contains no element <tt>e2</tt> such that
! * <tt>(e==null ? e2==null : e.equals(e2))</tt>.
* If this set already contains the element, the call leaves the set
! * unchanged and returns <tt>false</tt>.
*
* @param e element to be added to this set
! * @return <tt>true</tt> if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* Removes the specified element from this set if it is present.
! * More formally, removes an element <tt>e</tt> such that
! * <tt>(o==null ? e==null : o.equals(e))</tt>,
! * if this set contains such an element. Returns <tt>true</tt> 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 <tt>true</tt> if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
--- 180,237 ----
public int size() {
return map.size();
}
/**
! * Returns {@code true} if this set contains no elements.
*
! * @return {@code true} if this set contains no elements
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
! * Returns {@code true} if this set contains the specified element.
! * More formally, returns {@code true} if and only if this set
! * contains an element {@code e} such that
! * <code>(o==null ? e==null : o.equals(e))</code>.
*
* @param o element whose presence in this set is to be tested
! * @return {@code true} if this set contains the specified element
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* Adds the specified element to this set if it is not already present.
! * More formally, adds the specified element {@code e} to this set if
! * this set contains no element {@code e2} such that
! * <code>(e==null ? e2==null : e.equals(e2))</code>.
* If this set already contains the element, the call leaves the set
! * unchanged and returns {@code false}.
*
* @param e element to be added to this set
! * @return {@code true} if this set did not already contain the specified
* element
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* Removes the specified element from this set if it is present.
! * More formally, removes an element {@code e} such that
! * <code>(o==null ? e==null : o.equals(e))</code>,
! * if this set contains such an element. Returns {@code 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 {@code true} if the set contained the specified element
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
*** 242,252 ****
public void clear() {
map.clear();
}
/**
! * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
* themselves are not cloned.
*
* @return a shallow copy of this set
*/
@SuppressWarnings("unchecked")
--- 242,252 ----
public void clear() {
map.clear();
}
/**
! * Returns a shallow copy of this {@code HashSet} instance: the elements
* themselves are not cloned.
*
* @return a shallow copy of this set
*/
@SuppressWarnings("unchecked")
*** 259,272 ****
throw new InternalError(e);
}
}
/**
! * Save the state of this <tt>HashSet</tt> instance to a stream (that is,
* serialize it).
*
! * @serialData The capacity of the backing <tt>HashMap</tt> instance
* (int), and its load factor (float) are emitted, followed by
* the size of the set (the number of elements it contains)
* (int), followed by all of its elements (each an Object) in
* no particular order.
*/
--- 259,272 ----
throw new InternalError(e);
}
}
/**
! * Save the state of this {@code HashSet} instance to a stream (that is,
* serialize it).
*
! * @serialData The capacity of the backing {@code HashMap} instance
* (int), and its load factor (float) are emitted, followed by
* the size of the set (the number of elements it contains)
* (int), followed by all of its elements (each an Object) in
* no particular order.
*/
*** 286,296 ****
for (E e : map.keySet())
s.writeObject(e);
}
/**
! * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
--- 286,296 ----
for (E e : map.keySet())
s.writeObject(e);
}
/**
! * Reconstitute the {@code HashSet} instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
< prev index next >