preface
HashSet implements the Set interface, whose underlying layer is supported by HashMap. The elements of a HashSet are actually stored on the keys of the underlying HashMap. Due to the unordered non-repeating nature of a HashMap, elements stored in a HashSet are also unordered and cannot be repeated, and only one NULL element is allowed to be stored.
HashSet source code analysis
Main attributes:
Private TRANSIENT HashMap<E,Object> map; Private static final Object PRESENT = new Object();Copy the code
A HashSet is used to store elements in a HashMap. Since it only needs to be stored in a key, the virtual object PRESENT is used to reference the value of the key-value inserted in the map. Each time an element is added to the map, the value corresponding to the key-value pair is PRESENT.
Constructor:
Public is constructed with no arguments by defaultHashSet() { 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) {map = new HashMap<>(initialCapacity); } public HashSet(int initialCapacity,floatloadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } // This constructor cannot be called externally, so that LinkedHashSet overwrites HashSet(int initialCapacity,float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}Copy the code
Constructors are initial maps that are stored when elements are added.
Important methods:
// Set size public intsize() {
returnmap.size(); } // Whether the collection is empty public BooleanisEmpty() {
returnmap.isEmpty(); } public Boolean add(E E) {returnmap.put(e, PRESENT)==null; } public Boolean remove(Object o) {returnmap.remove(o)==PRESENT; } // Empty the collection public voidclear() { map.clear(); } public Boolean contains(Object o) {public Boolean contains(Object o) {return map.containsKey(o);
}Copy the code
Adding, deleting, modifying, and checking hashsets, as well as manipulating maps directly, is very simple.
LinkedHashSet
LinkedHashSet is derived from HashSet and is constructed by:
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}Copy the code
The LinkedHashSet constructor calls this constructor of the parent HashSet class:
LinkedHashMap HashSet(int initialCapacity,float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}Copy the code
So, underneath it is a LinkedHashMap, and all operations of elements are maintained by LinkedHashMap. The difference between LinkedHashSet and HashSet is the same as the difference between LinkedHashMap and HashMap. LinkedHashMap and LinkedHashSet are ordered, and the order is recorded internally by a two-way linked list, while HashMap and HashSet are unordered.
The last
For HashSet/LinkedHashSet, as long as you read the source code of HashMap/LinkedHashMap, you can almost fully understand how it is implemented. The storage, deletion and access of data in HashSet/LinkedHashSet are all direct operations on the internal HashMap. It can be said that HashSet/LinkedHashSet is a shell added on the basis of HashMap/LinkedHashMap. The only difference is that HashSet/LinkedHashSet holds elements as individual data or objects, whereas HashMap/LinkedHashMap holds elements as key-value pairs.