深度解析HashSet.add执行过程

一、创建新的HashSet对象。

我们先看一段代码，这里调用了HashSet的无参构造方法，创建了一个新的对象，将对象的引用赋值给了它实现的接口Set。

Set<String> set=new HashSet<String>();

调用HashSet的无参构造，实际上是调用了HashMap的无参构造初始化了成员变量map。

public HashSet() {
    map = new HashMap<>();
}

二、HashSet.add过程

这里我们看一下JDK1.8 里面add的方法源码：

set.add("Jim");

调用HashSet里的add方法添加元素，这里的e为我们要传入的对象“Jim”，它 依然是调用的是hashMap里的put方法，如果该方法结果return map.put(e, PRESENT)==null返回值为true，map.put（e，PERSENT）返回的结果为空。

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

进入put方法后，这里又调用了HashMap里的putkey，之前e里的“Jim”传入到put里的key中，putVal()传入的第一个参数调用了hash()方法。

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

三、hash()的实现原理;

hash接收到的参数类型为object，这里传入的key被上转型为object类型。

hash的返回值，如果传入的key值为空则返回0，key值不为空则调用object里的HashCode方法，这里由于string重写了object里的hashCode()方法，所以调用的是string里的hashCode()方法，然后进行右移位运算，在于之前得到的hashCode()进行按位异或运算得到hash值。

static final int hash(Object key) {
    int h;    
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}

四、HashMap中putVal方法。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //table为新对象数组tab赋值，并判断其是否为空。
    //数组tab的长度赋值给n，并判断其是否为空。
    //如果有一个条件成立，tab指向了一个长度为16的数组将其长度赋值给n。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //根据hash与（n-1）的按位与计算出Jim在tab数组中的下标。赋值给p，判断其是否为空
    //因为String中重写了hashCode的方法，如果String类型中两个值相同则hash值相同。
    if ((p = tab[i = (n - 1) & hash]) == null)
         /*
            数组内没有将要添加的元素
         */
    
        //如果传入hash后tab[i]的元素为空，则为该数组添加该元素。
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        /*
            数组中含有将要添加的元素
         */  
        //如果传入hash后tab[i]的元素不为空，调取这个数组元素的hash值与传入的hash作比较
        if (p.hash == hash &&
        //同时与（这个元素的key地址值赋值给k，再与传入的key地址值）作比较
        //或者传入的key地址值不为空同时传入的key和本数组key元素赋值的k作比较
        //因为String中同样重写了equals方法，实质是比较字符转内容后是否相同。
            ((k = p.key) == key || (key != null && key.equals(k))))
            //那么就将已存在的p值赋值给e
            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;
            }
        }
        //然后然后就到了这里，通过上面的逻辑，如果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;
}

1.如果传入的key值与数组内的元素相同，则return返回的值最后传入hashSet的add方法中，map.put(e, PRESENT)==null，因为返回值不为空，所以结果为false。

2.如果传入的key值与数组内的元素不相同，则上述结果返回return null;，返回的值最后传入hashSet的add方法中，map.put(e, PRESENT)==null，因为返回值为空，所以结果为true

//HashMap里的resize方法，第一次添加元素时，会创建一个长度为16的数组。
final Node<K,V>[] resize() {       
    newCap = DEFAULT_INITIAL_CAPACITY; //静态常量，默认容量16。
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}