HashMap源码解读——逐句分析get和put方法的实现

一、前言

  最近在研究HashMap的源码，经过这几天的研究，我对HashMap的底层实现有了一个比较清晰的认识。今天就来写一篇博客，带大家阅读一下HashMap中，最最重要的两个方法——get和put的代码实现。（注：以下代码基于JDK1.8）

  若想要看懂这两个方法的源代码，首先得对HashMap的底层结构有一个清晰的认识，若不清楚的，可以看看我之前写的一篇博客，这篇博客对HashMap的底层结构和实现进行了一个比较清晰和全面的讲解，同时博客的最底下附上了两篇阿里架构师对HashMap的分析，写的非常好，很有参考价值：

• Hexo链接 —— HashMap源码解读——深入理解HashMap高效的原因

• 博客园链接 —— https://www.cnblogs.com/tuyang1129/p/12362959.html

二、解析

 2.1 get方法源码解读

  get方法的作用是传入我们需要获取的节点的key，然后将这个节点的value返回。首先先贴上get方法的代码：

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

  可以看到，get方法的代码非常的简洁，因为具体的代码都封装在了getNode这个方法里面，get方法只是对它进行了调用。getNode方法接收两个参数，第一个参数是key的hash值，第二个参数就是key本身。下面我们就来看看getNode方法的源代码（通过注释，对源码进行了逐句解读）：

/**
 * Implements Map.get and related methods
 *
 * @param hash key到hash值
 * @param key key值
 * @return the node, or null if none
 */
final HashMap.Node<K,V> getNode(int hash, Object key) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;

    // 以下if语句中判断三个条件：
    //   1、HashMap中存储数据的数组table不为null；
    //   2、数组table不为null，且长度大于0；
    //   3、table已经创建，且通过hash值计算出的节点存放位置有节点存在；
    // 若上面三个条件都满足，才表示HashMap中可能有我们需要获取的元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {

        // 定位到元素在数组中的位置后，我们开始沿着这个位置的链表或者树开始遍历寻找
        // 注：JDK1.8之前，HashMap的实现是数组+链表，到1.8开始变成数组+链表+红黑树

        // 首先判断这个位置的第一个节点的key值是否与参数的key值相等，
        // 若相等，则这个节点就是我们要找的节点，将其返回
        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 HashMap.TreeNode)
                return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
            // 若不是一个树节点，表示当前位置是一个链表，则使用do...while循环遍历查找
            do {
                // 若查找到某个节点的key值与参数的key值相等，则表示它就是我们要找的节点，将其返回
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 若没有找到对应的节点，返回null
    return null;
}

  在HashMap中，containsKey方法也是依赖getNode方法实现的：

public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

 2.2 put方法源码解读

  看完了get方法的源代码，我们再来看看put方法。put方法的作用是将一对key-value插入到HashMap中，若HashMap中已经存在这个key，则用新的value替换旧的value。

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

  可以看到，put方法比get方法还要简短，和get方法一样，他也是将实现放入了另一个方法中，这个方法叫做putVal。我们先来看看这个方法的签名：

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

 这个方法有5个参数：

1. hash：需要插入的元素，它的key的hash值；
2. key：需要插入的元素的key值；
3. value：需要插入的元素的value值；
4. onlyIfAbsent：一个标识，当它的值为false时，若查询重复的key值，则将用新的value替换原来的value；反之则不替换，留下旧值；
5. evict：在HashMap中无意义，将在子类LinkedHashMap中使用；

  除了上面五个参数，在putVal中还用来另外成员变量，我们要先明确它们的意义：

1. TREEIFY_THRESHOLD：将链表转换成红黑树的阈值；在HashMap中，若某一条链表上的节点数大于等于TREEIFY_THRESHOLD，那就会将它从链表转换成红黑树，这个值默认为8；
2. modCount：记录HashMap被修改的次数，这里的修改仅仅是指插入和删除；这个变量的作用是为了安全的使用迭代器：迭代器在创建时，会记录下这个值，若迭代器在使用的过程中，modCount与迭代器中记录的值不一致，表示在迭代器被创建后，集合的元素数量发生了改变，这个时候迭代器就不再安全了，此时再使用这个迭代器时将会抛出异常；
3. size：HashMap中，节点的数量；
4. threshold：HashMap中，当前允许放入的最大节点数，当到达这个数量时，HashMap将进行扩容；

  好了，下面我们就来看看putVal方法的源代码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;

    // 判断当前存储数据的数组是否为null，或者大小为0，若是，则调用resize方法初始化数组
    // resize方法用来初始化HashMap中存储数据的table数组，或者给table扩容（即*2）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;

    // 判断新值将要插入的位置是否为null，若为null，则用传入的值创建一个新的节点，并放入到这个位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 若新值将要放入的位置已经存在节点了，则进一步判断
    else {
        // 若已经存在一个节点，它的key与新值的key相等，则用变量e记录这个节点
        // e的作用就是干这个的，下面很长一段代码都是用来判断是否存在这样一个节点
        HashMap.Node<K,V> e; K k;
        // 若新值将要插入的位置已经存在的节点，它的key值与新值的key相等，
        // 则用变量e记录下它
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 若已经存在的节点是一个Tree节点，则使用树的方法将节点加入
        // 用e接收返回值，此处返回值e不为空，表示这棵树上存在与新值的key相同的节点
        else if (p instanceof HashMap.TreeNode)
            e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 若以上条件均不满足，则表示这个位置不是一棵树，而是一个链表
        else {
            // 遍历这个链表
            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;
                }
                // 若在遍历这条链表的过程中，发现了一个节点，它的key值与新值的key相等，则不插入新节点
                // 且此时由于上面的操作，e已经指向了这个key重复的节点，不需要继续遍历了，跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 这一步赋值没看懂意义何在
                p = e;
            }
        }

        // 判断e是否为null，若不为空，表示在原来的节点中，存在一个key值与新值的key重复的节点
        if (e != null) { // existing mapping for key
            // 记录下这个节点原来的value值
            V oldValue = e.value;
            // 若onlyIfAbsent的值为false，或者原来的value是null，则用新值替换原来的值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 这是一个回调函数，但是在HashMap中是一个空函数，
            // 看源码貌似是留给LinkedHashMap去扩充的，
            // 感觉这个应该属于模板方法设计模式
            afterNodeAccess(e);
            // 返回旧value，如果在这里被返回，则不会执行剩下的代码
            // 也就是说，若执行到剩下的代码，表示并不是执行修改原有值的操作，而是插入了新节点
            return oldValue;
        }
    }
    // 能运行到这里，表示这次进行的是插入操作，而不是修改
    // modCount用来记录Map（仅指插入+删除）被修改的次数
    // 此处modCount+1，因为HashMap被修改了（新插入了一个节点）
    ++modCount;
    // Map中元素的数量+1，并判断元素数量是否到达允许的最大值，若到达，则对Map进行扩容
    if (++size > threshold)
        resize();
    // 与上面的afterNodeAccess类似，同为留给LinkedHashMap编写的回调函数
    afterNodeInsertion(evict);
    // 若插入一个新节点，则返回null
    return null;
}

三、总结

  为了能够更好的理解，上面的代码我都进行了非常详细的注释，希望对看到这篇博客的人能够有所帮助。因为我对红黑树不是很了解，所以在上面的两个方法中，关于树的操作那部分我都没有深入探讨，之后有时间，我会去专门研究一下红黑树，比较这是在集合中，使用的比较多的一个数据结构。

四、参考

https://blog.csdn.net/qq_35321596/article/details/81117669
https://blog.csdn.net/AJ1101/article/details/79413939