HashSet (JDK1.8)

A HashSet is an array + linked list (or red-black tree) implementation that does not allow a hash table with repeating elements

Again, let’s start with the class diagram

As you can see from the class diagram, HashSet inherits an abstract class and implements three interfaces.

  • AbstractSet: This provides operations related to iterators
  • Set: provides operations such as add, delete, modify, and query
  • Cloneable: Copy operations by field
  • Serializable: Enables its serialization operation

attribute

Attribute related source code


    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

Copy the code

private transient HashMap<E,Object> map; // Store the structure of the element directly using HashMap

private static final Object PRESENT = new Object(); // Each virtual Value stored in the HashMap Value

A constructor

public HashSet() { map = new HashMap<>(); } public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } //default access permission, do not allow users to call directly, HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }Copy the code

It can be seen from the four constructors that the main parameters are initialCapacity and loadFactor, which completely correspond to the constructors of HashMap

InitialCapacity: indicates the initialCapacity. The default value is 16 of the HashMap

LoadFactor: loadFactor. The default value is 0.75

Add and delete

Insert elements


    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    
Copy the code

The put method of the HashMap is called, and the value is PRESENT, and the put method performs the analysis of the HashMap

Remove elements


    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

Copy the code

It’s just a call to the remove method of the HashMap, and it returns the value to determine if it’s PRESENT, and the specific remove performs the analysis of the HashMap

Other methods

Contains () and clear() are the corresponding methods of the HashMap that are called directly. A HashSet is a hash table that does not allow duplicate elements, except that the value is PRESENT and the key is unique

The contrast

  • A HashSet, like a HashMap, is thread-unsafe

  • LinkedHashSet inherits HashSet, but is implemented through LinkedHashMap