通过本章内容来给大家解读hashMap中put()方法的逻辑流程。
目录：
- put()方法流程图
- put()方法代码解读
- 单元测试代码
- put方法
- hash()方法
- putVal()方法
- resize()扩容方法
1、put()方法的流程图
2、put()方法-代码解读
2.1、单元测试代码
1 public class HashMapTest {
2
3 public static void main(String[] args) {
4 Map<String, String> hashMap = new HashMap<>();
5 hashMap.put(null, "null");
6 hashMap.put("key0", "value0");
7 hashMap.put("key1", "value1");
8 System.out.println(hashMap);
9 }
10 }
2.2、put()方法
/**
* put()方法：向table数组中添加元素
*
* hash(key)：计算key的hash值，
* putVal(): 向table[]添加元素
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
2.3、hash()方法
1 /**
2 *
3 * 在jdk1.8是优化后的降低冲突概率的hash算法
4 */
5 static final int hash(Object key) {
6 int h;
7 /**
8 * 1、如果HashMap的key==null，则计算后的hash值=0
9 * 2、如果HashMap的key不等于null，则：
10 * 2.1、获取int类型的key的hashCode值
11 * 2.2、将hashCode值无符号右移16位
12 * 2.3、把key的hashCode值与无符号右移后的数字做异或操作；异或：俩值相等=0，俩值不等=1
13 * 3、根据key取完hashCode值后为什么要无符号右移16位，又为什么要做异或运算？
14 * 因为无符号右移和异或运算后得到的数字包含了 hashCode二进制值的高位和低位特征的，当hashmap容量较少时大大降低了 put时数组index寻址的冲突概率；
15 * 也即：异或运算其实是将 hashCode的16个低位和16个高位做异或运算，最后结果得出hash值和数组容量做与操作来寻址降低数组index冲突
16 * 否则只拿hashCode去数组index寻址的话，有可能存在hashCode二进制值高位16位做运算时用不到，增加了数组index冲突的概率；
17 * 4、举例子：
18 * 第一步 hashCode值： 0000 0000 0011 0010 0010 1101 1011 0001 328849（key0的hashcode值）
19 * 第二步 无符号右移16位： 0000 0000 0000 0000 0000 0000 0011 0010 50（hashcode无符号右移16位）
20 * 第三步 把hashCode值和右移后的数组做异或运算： 0000 0000 0011 0010 0010 1101 1000 0011 3288451（异或运算后的值）
21 *
22 *
23 */
24 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
25 }
2.4、putVal()方法
1 /**
2 * Implements Map.put and related methods
3 *
4 * @param hash hash for key （key的hash值）
5 * @param key the key （key）
6 * @param value the value to put （value值）
7 * @param onlyIfAbsent if true, don't change existing value （当key冲突时，是否覆盖原有的值，这里时false，表示不会被覆盖）
8 * @param evict if false, the table is in creation mode.
9 * @return previous value, or null if none。（返回key所在index处的上一个值）
10 */
11 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
12 boolean evict) {
13 Node<K,V>[] tab; Node<K,V> p; int n, i;
14 if ((tab = table) == null || (n = tab.length) == 0)
15 // 1、当第一次添加元素时进入
16 // 首次触发Node数组扩容为16， 之后将扩容后HashMap的Node数组长度赋值临时变量n
17 n = (tab = resize()).length;
18 // 2、HashMap数组寻址
19 /**
20 * (n - 1) & hash]: 与运算，运算效果与取取模一致，计算机与运算效率要比取模高；
21 * 这里为什么要用 n-1？ 当 n-1和2的n次方做"与运算"时为什么能达取末运算的效果？这里与运算的计算方式和取末方式有什么联系？
22 *
23 * 因为：当计算机对比取末时，与运算会更快，所以为了提高计算效率，HashMap采用与运算的方式来达到和数字取模一致的效果；
24 * 为达到此目的，HashMap中规定了table数组容量必须是2的n次方，而 2^n-1 转换为二进制就是n个连续的1（从低位开始n个连续的1），
25 * 进而 hash值 & (n个连续的1) 就是拿n个hash低位与n个1做与计算，最后该计算结果就是(0～2^n-1)的数字，即0～length-1的数字 自然就获取到了数组index索引。
26 * 与运算（&）：两数为真则结果为真，否则结果为假。（都是1时则结果为1，否则结果为0）。
27 */
28 // 这里也说明了做hash取值时为什么要先无符号右移16位和做异或运算，因为当数组容量比较少时做与运算会出现只和低位做运算，高位运算结果全部是0
29 if ((p = tab[i = (n - 1) & hash]) == null)
30 // 寻址完成后，检查若index位置上的元素==null，则直接创建新Node放到数组的指定index处
31 tab[i] = newNode(hash, key, value, null);
32 else {
33 // 寻址完成后，检查若发现指定index处已经有元素了，会有三种情况处理：
34 // 名次解释：p=hash表中index处已存在的老元素
35 // 第一种情况：检查老元素和新元素的hash值以及key值相等时，则直接做相同key的值覆盖；老元素的value值丢弃；
36 // 第二种情况：检查index处的元素是个红黑树结构，则在红黑树中做添加处理；
37 // 第三种情况：第一种和第二种情况都不满足，则index处的元素做链表处理，新元素挂载到老元素的next处；
38 Node<K,V> e; K k;
39 if (p.hash == hash &&
40 ((k = p.key) == key || (key != null && key.equals(k))))
41 // 第一种情况，当新元素和老元素hash值和key值都想等时，将老元素赋值给变量e，在下一步做Node value值的覆盖
42 e = p;
43 else if (p instanceof TreeNode)
44 // 第二种情况，检查index处的元素若是红黑树结构，则根据红黑树结构去添加新元素
45 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
46 else {
47 // 第三种情况，若元素hash值和key值既不想等，index处的元素也不是红黑树结构，那么就是链表结构（或者index处的元素只有一个，添加新元素时要升级为单向链表结构）
48 for (int binCount = 0; ; ++binCount) {
49 // 没有上限的for循环遍历（相当于while循环），靠条件break；
50 // 将index处Node p的next属性上的元素赋值给Node e，并校验是否为空（意为：是否有下个Node元素），当第一次index冲突时，p.next是等于空的
51 if ((e = p.next) == null) {
52 // 若遍历到链表的尾节点，则创建新的Node插入到链表的尾节点上
53 p.next = newNode(hash, key, value, null);
54 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
55 // 检查若binCount>=7，那么链表长度等于9时，p=第八个Node节点，binCount才会等于7，
56 // 因为for循环是从第二个Node开始遍历的，binCount遍历初始值是0，而新创建的节点都是当前节点的next，此处是先创建节点后校验链表长度，所以实际当链表长度=9时才会转变为红黑树
57 // 这时才会将单向链表结构升级为红黑树结构
58 treeifyBin(tab, hash);
59 // 元素添加完成，跳出for循环
60 break;
61 }
62 // 检查 单向链表上的每个Node的hash值和key是否与当前要添加的新元素对应的值相等，
63 // 若相等则跳出for循环，在下一步做相同key的value值覆盖，当前要添加的元素也就添加完成了；
64 if (e.hash == hash &&
65 ((k = e.key) == key || (key != null && key.equals(k))))
66 break;
67 // 将next属性上的Node实例赋值给变量p，继续for循环（next.next上的Node元素）
68 // p指向的是链表的第二个Node元素...第三个元素...；（就实现了链表的单向遍历）
69 p = e;
70 }
71 }
72 // 作用：相同key的value值覆盖
73 // 主要是处理：根据上面的逻辑来看 只有在hash表中找出新元素与旧元素的hash值和key相等时，Node e才不等于null，才会做value值覆盖的操作
74 // 也就是说： 当链表中存在hash值和key与新元素相等时，只需要将新元素value值覆盖旧元素value值即可，就实现了新元素的put操作
75 if (e != null) { // existing mapping for key
76 V oldValue = e.value;
77 if (!onlyIfAbsent || oldValue == null)
78 e.value = value;
79 afterNodeAccess(e);
80 return oldValue;
81 }
82 }
83 // 记录修改次数++
84 ++modCount;
85 // 检查如果元素数量+1后大于扩容阈值则触发resize()扩容
86 if (++size > threshold)
87 resize();
88 afterNodeInsertion(evict);
89 return null;
90 }
2.5、resize()扩容方法
1 /**
2 * Initializes or doubles table size. If null, allocates in
3 * accord with initial capacity target held in field threshold.
4 * Otherwise, because we are using power-of-two expansion, the
5 * elements from each bin must either stay at same index, or move
6 * with a power of two offset in the new table.
7 *
8 * hash表数组扩容
9 * @return the table
10 */
11 final Node<K,V>[] resize() {
12 // 获取hash表数组
13 Node<K,V>[] oldTab = table;
14 // 获取hash表容量和hash表扩容阀值
15 int oldCap = (oldTab == null) ? 0 : oldTab.length;
16 int oldThr = threshold;
17 // 定义新hash表的容量和扩容阀值
18 int newCap, newThr = 0;
19 if (oldCap > 0) {
20 // 首先处理数组容量大于2^30的情况；
21 // 若hash表数组容量大于最大值（2的30次方），那么将扩容阀值增加为integer的最大值
22 if (oldCap >= MAXIMUM_CAPACITY) {
23 threshold = Integer.MAX_VALUE;
24 return oldTab;
25 }
26 // 其次在合理的范围内实现数组扩容
27 // hash表数组容量和阀值都扩大到原来的2倍
28 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
29 oldCap >= DEFAULT_INITIAL_CAPACITY)
30 newThr = oldThr << 1; // double threshold
31 }
32 else if (oldThr > 0) // initial capacity was placed in threshold
33 newCap = oldThr;
34 else { // zero initial threshold signifies using defaults
35
36 // 向HashMap首次添加元素时进入
37 // 将初始容量大小16作为首次扩容后的容量大小
38 // 并计算扩容阀值为12
39 newCap = DEFAULT_INITIAL_CAPACITY;
40 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
41 }
42 if (newThr == 0) {
43 float ft = (float)newCap * loadFactor;
44 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
45 (int)ft : Integer.MAX_VALUE);
46 }
47 // 新的扩容阀值赋值到全局变量
48 // 接着创建一个新的扩容后的hash表数组，赋值到全局变量
49 threshold = newThr;
50 @SuppressWarnings({"rawtypes","unchecked"})
51 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
52 table = newTab;
53
54 // rehash，对hash表中旧元素重新寻址
55 // 对hash表的数组上的元素一个一个遍历，分为三种情况遍历：
56 // 第一种情况：index处只有一个元素
57 // 第二种情况：index处是一个链表
58 // 第三种情况：index处是一个红黑树
59 if (oldTab != null) {
60 for (int j = 0; j < oldCap; ++j) {
61 Node<K,V> e;
62 if ((e = oldTab[j]) != null) {
63 // 获取并操作旧hash表中每个元素
64 oldTab[j] = null;
65 if (e.next == null)
66 // 第一种情况：index处只有一个元素；
67 // 处理办法：直接对index处的元素重新寻址
68 newTab[e.hash & (newCap - 1)] = e;
69 else if (e instanceof TreeNode)
70 // 第三种情况：index处是一个红黑树
71 // 此处当红黑树Node小于等于6时会触发 红黑树转链表的行为
72 // 处理办法：
73 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
74 else { // preserve order
75 // 第二种情况：index处是一个链表
76 // 处理办法：遍历链表上的Node重新寻址；
77 // 新index只会有两种情况：1⃣️ Node新index还是在原位置可能形成新链表；2⃣️ Node新index位置= 原index+oldCap并可能形成链表；
78 Node<K,V> loHead = null, loTail = null;
79 Node<K,V> hiHead = null, hiTail = null;
80 Node<K,V> next;
81 do {
82 next = e.next;
83
84 // 当前if如果成立，则说明，当前链表上当前Node节点在新数组中index和老数组index一致
85 // 将这些index上的Node组成一个新的链表
86 if ((e.hash & oldCap) == 0) {
87 if (loTail == null)
88 loHead = e;
89 else
90 loTail.next = e;
91 loTail = e;
92 }
93 // 若走了如下else分支，则说明：当前链表上当前Node节点在新数组中index= Node在老数组中的index + 老数组的容量
94 // 将这些index上的Node组成一个新的链表
95 else {
96 if (hiTail == null)
97 hiHead = e;
98 else
99 hiTail.next = e;
100 hiTail = e;
101 }
102 } while ((e = next) != null);
103
104 if (loTail != null) {
105 loTail.next = null;
106 newTab[j] = loHead;
107 }
108 if (hiTail != null) {
109 hiTail.next = null;
110 newTab[j + oldCap] = hiHead;
111 }
112 }
113 }
114 }
115 }
116 return newTab;
117 }
标签：Node,index,Jdk1.8,hash,HashMap,链表,key,put,null From： https://www.cnblogs.com/routine/p/17196815.html