1.8HashMap源码解析之put与get方法

put方法

    在看put方法，可以先看看之间将的构造方法源码解析：1.8HashMap源码解析之构造方法
    put方法上来调用了putval方法，把key的哈希值(注意这个hash值计算方法)，key以及value等信息传递给了putval方法。

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

    先来看看这个key的hash值是怎么计算出来的，通过hashCode方法得到的哈希值无符号左移了16位之后异或了原来的hash值，这样做是为了减少hash冲突，让结点比较均匀的分布。

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

    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;
   /* hashmap属于是懒加载，并不是在构造方法里面直接对node数组赋值，
   而是在put第一个结点的时候创建*/
   // 如果node的数组长度为0，就会进入到第一个if中
   if ((tab = table) == null || (n = tab.length) == 0)
       /* 调用resize()方法来创建node数组，将node数组的引用赋值给tab，
       将node数组的长度赋值给n*/
       // 这个resize()方法其实就是扩容方法，将创建Node数组的逻辑也放在了resize()方法中
       n = (tab = resize()).length;
   // 如果node数组创建出来，并且对应位置的值为空，则直接占有tab中对应位置，如下图(a)所示    
   /* 这里可以发现，hash值对应的下标时，不是用取余运算，而是将得到的hash值与node数组的
   长度进行与运算，得到下标，提高了计算效率*/
   if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);
   /* 如果下标已经被某个node结点占用了，就会进行这个else中，
   就比如如图(b)的第三个结点已经被k1,v1占用，就会进入这个else中*/
   else {
       Node<K,V> e; K k;
       // 注意，此时的p已经在上一个if中被赋值了，指向了第一个(k1,v1)这个结点。
       /* 所以这个if用来判断key的hash值和对应的key内容是否相同，如果都相同，
       说明是修改这个key对应的value值，但是并没有直接修改，而是将这个p的值赋值给了e*/
       if (p.hash == hash &&
           ((k = p.key) == key || (key != null && key.equals(k))))
           e = p;
       /* 这个else if就用用来判断这个node所对应的这个链是不是已经树化了，
       如果树化了，走树化插入结点的逻辑。*/
       else if (p instanceof TreeNode)
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
       // 这个结点对应的是链表，不是树，并且key和第一个node的key不同时，就会进入这个else
       else {
       	   /* 用图(b)来说明，首先将e赋值给p的next，就是(k2,v2)，显然这个e指向了(k2,v2)，
       	   肯定不为null,进入下一个if，判断这个k2和用户传递古来的key是否相同，相同，
       	   直接跳出循环，此时p指向了需要修改的结点；如果不相同，将p指向(k2,v2)，继续循环，
       	   进入第一个if，将e指向了p的next，就是null,进入第一个if直接创建了一个
       	   新的node结点插入到最后。还判断了这个链表的长度是否大于8，如果大于8，
       	   调用treeifBin转化为红黑树*/
           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;
           }
       }
       /* onlyIfAbsent这个参数如果为true，表示新的value不能替换旧的value，
       如果为false就可以替换。上述如果key值相同，只是将e指向对应的node结点，
       到这个if进行了修改。*/
       if (e != null) {
           V oldValue = e.value;
           if (!onlyIfAbsent || oldValue == null)
               e.value = value;
           afterNodeAccess(e);
           return oldValue;
       }
   }
   ++modCount;
   // 如果size超过了扩容容量，就会触发resize进行扩容
   if (++size > threshold)
       resize();
   // afterNodeAccess和afterNodeInsertion就是一个空方法，用于扩展业务逻辑使用
   afterNodeInsertion(evict);
   return null;
}

node数组创建时resize方法调用的语句

    node数组属于懒加载，调用resize进行创建，这个resize也是扩容的逻辑，下面对node创建时走的resize中的语句进行说明。

// 调用这个resize后，会进入这个else中，如果调用的是空参构造方法，则newCap会被赋值为16，newThr被会赋值为16*0.75=12.
else {
	newCap = DEFAULT_INITIAL_CAPACITY;
	newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 将12赋值给成员变量threshold 
threshold = newThr;
// 创建大小为16的node数组，并返回
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

afterNodeAccess与afterNodeInsertion的源码展示

void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

get方法

    get方法上来就调用了getNode方法来获取value，getNode方法传递了key的hash，key和value等参数。

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

    getNode方法代码不是很多，下面一点一点来看。

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    /* 最外层if判断node数组不能为空，
    并且对应hash值的node链表第一个结点不能为空*/
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 如果第一个结点就是需要找的结点，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /* 第一个结点如果不是需要找的结点，
        就使用一个指针不断地遍历整个链表，这个指针就是e*/
        if ((e = first.next) != null) {
            // 判断node如果不是链，而是树，则走遍历树的逻辑
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);       
            /* 不是树，就是链表，则用e不断地遍历链表所有结点，
            直到找到对应地结点并返回或者遍历到链表末尾，e为null停止*/
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}