【HashSet】| 深度剥析Java SE 源码合集Ⅲ

一. 🦁 HashSet介绍

1.1 特点

HashSet 是一个不保证元素的顺序且没有重复元素的集合，是线程不安全的。HashSet
允许有 null 元素。

1.2 底层实现

1. HashSet底层使用 HashMap 存储元素的。
2. HashMap 底层使用的是数组与链表实现元素的存储。
3. 元素在数组中存放时，并不是有序存放的也不是随机存放的，而是对元素的哈希值进行运算决定元素在数组中的位置。
4. 当两个元素的哈希值进行运算后得到相同的在数组中的位置时，会调用元素的 equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素，如果不相同则会使用单向链表保存该元素。

二. 🦁 结构以及对应方法分析

2.1 结构组成

2.1.1 源码实现

HashSet的源码并没有很多，因为其基本是调用HashMap的方法来实现的。

package java.util;import java.io.InvalidObjectException;
import jdk.internal.access.SharedSecrets;public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{static final long serialVersionUID = -5024744406713321676L;private transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapprivate 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*/public HashSet(Collection<? extends E> c) {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*             than zero, or if the load factor is nonpositive*/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*/public HashSet(int initialCapacity) {map = new HashMap<>(initialCapacity);}/*** Constructs a new, empty linked hash set.  (This package private* constructor is only used by LinkedHashSet.) The backing* HashMap instance is a LinkedHashMap with 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* @param      dummy             ignored (distinguishes this*             constructor from other int, float constructor.)* @throws     IllegalArgumentException if the initial capacity is less*             than zero, or if the load factor is nonpositive*/HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);}/*** 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*/public Iterator<E> iterator() {return map.keySet().iterator();}/*** Returns the number of elements in this set (its cardinality).** @return the number of elements in this set (its cardinality)*/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 Objects.equals(o, e)}.** @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 Objects.equals(e, e2)}.* 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 Objects.equals(o, e)},* 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;}/*** Removes all of the elements from this set.* The set will be empty after this call returns.*/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")public Object clone() {try {HashSet<E> newSet = (HashSet<E>) super.clone();newSet.map = (HashMap<E, Object>) map.clone();return newSet;} catch (CloneNotSupportedException e) {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.*/private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException {// Write out any hidden serialization magics.defaultWriteObject();// Write out HashMap capacity and load factors.writeInt(map.capacity());s.writeFloat(map.loadFactor());// Write out sizes.writeInt(map.size());// Write out all elements in the proper order.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 {// Consume and ignore stream fields (currently zero).s.readFields();// Read capacity and verify non-negative.int capacity = s.readInt();if (capacity < 0) {throw new InvalidObjectException("Illegal capacity: " +capacity);}// Read load factor and verify positive and non NaN.float loadFactor = s.readFloat();if (loadFactor <= 0 || Float.isNaN(loadFactor)) {throw new InvalidObjectException("Illegal load factor: " +loadFactor);}// Clamp load factor to range of 0.25...4.0.loadFactor = Math.min(Math.max(0.25f, loadFactor), 4.0f);// Read size and verify non-negative.int size = s.readInt();if (size < 0) {throw new InvalidObjectException("Illegal size: " + size);}// Set the capacity according to the size and load factor ensuring that// the HashMap is at least 25% full but clamping to maximum capacity.capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),HashMap.MAXIMUM_CAPACITY);// Constructing the backing map will lazily create an array when the first element is// added, so check it before construction. Call HashMap.tableSizeFor to compute the// actual allocation size. Check Map.Entry[].class since it's the nearest public type to// what is actually created.SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Map.Entry[].class, HashMap.tableSizeFor(capacity));// Create backing HashMapmap = (((HashSet<?>)this) instanceof LinkedHashSet ?new LinkedHashMap<>(capacity, loadFactor) :new HashMap<>(capacity, loadFactor));// Read in all elements in the proper order.for (int i=0; i<size; i++) {@SuppressWarnings("unchecked")E e = (E) s.readObject();map.put(e, PRESENT);}}/*** Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>* and <em>fail-fast</em> {@link Spliterator} over the elements in this* set.** <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and* {@link Spliterator#DISTINCT}.  Overriding implementations should document* the reporting of additional characteristic values.** @return a {@code Spliterator} over the elements in this set* @since 1.8*/public Spliterator<E> spliterator() {return new HashMap.KeySpliterator<>(map, 0, -1, 0, 0);}
}

2.1.2 成员变量及构造方法

1. HashMap<E,Object> map：存储元素的容器
2. Object PRESENT = new Object()：充当map中的value
3. 构造方法：这个无参构造方法里new了一个HashMap容器。说明了HashSet的底层是由HashMap实现的。

   static final long serialVersionUID = -5024744406713321676L;private transient HashMap<E,Object> map;// Dummy value to associate with an Object in the backing Mapprivate 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<>();}

2.2 常用的方法

2.2.1 添加add(E e)方法

    /*** 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 Objects.equals(e, e2)}.* 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;}

由源码可以看到，添加方法是通过返回一个布尔类型，而有趣的是它的实现方法居然是直接调用map的put()方法，而参数e则是放在了key的位置，value位置则是前面看到的成员变量。这里很好的说明了HashSet的值为什么不能重复，而且是无序的，因为HashMap的key就是无序的，而且不能重复。

2.2.2 删除remove(Object o)方法

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

这里的删除方法是调用了HashMap的remove(),这个方法在HashMap中是直接根据主键删除对应的元素，非常直观。

三. 最后想说

学习源码知识，有助于帮助我们扎实内功,提升程序员的涵养，如果您不想直接在idea查看源码，也想了解他，可以关注博主，都给您整理好啦，好了，文章到这里就结束啦，咱们下期见，喜欢可以一键三连哦😄