jdk13 HashMap中put方法源码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
import java.util.HashMap.Node;
import java.util.HashMap.TreeNode;
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* 在这个map中将指定的value与指定的key联系起来，如果map事先已经包含了这个key
* 那么老的value会被取代。
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
*
{@code null} if there was no mapping for {@code key}.
*
(A {@code null} return can also indicate that the map
*
previously associated {@code null} with {@code key}.)
*
* 这个方法返回的是在前与这个key联系在一起的value，或者是null，当没有value与这个key联系
* 在一起时。返回空值也能表明这个key实现与一个空值联系。
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower.
Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.)
So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*
* 计算key.hashCode（）并将哈希的较高位扩展（XOR）到较低位。 因为该表使用2的幂次掩码，
* 所以仅在当前掩码上方的位中变化的哈希集将始终发生冲突。 （众所周知的示例是在小表中保存连续
* 整数的Float键集。）因此，我们应用了一种将向下扩展较高位的影响的变换。 在速度，实用性和
* 位扩展质量之间需要权衡。 由于许多常见的哈希集已经合理分布（因此无法从扩展中受益），并且由
* 于我们使用树来处理容器中的大量冲突集，因此我们仅以最便宜的方式对一些移位后的位进行XOR，
* 以减少系统损失， 以及合并最高位的影响，否则由于表范围的限制，这些位将永远不会在索引计算中
* 使用。
* 事实上我不懂上面这一段说的什么。。。，说的应该就是为什么要用下面这种算法的理由吧
* 这个方法就是说的是给定一个key，试怎么算出它的hash值的。
*
*
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* Returns a hash code for an {@code int} value; compatible with
* {@code Integer.hashCode()}.、
* 这个是Integer的hashcode（）方法
*
*
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for an {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
/**
* 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
* 如果onlyIfAbsent为true的话，不改变已经存在的值
* @param evict if false, the table is in creation mode.
* evict如果是false的话，table是创建模式
* @return previous value, or null if none
*/
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)
n = (tab = resize()).length;
//如果table是空，或者table的长度为空，就resize，
/*
* 关于resize
* Initializes or doubles table size.
If null, allocates
* in accord with initial capacity target held in field
* threshold. Otherwise, because we are using power-of-two
* expansion, the elements from each bin must either stay
* at same index, or move with a power of two offset in
* the new table.
*
* 初始化或增加表大小。 如果为空，则根据字段阈值中保持的初始容量目标进行分配。 否则，
* 因为我们使用的是2的幂，所以每个bin中的元素必须保持相同的索引，或者在新表中以2
* 的幂偏移。
*
* */
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//tab[i = (n - 1) & hash]这一块就是根据key的hash值与table的长度减一
//进行运算，得到要放入的table桶序号，如果这个桶中没有节点，则直接放入桶的第一个位置
else {
//如果得到的tab【i】是有节点的
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果传入的hash与p的hash一样，传入的key与p的key一样，则把p赋给e（为什么这么做）
//这么做是因为如果做了这个赋值，下面的elseif和else就不用执行了，而后面是在e上操作的，
//所以把p赋给e，相当于找到了这个节点，用e表示这个节点，p是辅助节点。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果hash和key不一样，检查p（这个桶最开头的节点）是不是treenode，是的话按照treenode
//的规则插入新节点
else {
//桶一样，hash和key不一样，不是tree节点，那就从p开始遍历
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;
}
//上面这个是检查是否遍历到了最后一个，如果是的话就在最后一个后面插入
//再检查bincount计数器是否大于等于7，是的话就转成红黑树并跳出for
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//如果再遍历过程中遇到一个hash和key都相等的节点，就跳出
p = e;
//这是让p等于p.next 相当于让p后移一个
}
}
//经过上面的代码，要么已经插入完成（桶一样，hash和key不一样，是tree节点就用tree节点
//的方法插入了，不是tree节点就遍历到了这个桶的最后，在桶的最后插入了，这两种情况下e都为null），
//要么是找到了key一样的节点(可能是桶的第一个节点一样，或者是不是树节点，在遍历中途找到了key
//一样的节点），并把它指向了e。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
//上面是在已经存在这个key的情况下，根据onlyifabsent 判断是否修改value的值。
//并返回旧的value,在修改了value的值后，这儿为啥没有modCount++呢？
}
}
++modCount;	//为了实现fast-file机制
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}