HashSet 是一个不保证元素的顺序且没有重复元素的集合
,是线程不安全的。HashSet
允许有 null 元素。
- HashSet底层使用 HashMap 存储元素的。
- HashMap 底层使用的是数组与链表实现元素的存储。
- 元素在数组中存放时,并不是有序存放的也不是随机存放的,而是
对元素的哈希值进行运算决定元素在数组中的位置
。- 当两个元素的哈希值进行运算后得到相同的在数组中的位置时,会调用元素的 equals()方法判断两个元素是否相同。如果元素相同则不会添加该元素,如果不相同则会使用单向链表保存该元素。
HashSet的源码并没有很多,因为其基本是调用HashMap的方法来实现的。
package java.util;import java.io.InvalidObjectException;
import jdk.internal.access.SharedSecrets;public class HashSetextends AbstractSetimplements Set, Cloneable, java.io.Serializable
{static final long serialVersionUID = -5024744406713321676L;private transient HashMap 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 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 newSet = (HashSet) super.clone();newSet.map = (HashMap) 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@SuppressWarnings("unchecked")E e = (E) s.readObject();map.put(e, PRESENT);}}/*** Creates a late-binding* and fail-fast {@link Spliterator} over the elements in this* set.** 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 spliterator() {return new HashMap.KeySpliterator<>(map, 0, -1, 0, 0);}
}
- HashMap
map:存储元素的容器 - Object PRESENT = new Object():充当map中的value
- 构造方法:这个无参构造方法里new了一个HashMap容器。说明了HashSet的底层是由HashMap实现的。
static final long serialVersionUID = -5024744406713321676L;private transient HashMap 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<>();}
/*** 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就是无序的,而且不能重复。
public boolean remove(Object o) {return map.remove(o)==PRESENT;}
这里的删除方法是调用了HashMap的remove(),这个方法在HashMap中是直接根据主键删除对应的元素,非常直观。
学习源码知识,有助于帮助我们扎实内功,提升程序员的涵养,如果您不想直接在idea查看源码,也想了解他,可以关注博主,都给您整理好啦,好了,文章到这里就结束啦,咱们下期见,喜欢可以一键三连哦😄