HashMap|put方法解析

public class TestHashMap {
    public static void main(String[] args) {
        HashMap<Object, Object> hashMap = new HashMap<>();
        hashMap.put("a", "a");
    }
}

直接点进put方法内，看到实则调用putVal方法

1
2
3

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

putVal方法

思考

就算不看源码之前，自己想一下该怎么往哈希桶中插入一些值（首先肯定要了解HashMap的基本结构的啊！）：

先根据一些算法找到你要插入元素在哈希桶中的位置。
找到这个位置之后判断一下这个位置是否为空，为空则直接插入，执行完毕。
如果不为空则，看一下你要插入的是否和这个元素的key相等，相等则替换值即可。
否则肯定是判断这个结点的下一个是否为空，为空的话，说明这个哈希桶中不是链表就是红黑树。
先判断一下它是否为树，如果为树，按照红黑树的方式插入元素。
否则为链表则遍历该链表啊，看是不是和你的值冲突，如果冲突就替换，否则在链表最后插入即可。

这个过程很简单，实际上除了TreeNode类中有关的那些方法，其它的实现都相对简单。那个TreeNode要对红黑树特别了解才能理解明白。上述的几个步骤中就是其中缺少了对于扩容的一些处理，对于链表每次要是插入一个元素就应该考虑是否扩容，是否树化。所以在第6步骤插入元素后需要考虑这些。（替换则不需要考虑了啊）

源码中的实现大概思想是这样，但存在许多细节。这里随便列举几个：

首先这个一个元素到底存放在哈希桶中哪个位置，这个算法具体怎么实现的？？

如果达到扩容阈值，扩容之后那哈希桶中的元素该怎么重新分配（这个是在resize扩容方法中处理的）？？？

还可以得出一个问题就是为什么HashMap的长度要是2的幂次方（这个和1和2问题有关）？

…

后面都会详细解释这些问题、

源码解读

看putVal方法之前要明白一个元素是怎么确定在table数组中的位置的。

(n- 1) & hash

n为table的长度，hash为可以的hash并且这个hash并不是直接取key的哈希而是经过hash这个扰动函数让hash更加分散

static final int hash(Object key) { // 返回这个你传入的键的hash值
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // 让hash的高16位与低16位异或，更分散，扰动函数，让哈希更分散；这里还说明了如果你的key为空则放在哈希桶的0位置处
    }

(n- 1) & hash到底是什么意思？

这个含义是hash % n的意思。

首先hashMap的长度规定为2的次幂，那么长度的2进制必然为前面一个1后面全是0，比如8是1000，4是0100。

那么这个2进制减去1是多少，比如8的二进制-1 ：1000 - 1 = 0111 原来为1的位变0后面全部为1。

然后和hash进行与操作，&操作只有在全是1的情况下才为1，可以看出来了吧，这个n-1&hash 无论hash的高位多么的花里胡哨的全给我变成0，只保留后面的几位，如果hash>n-1 的话就是求余操作，否则就是hash这个值。

这你也就明白了HashMap的长度为什么是2的次幂了吧。这个在resize方法中也有体现后续会说明。

参数含义

