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;
        // 如果说桶（也就是数组，以下都用"桶"代替）为空，或者桶大小为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);
        else {
        // 运行到这说明定位的位置已经有元素了
            Node<K,V> e; K k;
        // 既然有人霸占元素的位置，那么就要与该元素进行对比，看看自己的Hash值和
        // key值是不是和该位置的元素一直，如果都一直就记录下该元素以下为e
        // 说明有一个和我插入元素的key一样的元素 后续可能要用新值替换旧值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        // 如果只是Hash值相等而key不等，这里就是Hash碰撞啦，要解决hash碰撞
        // hashMap采用的是链地址法 就是碰撞的元素连成一个链表 这里由于链表
        // 如果太长就会树化成红黑树，以下是判断p也就是桶里放的是不是红黑树
            else if (p instanceof TreeNode)
        // 是红黑树 我们就把节点放入红黑树 注意：这里也不是一定插入到树中，
        // 因为如果我们要插入的元素和红黑树中某个节点的key相同的话，也会考虑
                // 新值换旧值的问题
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
        // 跳到这 说明p不是树，而是链表 binCount用来记录链表中元素的个数，那么
        // 为啥要记录链表中元素的个数呢？主要判断链表是否需要树化成红黑树
                for (int binCount = 0; ; ++binCount) {
                    // e的后一个节点为空 那么直接挂上我们要插入的元素
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // TREEIFY_THRESHOLD 是树化的阈值且其值为8
                        // 这里要注意：我们要插入的节点p是还没有加到binCount中的
                        // 也就是说这里虽然binCount>=7就可以树化，其实真正的树化
                        // 条件是链表中元素个数大于等于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;
                    p = e;
                }
            }
            // 说明找到了key相同的元素
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // 判断是否需要旧值换新值，默认情况下是允许更换的
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 这个方法点进去就是个空方法，主要是为了给继承HashMap的
                // LinkedHashMap服务的
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改次数+1
        ++modCount;
        // 看下达到扩容的阀值没
        if (++size > threshold)
        // 扩容 ，在本方法的前面需要初始化的时候也出现过
            resize();
         // 这个方法同样也是为LinkedHashMap服务的
        afterNodeInsertion(evict);
        // 没找到元素 就返回空
        return null;
    }

   final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 桶不为空 并且桶的元素大于0 同时定位的位置元素还不为空 那就顺藤摸瓜
        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;
            if ((e = first.next) != null) {
            // 第一个元素不是我们要找的，而且后面还接着元素 判断一下是不是树
                if (first instanceof TreeNode)
                    // 是树 按照树的获取节点方法去获取
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 到这说明是链表了 那就按照链表的方式去循环
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

 // 初始容量1向左移动4位为16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 // 最大容量1向左移30位
 static final int MAXIMUM_CAPACITY = 1 << 30;
 // 加载因子 也就是桶大小使用要是超过0.75 那么就要考虑扩容了
 static final float DEFAULT_LOAD_FACTOR = 0.75f; 
 //  链表太长 要变树的阀值
 static final int TREEIFY_THRESHOLD = 8;
 // 树变成链表的阀值
 static final int UNTREEIFY_THRESHOLD = 6;
  // TREEIFY_THRESHOLD达到8也不一定树化，还要容量达到64
 static final int MIN_TREEIFY_CAPACITY = 64;