HashSet is pass

JAVA COLLECTIONS source

1. What is a HashSet

• At the bottom, elements are stored using a HashMap
• Non-heavy, out-of-order, out of sync
• This version is based on JDK1.7

2. Data structure of HashSet

• The class definition

      

       
public class HashSet<E>
       
    extends AbstractSet<E>
       
    implements Set<E>, Cloneable. java.io.Serializable
      

• Important global variable

      

       
// Maintain a HashMap as the underlying data structure
       
private transient HashMap<E.Object> map;
       
Dummy Value, used as the default value of the underlying map when the HashSet is stored
       
private static final Object PRESENT = new Object(a);
      

• The constructor

      

       
/ * *
       
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
       
 * default initial capacity (16) and load factor (0.75).
       
* /
       
public HashSet(a) {
       
    map = new HashMap< > ();
       
}
       
/ * *
       
* Constructs a new set containing elements from the specified collection.
       
* The actual underlying layer creates a HashMap using the default load factor of 0.75 and an initial capacity large enough to contain all elements in the specified collection.
       
* @param c where elements will be stored in collection in this set.
       
* /
       
public HashSet(Collection<? extends E> c) {
       
    map = new HashMap<E.Object> (Math.max((int) (c.size(a) /.75f) + 1. 16));
       
    addAll(c);
       
}
       
/ * *
       
Construct an empty HashSet with the specified initialCapacity and loadFactor.
       
* The underlying layer actually constructs an empty HashMap with the corresponding parameters.
       
* @param initialCapacity initialCapacity.
       
* @param loadFactor Loads the factor.
       
* /
       
public HashSet(int initialCapacity. float loadFactor) {
       
    map = new HashMap< > (initialCapacity. loadFactor);
       
}
       
/ * *
       
* Construct an empty HashSet with the specified initialCapacity.
       
* the actual underlying construct is an empty HashMap with the corresponding argument and loadFactor loadFactor of 0.75.
       
* @param initialCapacity initialCapacity.
       
* /
       
public HashSet(int initialCapacity) {
       
    map = new HashMap< > (initialCapacity);
       
}
       
/ * *
       
* Constructs a new null link hash set with the specified initialCapacity and loadFactor. This constructor is package access, is not public, and is really just support for LinkedHashSet. The underlying implementation is to construct an empty LinkedHashMap instance with the specified parameters.
       
* @param initialCapacity initialCapacity.
       
* @param loadFactor Loads the factor.
       
* @param dummy flag.
       
* /
       
HashSet(int initialCapacity. float loadFactor. boolean dummy) {
       
    map = new LinkedHashMap< > (initialCapacity. loadFactor);
       
}
      

3. The HashSet storage

• Add method parsing

      

       
/ * *
       
* Use HashMap as the underlying data structure
       
* 1. Implement non-duplicate key in HashMap
       
* 2. The HashSet is not ordered because the HashMap is not ordered
       
* 3. The HashMap value uses a final static variable as the default value
       
* @return Return true if put succeeds, false otherwise (this method returns null when adding non-duplicate key pairs)
       
* /
       
public boolean add(E e) {
       
    return map.put(e. PRESENT) = =null;
       
}
      

• Analysis of Clone Method

      

       
/ * *
       
* Returns a shallow copy of this HashSet instance: the elements themselves are not copied
       
* @return The clone() method of HashMap is actually called to get a shallow copy of the HashMap
       
* develop:
       
* 1. Shallow copy is copying only the value type members of the class
       
* 2. A deep copy is a copy of a class's value type members and reference type members
       
* /
       
public Object clone(a) {
       
    try {
       
        HashSet<E> newSet = (HashSet<E>) super.clone(a);
       
        newSet.map = (HashMap<E. Object>) map.clone(a);
       
        return newSet;
       
    } catch (CloneNotSupportedException e) {
       
        throw new InternalError(a);
       
    }
       
}
      

• An iterative approach

      

       
/ * *
       
* 1. Iterator
          
            Iterator ()
          
       
* 2. Iterate over the map keySet
       
* /
       
public Iterator<E> iterator(a) {
       
    return map.keySet().iterator(a);
       
}
      

• inductive
  
  
  

  • For objects saved in the HashSet, be careful to overwrite them properlyequals 和 hashCodeMethod to ensure the uniqueness of the objects you put in
    
    
  • Ordered optionalLinkedHashSet.TreeSet
    
    
  • Thread safety is optionalCopyOnWriteArraySet.ConcurrentSkipListSet

notice