HashSet源码解读

HashSet源码解读
一：先看其实现了哪些接口和继承了哪些类

1.实现了Serializable接口，表明它支持序列化。
2.实现了Cloneable接口，表明它支持克隆，可以调用超类的clone（）方法进行浅拷贝。

3.继承了AbstractSet抽象类，和ArrayList和 edList一样，在他们的抽象父类中，都提供了equals（）方法和hashCode（）方法。它们自身并不实现这两个方法

4.从JDK源码可以看出，底层并没有使用我们常规认为的利用hashcode（）方法求的值进行比较，而是通过调用AbstractCollection的containsAll（）方法，如果他们中元素完全相同（与顺序无关），则他们的equals（）方法的比较结果就为true。

复制代码

/** * Compares the specified   with this set for equality.  Returns * <tt>true</tt> if the given   is also a set, the two sets have * the same size, and every member of the given set is contained in * this set.  This ensures that the <tt>equals</tt> method works * properly across different implementations of the <tt>Set</tt> * interface.<p> * * This implementation first checks if the specified   is this * set; if so it returns <tt>true</tt>.  Then, it checks if the * specified   is a set whose size is identical to the size of * this set; if not, it returns false.  If so, it returns * <tt>containsAll((Collection) o)</tt>. * * @param o   to be compared for equality with this set * @return <tt>true</tt> if the specified   is equal to this set */public boolean equals(  o) {    if (o == this)        return true;    if (!(o instanceof Set))        return false;    Collection<?> c = (Collection<?>) o;

　　　　 //保证个数相等

    if (c.size() != size())        return false;    try {

　　　　　　 //调用了AbstractCollection的方法。

        return containsAll(c);    } catch (ClassCastException unused)   {        return false;    } catch (NullPointerException unused) {        return false;    }}

复制代码
复制代码
public boolean containsAll(Collection<?> c) {

//只需要逐个判断集合是否包含其中的元素。    for (  e : c)        if (!contains(e))            return false;    return true;}

复制代码
4.实现了Set接口。

二：HashSet概述
1.HashSet是通过HashMap的键来存值，HashMap里面的所有值都为null;

2.学习这个之前先看HashMap;附上网址https://www.cnblogs.com/xhlwjy/p/11246618.html

三：HashSet的属性
　　private transient HashMap map;//用HashMap的Key来存值

// Dummy value to associate with an   in the backing Mapprivate static final   PRESENT = new  ();//用于填充HashMap的value

四：构造方法
复制代码

/** * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has * default initial capacity (16) and load factor (0.75). */

　　//这个是初始化一个HashMap

public HashSet() {    map = new HashMap<>();}/** * Constructs a new set containing the elements in the specified * collection.  The <tt>HashMap</tt> 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 */

　　//初始化HashMap,把c集合中的所有元素添加到map中

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 <tt>HashMap</tt> 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 */

　　//初始化HashMap的容量和加载因子

public HashSet(int initialCapacity, float loadFactor) {    map = new HashMap<>(initialCapacity, loadFactor);}/** * Constructs a new, empty set; the backing <tt>HashMap</tt> 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 *///初始化HashMap的容量public HashSet(int initialCapacity) {    map = new HashMap<>(initialCapacity);}/** * Constructs a new, empty  ed hash set.  (This package private * constructor is only used by  edHashSet.) The backing * HashMap instance is a  edHashMap 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 */

　　//这个初始化使用的是 edHashMap

HashSet(int initialCapacity, float loadFactor, boolean dummy) {    map = new  edHashMap<>(initialCapacity, loadFactor);}

复制代码

五：添加新元素
复制代码
　　//底层仍然利用了HashMap键进行了元素的添加。
　　//在HashMap的put()方法中，该方法的返回值是对应HashMap中键值对中的值，而值总是PRESENT,
　　//该PRESENT一直都是private static final PRESENT = new ();
　　//PRESENT只是初始化了，并不能改变，所以PRESENT的值一直为null。
　　//所以只要插入成功了，put（）方法返回的值总是null。

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

复制代码

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}

这段代码就不分析了，与HashMap的插入差不多，可以先去看HashMap

