4.2 put方法分析

源码分析：

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

    /**
     * @param hash：key的hash值
     * @param onlyIfAbsent  ：false表示key存在时，覆盖value
     * @param evict if false, the table is in creation mode.  待补充
     */
    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)
           //第一次put，先执行数组初始化操作
            n = (tab = resize()).length;
        //当前key对应的数组下标没有元素，则直接初始化新的Node到该数组位置
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null); //注意此时Node没有Next
        else {
        //当前key对应的数组下标已经存在元素
            Node<K,V> e; K k;
            // 情况一：//该位置的元素跟新put进来的数据key相等
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;    //注意这里是引用的赋值，因此后面e.value=value可以实现value覆盖
            //情况二：当前位置是红黑树结构
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeva l(this, tab, hash, key, value);
            else {
                //情况三：当前位置是链表结构
                for (int binCount = 0; ; ++binCount) {
                    //遍历到达链表末端
                    if ((e = p.next) == null) {
                        //创建新的Node并放在链表的末端
                        p.next = newNode(hash, key, value, null);
                        // treeify_threshold 为 8，所以，如果新插入的值是链表中的第 8 个，将链表转换为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //在链表当前位置找到相同的key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break; //这里break，代码后面统一对e进行value的覆盖处理
                    //此时既未遍历到链表末端，也没有发现key相等，则继续链表遍历
                    p = e;   //这个赋值，相当于链表的遍历，尾部指向下一个节点的头部，实现链表遍历
                }
            }
            if (e != null) { // existing mapping for key  key相等时
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;  //新的value覆盖旧的value值
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
        //每次put操作完成后，size自增；
        //如果size超过阈值，则在put完成后，再次执行扩容
            resize();
        afterNodeInsertion(evict);//父类抽象方法的实现，HashMap不做任何实现
        return null;
    }

• 第一次put时扩容过程如下：

容量：C
加载因子：F
扩容阈值：T

------ 1、无参初始化：
F=0.75
C=0
T=0

------ 2、有参初始化：容量参数=7
F=0.75
C=0
T=tableSizeFor(7)=8  //1、2、4、8 。。。大于7 所以取8

------ 3、第一次put && 无参初始化时
F=0.75
C=16（默认容量）
T=16*0.75=12

------ 4、第一次put && 有参初始化时
F=0.75
C=T=8 // 容量=阈值
T=8*0.75=6 // 阈值更新：容量*加载因子

5 关于HashMap

5.1 HashMap如何实现put、get操作时间复杂度为O(1)~O(n)?

1. 首先，对于数组的元素，如果知道index，那查找的复杂度就是O(1)级别
2. 对于get操作，首先根据key计算出hash值，而这个hash值 执行操作hash&(n-1)就是它所在的index，在最好的情况下，该index只有一个节点且hash值与key的hash值相等，那么时间的复杂度就是O(1)。当该节点为链表或者红黑树时，时间复杂度会上升，但是由于HashMap的优化（链表长度、红黑树长度相对HashMap容量不会过长，过长会触发resize操作），所以 最坏的情况也就是O(n) ,可能还会小于这个值。【链表的查询时间复杂度是：O (n)，红黑树是 O(logN)，比O (n)更小】
3. 对于put操作，我们知道，数组插入元素的成本是高昂的，HashMap巧妙的 使用链表和红黑树代替了数组插入元素需要移动后续元素的消耗，这样在最好的情况下，插入一个元素，该index位置恰好没有元素的话，时间复杂度就是O(1),当该位置有元素且为链表或者红黑树的情况下，时间复杂度会上升，但是最坏的情况下也就是O(n)。

5.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树？

1. 单节点转链表：当计算出来的index处有元素，且元素是单节点时，则该节点变为链表；
2. 链表转红黑树有两个条件：
   1. 链表长度大于TREEIFY_THRESHOLD，默认阈值是8；
   2. HashMap长度大于64

5.3 HashMap初始化时为什么要给自定义的初始容量？