【腾讯文档】hashmap的put过程思维导图

https://docs.qq.com/mind/DWEZDTHlvdmNDVmxY

【腾讯文档】HashMap扩容思维导图

https://docs.qq.com/mind/DWE5nWm5YZ1lFZUdD

下面是具体源码过程：

1. put(K key, V value)

1. hash(Object key)：通过key的高16位和低16位的异或操作获取hash值

2. putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

1. node table没有初始化时：resize()，以默认容量16初始化数组

2. (p = tab[i = (n - 1) & hash]) == null 当没有hash冲突时直接把node节点放入tab中

3. 有hash冲突

1. p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))当是同一个key时覆盖旧key的value

2. p instanceof TreeNode当是树节点时，把new node放到红黑树中

3. 否则就是单向链表，for (int binCount = 0; ; ++binCount)，遍历单链表

1. (e = p.next) == null当遍历到链表的最后一个元素时把新元素挂到尾部，binCount >= TREEIFY_THRESHOLD - 1 treeifyBin(tab, hash)同时检查链表长度是否超过8，超过则转成红黑树

2. if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))每次遍历时都会判断key是否一样，一样则结束遍历，然后覆盖旧value

4. if (e != null)table中具有同样的key，则覆盖旧value，并返回旧value

5. ++modCount;这个跟之前讲的集合一样，主要是防止你在遍历集合时对集合put和remove操作

6. ++size > threshold，判断是否需要扩容threshold = table容量*加载因子

3. resize() 扩容

1. oldCap > 0， newCap = oldCap << 1，newThr = oldThr << 1;除了之前的table初始化，正常新的table容量是旧table容量的两倍，扩容阈值也是原来的2倍

2. threshold = newThr;扩容阈值也是原来阈值的2倍

3. oldTab != null，for (int j = 0; j < oldCap; ++j)，当旧table不为空时进行元素迁移

4. if ((e = oldTab[j]) != null)，j位置有元素时进行遍历j位置上的元素进行元素迁移

1. e.next == null，j位置元素没有hash冲突则用e.hash & (newCap - 1)定位新tab的位置放入

2. e instanceof TreeNode，split(this, newTab, j, oldCap)如果是红黑树则遍历树进行元素迁移，for (TreeNode<K,V> e = b, next;e != null; e = next)遍历红黑树

1. (e.hash & bit) == 0如果e的hash跟旧tab容量与的结果是0说明跟新数组e.hash & (newCap - 1)操作时位置结果还是index位置(e.prev = loTail) == nullloHead = e说明此时链表还是空的，此时e是头节点，否则 loTail.next = e;在尾部放入e，此时loTail = e;e就是新的尾部

2. 否则(e.hash & bit) ！= 0如果e的hash跟旧tab容量与的结果不是0说明跟新数组e.hash & (newCap - 1)操作时位置结果不是index位置，而是 bit+index，此时就需要挪动(e.prev = hiTail) == nullhiHead= e说明此时链表还是空的，此时e是头节点，否则hiTail.next = e;在尾部放入e，此时hiTail= e;e就是新的尾部

3. loHead != null不需要挪动位置的元素存在时

1. lc <= UNTREEIFY_THRESHOLD，loHead.untreeify(map)如果少于六个元素，则变为链表并放到新数组的index位置。loHead.treeify(tab);否则维护红黑树，并放到新数组的index位置

2. lc <= UNTREEIFY_THRESHOLD，loHead.untreeify(map)如果少于六个元素，则变为链表并放到新数组的index + bit位置。loHead.treeify(tab);否则维护红黑树，并放到新数组的index + bit位置

4. 
   

3. 否则就是单向链表，do{}while()遍历单向链表

1. (e.hash & oldCap) == 0，如果e的hash跟旧tab容量与的结果是0说明跟新数组，e.hash & (newCap - 1)操作时位置结果还是j位置，loTail == null，loHead = e，说明不需要挪动的链表还是空的，此时e是头节点，否则loTail.next = e;在尾部放入e，此时loTail = e;e就是新的尾部

2. 否则(e.hash & oldCap) != 0，如果e的hash跟旧tab容量与的结果不是0说明跟新数组，e.hash & (newCap - 1)操作时位置结果不是j位置，而是 j+oldCap，此时就需要挪动hiTail == null，hiHead= e，说明此时需要挪动还是空的，此时e是头节点，否则hiTail.next = e;在尾部放入e，此时hiTail= e;e就是新的尾部

3. loTail!= null不需要挪动位置的元素存在时

1. loTail.next = null;newTab[j] = loHead;把链表放入新数组的j位置

4. hiTail != null需要挪动位置的元素存在时

1.  hiTail.next = null;newTab[j + oldCap] = hiHead;把链表放到新数组的j + oldCap位置

对整个过程中的一些总结：

1. 整个put过程是按没有hash冲突，有hash冲突两个大流程来分的，当有hash冲突时通过instanceof来判断是否是TreeNode的对象（这个是我们可以借鉴的地方，在我们实际开发中可能也会判断某个对象是否是某个类的对象）。

2. 在进行tab扩容时不管是TreeNode还是单向链表，都是先生成两个单向链表：一个不需要挪动位置的链表，一个是需要挪动位置的链表，是TreeNode时再通过判断链表的长度来判断是否需要维护红黑树。而且这个地方巧妙的利用的tab扩容是旧tab的2倍，而且tab的容量是2的倍数这个特性，在判断是否需要挪动元素使用的是(e.hash & oldCap) == 0这个方式，而没有使用e.hash & (newCap - 1)这种方式，这个扩容特性确定了不需要挪动的元素就在j位置，需要挪动的元素是j+oldCap,这样也就不需要像1.8之前使用头插法了。

3. 巧妙的程序设计总是能事半功倍的，在日常开发中多想想程序设计的合理性，这可能就是拉开你和别人差距的一种方式