key的哈希值
key
value
是否覆盖原来旧的值，就是HashMap中存在与你这个key相同的，false覆盖，true不覆盖
evict，如果为false，则处于创建模式（无特殊含义，在HashMap的一个构造函数中传过来的是false）。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0) // 判断当前的table是否为空
            n = (tab = resize()).length; // resize()方法中初始化table，并将初始化后的长度赋值给n
        if ((p = tab[i = (n - 1) & hash]) == null) // 判断元素要插入的位置的那个哈希桶是否为null，(n - 1) & hash 意思是求出该元素在hash桶中的下标
            tab[i] = newNode(hash, key, value, null); // 为空说明这个哈希桶还未有其他元素，直接填入这个位置即可
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))) // 判断你插入元素是否和p冲突（p为哈希桶的第一个元素，冲突的意思就是hash相同key的equals为true）
                e = p; // 将p赋值为e这个Node结点
            else if (p instanceof TreeNode) // 如果这个哈希桶中已经是个红黑树
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 红黑树的putTreeVal来插入这个元素，返回旧的结点如果有冲突的话，并赋值给e
            else { // 为链表结点
                for (int binCount = 0; ; ++binCount) { // 遍历链表
                    if ((e = p.next) == null) { // 判断p的下一个结点是否为空，这个为空的意思就是已经遍历到链表的最后一个结点了。。
                        p.next = newNode(hash, key, value, null); // 遍历完全部的链表都没发现链表中与你要插入的结点冲突，直接new一个结点插入到链表的尾部即可
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 因为你插入了一个元素就需要判断一下你这个插入后的长度是不是超过了建树的阈值，TREEIFY_THRESHOLD默认为8
                            treeifyBin(tab, hash); // 这个是将这个链表树化的操作
                        break; // 跳出循环
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k)))) // 发现与你要插入的元素冲突的元素
                        break; // 跳出循环
                    p = e; // 这个就是每次都将p设置为e = p.next，p的下一个结点
                }
            }
            if (e != null) { // existing mapping for key 经过上面那些操作这个e保存的就是与你冲突的那个节点
                V oldValue = e.value; // 将e结点的value赋值给oldValue
                if (!onlyIfAbsent || oldValue == null) // onlyIfAbsent：是否替换旧值（put方法传入的是false替换），或者e的value为空满足其一则替换
                    e.value = value; // 将新值替换为这个节点的值
                afterNodeAccess(e); // HashMap中为空函数并没有实际含义（LinkedHashMap使用）
                return oldValue; // 返回旧值，因为是替换操作没有新增加结点，所以无需考虑扩容问题，直接返回即可。
            }
        }
        ++modCount; // 修改的次数+1
        if (++size > threshold) // 插入元素后判断是否超过扩容阈值
            resize(); // 超过扩容阈值进行扩容操作
        afterNodeInsertion(evict); // HashMap中为空函数并没有实际含义（LinkedHashMap使用）
        return null; // 新增加了节点，并没有替换，所以返回null
    }

确定元素在哈希桶中的位置：

小结

这个过程和自己想的过程一样吗，就是它插入时利用了一个中间变量e来记录与我key值相同的结点，如果这个e不为空则说明要覆盖这个结点，然后根据onlyIfAbsent这个参数，注意这个若这个e的value为null也进行覆盖！！覆盖之后就返回原来旧的value。

如果e为空，则判断是否需要扩容了，然后返回null。

resize方法

思考

不看源码之前自己现想一下让你实现扩容怎么实现（这个比较难想得出来！！）：

简单的思考一下，既然是扩容方法，肯定是要确定一下新的table容量，扩容阈值threshold肯定也需要重新设定一下子啊，不设定这个容量>扩容阈值不得每次都扩容吗。可得出第一个步骤就是求出新的table容量和相应的扩容阈值threshold。具体新的table是原来容量的多少倍肯定看源码才明白，现在明白新的table长度肯定是原来的2的幂次方的倍数。！
第1步中既然得到了扩容阈值和新容量，现在肯定要new一个新的table出来，然后把原来的table拷贝到这个新的table中。再细化一下，肯定是遍历原来的table然后判断哈希桶的根中是否存在数据存在数据则说明不是链表就是树，分别对链表和树进行相关处理，如果为空则跳过判断下一个了。
第2步拷贝到新的table完成后自然就返回这个新的table即可！！

如果只知道resize看表面来说是扩容方法，但是它还有一层含义就是初始化HashMap这个职责。这个我是肯定想不到，设计者思考的。

这个第2个步骤中对链表的处理，你想一下该怎么处理，现在的table是原来的2倍，链表该怎么移动？？后续给出答案！

源码解读

