HashMap底层分析

1. 调用HashMap的put方法 (内部调用了putVal()、hash()两个方法)

2. 执行hash函数，将计算出来的hash值传入putVal方法中

3. 执行putVal方法 （对着源码 和 这个流程图验证以下，就很容易看懂了。最好是，看着源码自己画一遍流程图）

4.执行完putVal后，我们的key-value就插入成功了 （执行完后，会return一个value值，如果key以存在，就会return已存在key对应的value值。如果key不存在，则返回null）

调用HashMap的put方法时，put方法会先调用hash函数计算hash值，然后传给putVal方法。并调用putVal方法对key-value进行后续处理。

//当两个结点的key相同，则新节点的value会覆盖旧结点的value，并且会将旧的value返回
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

hash函数是用来计算hash值，hash值在我们存取或这移除结点时，用来确定索引位置的。

static final int hash(Object key) {
    int h;
    //如果key为null，则返回0，反之则返回key的hash值(key的hashCode值与key的hashCode值的高16位进行^异或运算得到的值)
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Node结点对象，每当我们put入key-value时，都会先添加到Node结点对象中，然后再存储到Node[]数组中。HashMap的主干数组中存的就是一个个Node结点。

static class Node implements Map.Entry {
    final int hash;  //hash值
    final K key;     //key
    V value;         //value
    Node next;  //指向下一个结点的next指针，(这是个单向链表，所以只有next指针，没有pre指针)

    Node(int hash, K key, V value, Node next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //Node数组       //p结点指向链表头节点    //数组长度，索引
    Node[] tab; Node p; int n, i;
    
    // 数组未初始化或者长度为0，进行扩容
    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);
        
    // 桶中已经存在元素 ： p(指向链表头节点)
    else {
        Node e; K k;
        // 比较桶中第一个元素p与要插入元素的key是否相等，key相等则此次put为覆盖操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 将第一个元素赋值给e，用e来记录
            e = p;
            
       // key不相等且头节点p为红黑树结点，则此次put为向红黑树中插入节点
        else if (p instanceof TreeNode)
        	//将节点添加到红黑树上
            e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            
        // key不相等；头节点p为链表结点，则此次put为向链表中插入节点（树化发生在此处）
        else {
        	//遍历链表，有两种情况下才会跳出循环
            for (int binCount = 0; ; ++binCount) {
            
            	//第一种：已经遍历到尾部,在尾部插入新结点跳出。（因节点数量+1 判断是否需要树化）
            	
                if ((e = p.next) == null) {
                	//在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    //判断是否需要树化
                    
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    	//并且数组长度>=64，则链表就会树形化(这些会在treeifyBin()方法中实现)
                        treeifyBin(tab, hash);
                    //跳出循环
                    break;
                }
                
                // 第二种：e指向的节点与要插入节点的key相同，此次put为覆盖操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    //跳出循环
                    break;
                //用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        //如果新节点不为空
        if (e != null) { // existing mapping for key
        	//记录e的value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            	//用新值替换旧值
                e.value = value;
            afterNodeAccess(e);
            //返回旧值
            return oldValue;
        }
    }
    ++modCount;
    //添加新结点后，要判断数组的使用长度，如果达到临界值，那么数组就会扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}