思路
1.7与1.8方法的比较
put方法大致流程—》put方法时下标位置元素为空（1.7、1.8）—》不为空
1.7 HashMap采用的是数据+链表
1.8 HashMap采用的是数组+链表+红黑树
大致流程
根据key通过哈希算法与运算得出数据下标。
下标位置元素为空
将key和value封装成Entry对象（1.7中是Entry对象，1.8中采用Node对象），并放入该位置
下标位置不为空
1.7
先判断是否需要扩容，如果需要则先进行扩容，如果不用就生成Entry对象，并使用头插法添加到当前位置的链表中。
1.8
先判断当前位置上的Node类型，看是红黑树Node还是链表Node
如果是红黑树Node，则将key和value封装成一个红黑树节点添加到红黑树中，在这个过程中判断红黑树中是否存在当前key，如果存在则更新value
如果此位置上的Node对象是链表节点，则将key和value封装成一个链表Node并通过尾插法插入到链表的最后位置，因为是尾插法，所以需要遍历链表，在遍历链表的过程中判断是否存在当前key，如果存在则更新value，当遍历完链表之后，将新链表Node插入后链表中，插入链表后，会看当前链表的个数，如果大于等于8，那么就会将链表转换成红黑树
将key和value封装位Node插入到链表或红黑树中后，再判断是否需要进行扩容，如果需要就扩容，如果不需要就结束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
73final Node<K,V>[] resize() { //数据扩容方法
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
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;
}
...
...
00:00
00:00
Copyright 2021 sunfy.top ALL Rights Reserved