final Node<K,V>[] resize() { // hashMap的初始化、扩容方法
        Node<K,V>[] oldTab = table; // 将table赋值给oldTab
        int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取table的长度
        int oldThr = threshold; // 将扩容阈值赋值给oldThr
        int newCap, newThr = 0; // 新的容量 和 新的扩容阈值
        if (oldCap > 0) { // 这里的意思就是你这个table已经初始化过了，并不是第一次使用这个hashMap
            if (oldCap >= MAXIMUM_CAPACITY) { // 如果你的旧容量大于默认的最大容量
                threshold = Integer.MAX_VALUE; // 将扩容阈值直接设置为int的最大值，就是再也不用考虑扩容
                return oldTab; // 直接返回即可
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY) // 将旧容量扩大2倍后赋值给新容量，如果小于默认的最大值 并且旧容量要大于默认的容量16
                newThr = oldThr << 1; // double threshold 就将旧容量扩大2倍然后直接赋值给新的扩容阈值
        }
        else if (oldThr > 0) // 这里说明你是自己指定了这个hashMap的长度
            newCap = oldThr; // 你如果是通过有参数构造函数传过来的话，就是将hashMap的table长度赋值给了threshold，然后这里初始化的时候才真正的赋值给真正的容量
        else {               // 你并没有指定任何的初始值，也就是用的无参构造函数
            newCap = DEFAULT_INITIAL_CAPACITY; // 将容量直接设置为默认即可
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 负载因子设置为(默认容量 x 负载因子 -> 16 x 0.75)
        }
        if (newThr == 0) { // 新的扩容阈值为0 这说明你是自己指定的hashMap容量，需要设置一下这个扩容阈值
            float ft = (float)newCap * loadFactor; // 上面已经求出了新的hashMap容量，新的容量 x 负载因子 就是扩容阈值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? // 这里是判断你这个新的容量小于hashMap的默认最大值，并且新的阈值也要小于
                      (int)ft : Integer.MAX_VALUE); // 都满足的话新的扩容阈值直接设置为求出来的即可，否则设置为int最大值，以后无需考虑扩容
        }
        threshold = newThr; // 将计算出来的扩容阈值赋值给threshold即可；从这往上所做的操作就是得到 newCap 和 newThr这两个值
        @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 根据新容量设置一个新的Node数组
        table = newTab; // 将新的table数组赋值给table
        if (oldTab != null) { // 如果旧的长度不为空，这个才会考虑将原来旧的数据转移到新创建的中Node数组中，否则你执行的只是hashMap的初始化操作没必要拷贝啊！！
            for (int j = 0; j < oldCap; ++j) { // for循环遍历旧的Node数组
                Node<K,V> e;
                if ((e = oldTab[j]) != null) { // 如果hash桶的根不为空，则说明这个桶中存在数据，否则为空无需操作
                    oldTab[j] = null; // 将旧的数据设置为空，释放空间，因为旧的桶已经不用了
                    if (e.next == null) // 如果这个根结点的下一个结点为空则说明只有这一个数据
                        newTab[e.hash & (newCap - 1)] = e; // 直接在新的Node数组中找出一个位置填进去即可。找的方法还是和原来一样 e.hash & (newCap - 1)
                    else if (e instanceof TreeNode) // 这个桶中的数据已经变成了树了
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 拆了这个树
                    else { // 这个哈希桶为链表，这里操作巧妙，见后续详解，注释无法全部说明，先看后续详解再看注释比较好！！！
                        Node<K,V> loHead = null, loTail = null; // 定义 旧的位置的头结点，旧的位置尾结点
                        Node<K,V> hiHead = null, hiTail = null; // 定义 新的位置的头结点，新的位置尾结点
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { // (e.hash & oldCap) == 0 只要满足这个条件就是在原位置的链表
                                if (loTail == null) // 这几步的操作就是构建这个旧的位置的链表
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else { // 否则就是在 旧容量 + 原来的下标的位置上
                                if (hiTail == null) // 这几步的操作就是构建这个新的位置的链表
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) { // 旧位置下的链表头不为空
                            loTail.next = null;
                            newTab[j] = loHead; // 将链表头填入哈希桶的根处
                        }
                        if (hiTail != null) { // 新位置下的链表头不为空
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead; // 将链表头填入哈希桶的根处
                        }
                    }
                }
            }
        }
        return newTab; // 返回这个新的Node数组
    }