复制代码
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {        Node<K,V> e; K k;        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        else if (p instanceof TreeNode)            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        else {            for (int binCount = 0; ; ++binCount) {                if ((e = p.next) == null) {                    p.next = newNode(hash, key, value, null);                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        if (e != null) { // existing mapping for key            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}

复制代码

六：删除一个元素

//该方法底层实现了仍然使用了map的remove（）方法。//map的remove（）方法的返回的是被删除键对应的值。（在HashSet的底层HashMap中的所有键值对的值都是PRESENT）public boolean remove(  o) {    return map.remove(o)==PRESENT;}

之后的代码就不粘贴出来了，自己可以去源码里面看

七：清空方法
public void clear() {

    map.clear();}

八：克隆方法
　　底层仍然使用了 的clone（）方法，得到的 对象，并把它强制转化为HashSet,然后把它的底层的HashMap也克隆一份（调用的HashMap的clone（）方法），并把它赋值给newSet，最后返回newSet即可。

复制代码
@SuppressWarnings("unchecked")

public   clone() {    try {        HashSet<E> newSet = (HashSet<E>) super.clone();        newSet.map = (HashMap<E,  >) map.clone();        return newSet;    } catch (CloneNotSupportedException e) {        throw new InternalError(e);    }}

复制代码
九：是否包含某个元素
底层使用了HashMap的containsKey（）

　　public boolean contains( o) {

    return map.containsKey(o);}

十：判读是不是空
调用HashMap的方法

　　public boolean isEmpty() {

    return map.isEmpty();}

十一：统计HashSet中包含元素的个数
　　public int size() {

    return map.size();}

十二：生成迭代器

public Iterator<E> iterator() {    return map.keySet().iterator();}

十三：序列化
复制代码

/** * Save the state of this <tt>HashSet</tt> instance to a stream (that is, * serialize it). * * @serialData The capacity of the backing <tt>HashMap</tt> 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  ) in *             no particular order. */private void write (java.io. OutputStream s)    throws java.io.IOException {    // Write out any hidden serialization magic    s.defaultWrite ();    // Write out HashMap capacity and load factor

　　　　 //容量写入流

    s.writeInt(map.capacity());

　　　　 //加载因子写入流

    s.writeFloat(map.loadFactor());    // Write out size

　　　　　//存放的数量写入流

    s.writeInt(map.size());    // Write out all elements in the proper order.

　　　　 //把每个元素写入流

    for (E e : map.keySet())        s.write (e);}

复制代码

十四：反序列化
复制代码
private void read (java.io. InputStream s)

    throws java.io.IOException, ClassNotFoundException {    // Read in any hidden serialization magic    s.defaultRead ();    // Read capacity and verify non-negative.    int capacity = s.readInt();    if (capacity < 0) {        throw new Invalid Exception("Illegal capacity: " +                                         capacity);    }    // Read load factor and verify positive and non NaN.    float loadFactor = s.readFloat();    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {        throw new Invalid Exception("Illegal load factor: " +                                         loadFactor);    }    // Read size and verify non-negative.    int size = s.readInt();    if (size < 0) {        throw new Invalid Exception("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);    //HashMap中构建哈希桶数组是在第一个元素被添加的时候才构建，所以在构建之前检查它,    // 调用HashMap.tableSizeFor来计算实际分配的大小,    // 检查Map.Entry []类，因为它是最接近的公共类型实际创建的内容。    SharedSecrets.getJavaOISAccess()                     .checkArray(s, Map.Entry[].class,HashMap.tableSizeFor(capacity));    //创建HashMap。    map = (((HashSet<?>)this) instanceof  edHashSet ?           new  edHashMap<E, >(capacity, loadFactor) :           new HashMap<E, >(capacity, loadFactor));    // 按写入流中的顺序再把元素依次读取出来放到map中。    for (int i=0; i<size; i++) {        @SuppressWarnings("unchecked")            E e = (E) s.read ();        map.put(e, PRESENT);    }}

复制代码
原文地址https://www.cnblogs.com/xhlwjy/p/11249286.html