HashMap源码解析

Hash数据结构设计

为什么HashMap的capacity是2的整数次幂?
JDK1.8相对于1.7改进了什么?
HashMap在多线程情况下会发生什么?

散列函数

Java中把每个对象散列成一个整数的方法是hashCode(),这个方法是从Object而来的。
默认的是通过对象的内存地址来。所以几乎是唯一的,不会产生碰撞的。
但是我们也可以自己选择重写这个方法。
不过我们在重写hashCode方法时,别忘了也要重写equals方法。
要保证hashCodeequals方法的行为一致。
也就是说equalstrue时,hashCode必然时相等的。
equalsfalse时,hashCode可以相等也可以不相等。

碰撞冲突

如果两个键的hashCode相同,那就是产生了碰撞。
有很多方法解决碰撞,常见的是拉链法和线性探测法。

拉链法

就是开一个Node的数组,然后每个元素指向一个链表。
但hash值相同时,就存在对应的元素的单链表中。
实现也较为简单。

借助这个再解释下hashCodeequals方法。
hashCode产生的值用来寻找数组的索引,但是可能产生碰撞,于是equals方法就用来便利单链表找到相等的键。

线性探测法

就是开一个Node数组,如果hash值相同,那么找下一个空位。
怎么找下一个空位呢。
最简单的就是每次+1,当然你也可以约定+2,+3。。。

HashMap源码解析

HashMap用的是拉链法,但是1.8中还增加了改进。
我们约定前面的数组的每一格称为桶
约定桶后面存放的每一个数据称为bin

1.8中补充了红黑树,如果一个桶的bin数大于8,那么就把这个桶的链表转换为红黑树。

Map

声明

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

HashMap继承自AbstractMap, 实现了Map接口的方法。

1
public abstract class AbstractMap<K,V> implements Map<K,V>

AbstractMap同样实现了Map接口的方法。
很多人可能奇怪为什么HashMap为什么不直接实现Map接口就好,中间要多个AbstractMap类呢。
因为类库开发者考虑到有些人可能要实现自己的Map类,为了给降低他们的开发难度,于是开发了AbstractMap类。
这样我们如果要实现自己的Map类,就继承AbstractMap类就好了。

Map接口的所有方法如下,其中有很多default方法,是Java8的新特性。
有兴趣的可以百度一下。这里就不赘述了。

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
public interface Map<K,V> {

//Map具有特征的方法,看名字就大概就能猜到用处
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
//Entry见下
Set<Map.Entry<K, V>> entrySet();

//来自Object的方法
boolean equals(Object o);
int hashCode();

//底层的数据单位Entry
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
//来自Object
boolean equals(Object o);
int hashCode();

//key的比较,lambda表达式还能这么用。。。
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}

//value的比较
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}

//自定义key的比较
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}

//自定义value的比较
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}


//给定一个key获取value,同时指定一个default值,如果不存在就返回default值
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}

//对Map中每个键值对进行指定的action操作
//这个方法会抛出异常如果在遍历过程中某个Entry被删除了
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}

//把所有的value进行重新赋值,也会抛出异常
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}

// ise thrown from function is not a cme.
v = function.apply(k, v);

try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}

//如果key不存在,则put进去
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}

return v;
}

//移除一个键值对,同时必须键值对都相等
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}

//替换一个key的value,同时oldvalue要和之前的value相等
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}

//也是替换一个key的value,但是不要求当前的value为何值
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}

//如果map中不存在key,则根据key通过mappingFuction得到一个value并放进去
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}

return v;
}

//如果map中存在key,则根据key和oldvalue通过remappingFuction得到一个value并放入
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}

//这个有点复杂,根据oldvalue(可能不存在)和key通过remappingFunction得到一个newValue
//如果newValue不为null,则置换或者增加这个key,newValue
//如果newValue为null,如果old也不为null,就把这个key移除出去
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);

V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}

//这个也有点复杂
//如果不存在这个键值对,就把key,value存进去
//如果存在,则根据oldvalue和value通过remappingFunction得到一个newvalue,如果newvalue为null,则把这个key移除,否则就存进去
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}

Map的大概就是这些,我们主要了解了一些通用的default方法,通过lambda表达式可以很方便的做一些事。
还有就是Map内部有一个Entry的接口,一个Entry,就是一个键值对。

