看过 Java 8 HashMap 源码的知道底层数据结构是数组、链表和红黑树实现的，从Debug调试或者序列化输出的都是K,V值，没法直观的看到上述的数据结构，为了直观的看到数据结构存储方面的变化，本文通过动图演示HashMap的结构变化。
为了简单看出链表到红黑树的变化，定义一个方便控制的key来演示效果。
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
| public class Key implements Comparable<Key>{
private final int hash;
private final int value;
public Key(int hash, int value) {
this.hash = hash;
this.value = value;
}
@Override
public int compareTo(Key o) {
return (value < o.value) ? -1 : ((value == o.value) ? 0 : 1);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Key key = (Key) o;
if (hash != key.hash) return false;
return value == key.value;
}
@Override
public int hashCode() {
return hash;
}
}
|
上面通过 hashCode 直接返回 hash 简单控制值落在数组中的位置，重写的 equals 中通过不同的 value 值保证为不同的 Key，通过 compareTo 比较 value 值，让红黑树可以更直观的展示。
通过下面代码创建一个 hash = 0，value自增的 Key：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public static void main(String[] args) throws Exception {
HashMap<Key, Integer> map = new HashMap<>();
int valueSize = 20;
for (int i = 0; i < valueSize; i++) {
clearScreen();
System.out.println("---------------------------------------------");
printTableLength("table.length before put: ", map);
map.put(new Key(0, i), i);
printTableLength("table.length after put : ", map);
print(map);
}
}
|
通过 clearScreen() 实现 CMD 清屏的效果，通过 printTableLength("table.length before put: ", map); 打印 HashMap 中 Node<K,V>[] table 数组的长度，当调整长度 resize 时，就会产生变化。通过 print(map) 输出 HashMap 的结构。上述代码执行过程中的关键输出如下：
1
2
3
4
5
6
7
8
9
10
| ---------------------------------------------
table.length before put: 0
table.length after put : 16
table[0] printmap.MapTest$Key@0 -> 0
---------------------------------------------
table.length before put: 16
table.length after put : 16
table[0] printmap.MapTest$Key@0 -> 0 -> 1
---------------------------------------------
省略...
|
下面开始，当链表长度超过8时，会转换树，转换树时会判断 table数组的长度是否超过64，由于此时长度为16，会先通过 resize 扩容来避免hash冲突。
链表长度10的时候，由于数据大小32，会先resize扩容，所以就出现了链表长度为 10 的特殊情况。
1
2
3
4
5
6
7
8
| ---------------------------------------------
table.length before put: 16
table.length after put : 32
table[0] printmap.MapTest$Key@0 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
---------------------------------------------
table.length before put: 32
table.length after put : 64
table[0] printmap.MapTest$Key@0 -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
|
等到下一次的时候，链表长度超过8，数组到了64，链表就转换为了红黑树（树形结构中B为黑，R为红）。
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
| ---------------------------------------------
table.length before put: 64
table.length after put : 64
table[0] printmap.MapTest$Key@0
│ ┌── R:10
│ ┌── B:9
│ │ └── R:8
│ ┌── R:7
│ │ └── B:6
│ ┌── B:5
│ │ └── B:4
└── B:3
│ ┌── B:2
└── B:1
└── B:0
---------------------------------------------
省略...
---------------------------------------------
table.length before put: 64
table.length after put : 64
table[0] printmap.MapTest$Key@0
│ ┌── R:18
│ ┌── B:17
│ │ └── R:16
│ ┌── R:15
│ │ └── B:14
│ ┌── B:13
│ │ └── B:12
│ ┌── R:11
│ │ │ ┌── B:10
│ │ └── B:9
│ │ └── B:8
└── B:7
│ ┌── B:6
│ ┌── B:5
│ │ └── B:4
└── R:3
│ ┌── B:2
└── B:1
└── B:0
|
上图是最终状态的树。下面的动图为完整的慢速执行过程：
想要源码吗？ 捐赠留下邮箱稍后即可收到。