JDK1.8 HashMap源码分析(二)

上一篇文章介绍了HashMap中的一些常量含义、构造方法以及扰动算法，这篇文章会分析HashMap中的核心方法get()、put()，第一遍读可能稍微有点模糊，多看几遍就很容易懂了。

一、成员变量

阅读get()和put()方法之前先需要了解一下HashMap中的成员变量。

/**
 * 存放元素的Node数组
 */
transient Node<K,V>[] table;

/**
 * 记录当前元素个数
 */
transient int size;

/**
 * 被修改次数
 */
transient int modCount;

/**
 * 下一次的扩容阈值
 */
int threshold;

/**
 * 当前负载因子
 */
final float loadFactor;

二、put()

源码中会有大量的赋值语句在if块中，这个需要习惯，方法内会使用局部变量存放成员变量的值，我也会提前标注好每个变量的含义。put()方法重点关注的地方有resize()方法、(n - 1) & hash为什么能代替模运算计算出下标、什么时候扩容、什么时候链表树化。

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

/**
 * hash: key的hash值
 * key: 目标元素key
 * value: 目标元素value
 * onlyIfAbsent: 是否覆盖已有元素，true不覆盖，false覆盖
 * evict: 暂时不用管，这个是给LinkedHashMap用的
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    /**
     * tab: 当前map中的Node数组
     * i: 根据key的hash计算出来的下标
     * n: 数组长度
     * p: 下标为i的元素
     */
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // HashMap是懒惰初始化,会在第一次put时初始化数组,这里如果talbe为null或长度为0时会进入resize()方法进行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 初始化后返回数组长度赋值给n,resize()后面讲
        n = (tab = resize()).length;
    /**
      * (n - 1) & hash这个与运算操作是计算出key存放的数组下标，按常理来讲我们使用hash去映射数组存放的下标
      * 是用hash % length完成的，但是这里特殊的地方是数组的长度一定是2的整数次幂
      * 演示长度为16的情况,length - 1 = 15 -> 0000 1111
      * 假设hash值为35(实际不会是35) 0000 0000 0000 0000 0000 0000 0010 0011
      * 那么与运算即为 0000 0000 0000 0000 0000 0000 0010 0011 & 0000 0000 0000 0000 0000 0000 0000 1111
      * 结果为 0000 0000 0000 0000 0000 0000 0000 0011 = 3，和35 % 16得到的结果是一样的
      * 所以这里使用位运算代替模运算提高效率
      * 仅在length为2的整数次幂时才能使用这种方式，这也是使用tableSizeFor()方法的意义
      */
    // 当这个下标位置的元素为null时可以直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        /**
         * e: 遍历时用的变量，如果key已存在则表示该元素
         * k: 链表中元素的key
         */
        Node<K,V> e; K k;
        // 先验证第一个元素的key是否和传入的key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 如果相等这里把第一个元素赋值给e,然后结束
            e = p;
        // 判断数组中的元素是否为红黑树节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 不是红黑树则是链表,这里遍历链表寻找key是否已存在
            // binCount表示下标
            for (int binCount = 0; ; ++binCount) {
                // 遍历到下一个元素是null时则说明key不存在,可以直接插入
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 插入后判断是否达到树化条件 binCount >= 7,即元素个数到达8时会进入treeifyBin()树化
                    // binCount >= 7只是其中一个条件，treeifyBin()里面还会再判断一次，后面讲
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果key存在,e表示当前key的元素，直接跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // e不为空时说明key是已存在的
        if (e != null) {
            V oldValue = e.value;
            // onlyIfAbsent为false或者key对应的value为null时会覆盖已有元素的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 这个方法不用管，是给LinkedHashMap用的
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 修改次数+1
    ++modCount;
    // size+1判断是否大于扩容阈值,如果是则进入resize()中进行扩容
    if (++size > threshold)
        resize();
    // 这个方法不用管，是给LinkedHashMap用的
    afterNodeInsertion(evict);
    return null;
}

关于resize()方法比较复杂，下一篇文章单独拉出来看，这里可以得出一些结论

• key是可以为null的，put()方法中全程没有限制key为null的情况，但只能有一个元素为null
• 桶位中链表进入树化方法的条件之一是链表中元素个数 大于等于 8
• 数组扩容条件之一是数组中的元素个数 大于 扩容阈值

三、get()

get()方法比较简单，读懂put()后应该没什么问题。

/**
 * 把key和key的扰动hash值传入getNode得到结果
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
    /**
     * tab: 当前map中的Node数组
     * first: 数组首元素
     * n: 数组长度
     * k: 需要查找的元素key
     */ 
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // (tab = table) != null && (n = tab.length) > 0 表示只有在数组已经初始化并且有元素的情况才继续判断，否则直接返回null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        // 这里获得下标后找出对应的元素,如果为null也不用继续走下去,不为null时继续去寻找
        (first = tab[(n - 1) & hash]) != null) {
        // 判断首个元素是否为目标key,如果是则返回
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        /**
         * 如果数组中的首个元素不是目标key，则继续走下面的逻辑
         * 1. 判断下一个节点是否为红黑树节点,如果是则走红黑树的查找逻辑,这里就不展开了,因为这又是一个大块
         * 2. 如果不是红黑树则只能为链表，所以开始遍历链表查找目标key，这里遍历的逻辑我就不讲了，这个太简单了
         * 不明白的话可以去leetcode刷几个链表的题目就会了。
         */
        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;
}