AbstractMap

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
public abstract class AbstractMap<K,V> implements Map<K,V> {

//key,value主要是存在这个entrySet中
public abstract Set<Entry<K,V>> entrySet();

//这里两个主要是为了得到所有的key集合或者value集合而设计的
transient Set<K> keySet;
transient Collection<V> values;

private static boolean eq(Object o1, Object o2) {
return o1 == null ? o2 == null : o1.equals(o2);
}

//AbstractMap中有Entry的两个实现
//其中之一是SimpleEntry
public static class SimpleEntry<K,V>
implements Entry<K,V>, java.io.Serializable {

private final K key;
private V value;

//省略一些正常的构造函数和getter和setter

//equals的实现是比较key和value是否相等
//其中eq函数是对Object的equals的封装,里面考虑了null的情况
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return eq(key, e.getKey()) && eq(value, e.getValue());
}

//hashCode()方法是对两个对象的hashCode求异或
public int hashCode() {
return (key == null ? 0 : key.hashCode()) ^
(value == null ? 0 : value.hashCode());
}
}

//第二个是SimpleImmutableEntry
public static class SimpleImmutableEntry<K,V>
implements Entry<K,V>, java.io.Serializable {

//可以看到key和value都是final的,所以自然没有setValue的方法,但是其实还是有的
private final K key;
private final V value;
//setValue方法抛出一个异常
public V setValue(V value) {
throw new UnsupportedOperationException();
}
//其他的和SimpleEntry的一样
}

//返回一个key的Set,这里使用了懒加载,只有在第一次调用的时候才会初始化keySet
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new AbstractSet<K>() {
public Iterator<K> iterator() {
return new Iterator<K>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public K next() {
return i.next().getKey();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object k) {
return AbstractMap.this.containsKey(k);
}
};
//因为是懒加载,所以加载完之后还要再赋给keySet
keySet = ks;
}
return ks;
}

//返回value的值集合,同样也是懒加载
public Collection<V> values() {
Collection<V> vals = values;
if (vals == null) {
vals = new AbstractCollection<V>() {
public Iterator<V> iterator() {
return new Iterator<V>() {
private Iterator<Entry<K,V>> i = entrySet().iterator();
public boolean hasNext() {
return i.hasNext();
}
public V next() {
return i.next().getValue();
}
public void remove() {
i.remove();
}
};
}
public int size() {
return AbstractMap.this.size();
}
public boolean isEmpty() {
return AbstractMap.this.isEmpty();
}
public void clear() {
AbstractMap.this.clear();
}
public boolean contains(Object v) {
return AbstractMap.this.containsValue(v);
}
};
values = vals;
}
return vals;
}

//返回entry的大小
public int size() {
return entrySet().size();
}

//这个主要要注意是允许存放null值的,也是可以搜索null值的
public boolean containsValue(Object value) {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (value==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getValue()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (value.equals(e.getValue()))
return true;
}
}
return false;
}


//同时key也是可以是null的
public boolean containsKey(Object key) {
Iterator<Map.Entry<K,V>> i = entrySet().iterator();
if (key==null) {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
return true;
}
} else {
while (i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
return true;
}
}
return false;
}

//get方法和上面的大同小异,,分为是null或者不是两种情况
public V get(Object key);


//remove方法。。。嗯,,,好像也没什么好解释的,,看看就懂了
public V remove(Object key) {
Iterator<Entry<K,V>> i = entrySet().iterator();
Entry<K,V> correctEntry = null;
if (key==null) {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (e.getKey()==null)
correctEntry = e;
}
} else {
while (correctEntry==null && i.hasNext()) {
Entry<K,V> e = i.next();
if (key.equals(e.getKey()))
correctEntry = e;
}
}

V oldValue = null;
if (correctEntry !=null) {
oldValue = correctEntry.getValue();
i.remove();
}
return oldValue;
}

//hashCode是把所有的Entry的hashCode加起来
public int hashCode() {
int h = 0;
Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext())
h += i.next().hashCode();
return h;
}
//这个toString写的很有意思,给人很有启发。。。主要是实现的比较优雅。。
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
if (! i.hasNext())
return "{}";
StringBuilder sb = new StringBuilder();
sb.append('{');
for (;;) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
sb.append(key == this ? "(this Map)" : key);
sb.append('=');
sb.append(value == this ? "(this Map)" : value);
if (! i.hasNext())
return sb.append('}').toString();
sb.append(',').append(' ');
}
}

HashMap

重头戏来了。。
前面说过jdk1.7以前的HashMap的bin就是一个单链表,但是到了1.8的时候进行了改进。
如果一个桶中的bin数量大于8并且当前的capacity大于64时,那么就会变成一颗红黑树。

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {


//约定前面的数组的每一格称为桶
//约定桶后面存放的每一个数据称为bin

//默认的桶的数量大小,写成这样不是直接写16是因为强调要是2的倍数
//为什么呢,往下看
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;


//最大的桶的数量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的负载,就是已有size/capacity,当达到这个值时,会进行resize,下面会提到
static final float DEFAULT_LOAD_FACTOR = 0.75f;


//如果一个桶中的bin数量大于8,那么就变成红黑树,但是还有个条件见下
static final int TREEIFY_THRESHOLD = 8;

//同上一个相反,当桶上的链表数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;

//数化的还有一个条件是当哈希表中的容量大于这个值时,否则即使大于8,也不会树化。
static final int MIN_TREEIFY_CAPACITY = 64;

//一些系统的参数
//系统的负载因子
final float loadFactor;

//threshold表示当HashMap的size大于threshold时会执行resize操作。
//threshold=capacity*loadFactor
int threshold;


//这个table是开地址法的数组,相当于桶
transient Node<K,V>[] table;
//放节点的Set
transient Set<Map.Entry<K,V>> entrySet;
//目前有多少对map
transient int size;

//当前的HashMap被修改了多少次。
//还记得ConcurrentModificationException么
//这个在使用Iterator时,会判断当前的modCount和使用时是否相等
//如果不相等,那么就抛出异常。
transient int modCount;



//先来看看构造函数
//第一个什么也没有,就是上面的值都是默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//第二个可以指定初始的容量的大小,它调用了第三个构造函数。
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//第三个构造函数主要对值进行了检查
//如果传进去的大小小于0,那就抛出一个异常,如果大于最大值,就设为最大值。
//但是loadFactor也进行了检查,不知道为什么,我好像没有看到一个方法可以对loadFactor进行修改。
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;

//还记得最开始说的容量最好是2的倍数吗?这里我们传一个数进去,它会找到最接近我们数的2的倍数作为容量。而不是就把我们的数作为容量了。具体函数见下
this.threshold = tableSizeFor(initialCapacity);
}

//找到最接近cap的2的倍数的数
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//先来看看resize函数吧,这个是核心
final Node<K,V>[] resize() {
//先拿到当前数组桶的索引
Node<K,V>[] oldTab = table;
//得到旧的table的长度,考虑到还没初始化,所以把null值作为0处理
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的bin的阀值
int oldThr = threshold;
int newCap, newThr = 0;

//如果oldCap大于0,大概就是已经初始化过了。
if (oldCap > 0) {
//如果已经达到最大值,就直接返回了,不可以在resize了。
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//不然看看把oldCap乘2,如果还没大于1 << 30,就是默认的最大的桶数
//则新的cap的值就是就的值乘2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
//不然新的桶的数量就是旧的阀值
newCap = oldThr;
else {
//如果以上两个条件都不满足,那么newCap就是默认的值16,新的阀值就是12.
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的阀值为0
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

//直接new一个新的具有newCap大小的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//= =这里为什么不直接和上面的合成一句话呢。。。。
table = newTab;
//下面就是把旧的table里的bin全部转移到新的table中
//其实很多文章说HashMap的put操作会造成死循环
//但是在1.8中进行了改进,所以下面这段代码在多线程环境中不会造成死循环
//旧的有个很好的文件进行解释,见下

if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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) {
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;
}

//下面先来看看最常用的put函数,调用了putVal函数
public V put(K key, V value) {
//对于这儿的hash()函数,其实还是挺有意思的,作者觉得原来的容易产生
//碰撞,所以把前16位和后16为进行了异或。。。
return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

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;
//这里就是为什么capacity取2的整数次幂的原因了
//正常我们找index的时候都是hash % length,但是用到了除法
//如果2的整数次幂,那么hash % length = (length - 1) & hash,用的是位运算
//对于计算机来说位运算的效率更高。
if ((p = tab[i = (n - 1) & hash]) == null)
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))))
e = p;
//如果是树节点
else if (p instanceof TreeNode)
e = ((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);
//如果大于8,进行进入treeifyBin函数,并不就是直接进行树化,因为还有一个条件。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}

//看看get方法,调用了getNode方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
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 TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}


//下面看看树的操作。
//在HashMap中Entry的实现有两个
//第一个就是单链表的Node
static class Node<K,V> implements Map.Entry<K,V>;
//第二个是树的Node,TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>;
//关于红黑树的原理,这里就不赘述了。。。完整说起来又是一遍长篇大论。

//将一个桶中的节点树化的函数
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果桶的大小小于64,进行的是resize而不是树化。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}

//简单看一看TreeNode的定义。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//还有指向父节点的指针。
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
}

HashMap死循环

我们要知道死循环的原因是链表产生了回路。
1.8之前产生回路的原因是换table时把原先的单链表每个节点放到了链表开头。
就是说比如旧table[0]中 1 -> 2 -> 3
在resize时,新的table[0]中变成 3 -> 2 -> 1

但是在1.8中不在这样,而是规规矩矩的还是1 -> 2 -> 3