前言
本篇博客涉及以下几个内容：
- HashMap的部分源码讲解
- 红黑树的数据结构
HashMap的结构和源码
Java中集合一共可以分为两类，一类是Collection，代表是ArrayList；一类是Map，代表是HashMap。而HashMap存储结构是哈希表。
哈希表
哈希表的本质是一个数组，但是性能比数组高很多，因为动态数组的插入和删除操作对应的时间复杂度是O(n)，而哈希表的增删改查操作时间复杂度均为O(1)。
为什么快？
哈希表利用函数映射的方式来将数据映射到其维护的数组上，这样执行增删改查操作时只需要通过这个函数就能找到数组的下标，从而实现快速定位。相比数组的顺序存储，哈希表是无序的，因此在执行删除操作时，并不需要移动其他下标的元素。用来执行元素映射的函数叫做哈希函数：hashcode()。
存储方式如下图：
哈希冲突
由上述的存储方式可知，如果两个不同元素通过哈希函数的值相同，则单纯用数组存储就会有冲突。这种方法最直接的解决办法就是设计优秀的哈希函数，把冲突的可能性降至最低，但是再优秀的哈希函数，都会有可能发生冲突。因此，需要有一种方法来解决冲突问题。
常见的方法有：
- 线性探测法，发生冲突后顺序找下一块空的地址。（运气差的话增删改查都会变O(n)）
- 对冲突的地址使用另一个Hash函数
- 链地址法：数组的每个位置都存一个链表。（运气差的话，查找会变O(n)）
HashMap解决冲突的办法就是链地址法，数组的每个位置我们称之为桶。如果运气不好的话，所有的数字都在一个桶里，那么查找一个链表的时间复杂度是O(n)，这很低效。所以JDK8之后，当一个桶里存放的元素超过8个时，则这个桶里会自动变成红黑树，这样查找的效率就成了O(logn)。
HashMap的实现原理
HashMap主干数组
1
2
|
transient Node<K,V>[] table;
|
Node<K,V>是HashMap的一个静态内部类(使用静态内部类是为了方便继承，TreeNode就继承了这个Node类)，源码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
|
其存储结构如下图：
当数组中某个桶存储的元素超过一定的数量后(默认是8个)，则Node会被转化为TreeNode进行存储，TreeNode继承自LinkedHashMap.Entry<K,V>，关于LinkedHashMap可以移步我的博客：浅谈Java中LinkedHashMap，TreeNode的解析将在下文的红黑树种讲解。
几个重要字段
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
static final int UNTREEIFY_THRESHOLD = 6;
transient int size;
final float loadFactor;
int threshold;
transient int modCount;
|
HashMap构造器
HashMap一共四种初始化的方式
1
2
3
4
|
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| 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;
this.threshold = tableSizeFor(initialCapacity);
}
|
1
2
3
4
5
6
7
8
9
10
11
|
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
|
put函数
上面我们看到，如果使用缺省的构造器，我们是不会初始化table的，而真正初始化table需要等到我们第一次使用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
| public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
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;
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);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
|
我看了一下网上的流程图都不是很准确，我这里用文字表示一下，最近实在是太累了，等我写LinkedHashMap的时候把图补上。
HashMap中put的流程如下：
- 判断table是否为空，为空则进行resize()初始化table
- 计算插入的Key的在table中的索引i
- 若table[i]中没有值，则新建一个Node插入该位置
- 若有值，则判断插入的key是否与table[i]中首节点的key相等，若相等则直接替换val
- 若key不等，则判断table[i]存放的是否为红黑树，若为红黑树，则进行红黑树的插入操作
- 红黑树中也会进行key值的比较，若相等则直接修改val，若不等则插入新节点
- 若table[i]中存放的是链表，则遍历链表
- 若遍历过程中发现有key相等，则直接替换
- 若遍历到链表的结尾，则在结尾插入新的Node
- 若此时table[i]内存放的元素大于8，则将链表转化成红黑树，并对红黑树进行扩容
- 插入成功后，若数组中存放的key-value数值大于数组阈值后，则进行resize()扩容操作。
get函数
有put就有get，这是HashMap最常用的两个函数，其主要的难点在于红黑树的查找，这在下文会讲。
以下是源码：
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
| 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 &&
((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;
}
|
remove函数
最后一项删操作，如果增和查的操作都了解的话，删操作也就通俗易懂。其大体的思路就是：查到需要删除的节点，然后执行红黑树的删除或者链表的删除。
源码如下：
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
| public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
|
resize函数
在我们进行HashMap操作的时候会经常会有扩容的需求，因此了解扩容的机制十分重要。
源码如下：
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
|
final 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;
}
else if (oldThr > 0)
newCap = oldThr;
else {
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;
@SuppressWarnings({"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 {
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;
}
|
红黑树讲解
JDK8之后，HashMap引入了红黑树，红黑树是一种自平衡二叉查找树。本节将通过数据《算法》和HashMap的部分源码来解析红黑树的结构。
2-3平衡树
理解红黑树的平衡是一件比较抽象的事情，很多博客并不讲红黑树是如何实现平衡的。本文通过2-3平衡树来讲解一下”平衡”的概念。
完美平衡
完美平衡是指，所有空结点到根结点的的距离相等，比如下图就是一个完美平衡的二叉树:
很明显可以看出来，如果一颗普通的二叉树要达到完美平衡，其对于结点的数量是有要求的: $ n = 2^{k} - 1 $ , 如果结点数量不满足这个等式, 那么一颗二叉树始终不可能是平衡的。
那么如何使一棵树不管有几个结点都能保持平衡呢?
这里设想一下, 左右子树在最理想的情况下高度差是多少? 答案很明显是1, 因为任意数都可以在$ 2^{k} $和$ 2^{k+1} $之间。因此如果我们把高的子树的高度减一, 那么这棵树就实现了完美平衡。
2-3树的基本结构
如何实现高度减一呢? 有一个特别简单的办法, 那就是新定义一个结点:3-结点。我们将普通二叉树的结点定义为：2-结点。2-结点存储一个key，并且有左右两个子树; 3-结点存储两个key, 并且有左中右三个子树。2-3树就是由2-结点和3-结点组成的树, 二叉树也是2-3树的一种。下面是一个2-3树示例:
实现完美平衡
2-3树可以始终保持完美平衡, 因为在2-3树中插入新值不会破坏其平衡性, 下面我们仔细讲一讲如何实现2-3树的插入操作。
一个树在第一次生成的时候一定是平衡的, 因为只有一个2-结点, 当我们在一个平衡的树的底部插入新结点的时候会破坏其平衡性。因此, 我们在讲解2-3树的插入操作前, 必须有一个前提: 2-3树在插入前是平衡的。
当我们插入一个新结点时，会遇到以下的几种情况:
- 在一个2-结点的底部插入新键:
- 在一个没有父节点的3-结点底部插入新键: 临时构建一个4-结点。
- 在一个父节点是2-结点的3-结点底部插入新键:
- 在一个父节点是3-结点的3-结点底部插入新键:
可以看到, 2-3树之所以能保持平衡性, 是因为其在插入的过程中, 不会在底部增加高度, 而是自下而上去寻找一个2-结点能够吸收这个高度变化, 如果没有寻找到这个2-结点, 则会通过把遇到的3-结点创建为临时4-结点并分解的方式使左右子树的高度均增加1, 以保证树的平衡。(这里稍微再说一下, 如果这个3-结点不是根结点, 则增加的高度也不会破坏其平衡性, 因为分解4-结点的操作会在顶部生成一个2-结点, 而这个增加的2-结点相当于对3-结点的父结点进行一次插入操作)
查找和插入操作的复杂度
要理解2-3树的操作复杂度, 需要知道树的高度。因为其平衡特性, 2-3树的高度在 $ log_{2}N $ (全是2-结点)和$ log_{3}N $ (全是3-结点)之间。因此, 其查找的复杂度在 $ O(logN) $; 其插入操作需要先查找, 然后进行结点的变换。单个结点变换的复杂度为$ O(1) $, 平均要进行$logN$次变换(最少变换一次: 父结点是2-结点; 最坏变换树的高度: 一路上去全是3-结点, 最后到根结点), 因此插入的复杂度是: $O(logN)+O(logN) = O(logN)$。
红黑树
理解了2-3平衡树后, 红黑树就好理解了。 红黑二叉树的基本思想是用标准的二叉树(全是2-结点)以及一些额外的信息(替换3-结点)来表示2-3平衡树。这个额外的信息是: 红链接将两个2-结点组成一个3-结点, 黑链接表示2-3树的普通链接。红链接指向的结点我们会标记为红色结点。关于一个3-结点和红链接的表示如下图： 
等价定义
红黑树可以说是2-3树的变种, 任意的2-3树都能转换成红黑树, 我们可以用一种等价的定义来描述红黑树(和网络上一般讲解的不太一样, 但是都是对的): 红黑树是满足下列条件的二叉查找树:
- 红链接均为左链接(即所有的红色结点都是左结点, 根结点必然是黑色);
- 没有任何一个结点同时与两条红链接相连;
- 该树是完美黑色平衡的
满足上述定义的红黑树与相应的2-3树必然是一一对应的。完美黑色平衡是非常直观的，因为红结点不能单独作为2-结点，我们把红链接放平，就是一颗完美平衡的2-3树, 下面是一个简单的示例: 
简单的红黑树结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| private static final boolean RED = true;
private static final boolean BLACK = false;
private class TreeNode{
Key key;
Value val;
TreeNode left, right;
int N;
boolean color;
TreeNode(Key key, Value val, int N, boolean color){
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
|
1
2
3
4
5
6
7
8
9
10
|
private boolean isRed(TreeNode x){
if(x == null) return false;
return x.color == RED;
}
private int size(TreeNode x){
if(x == null) return null;
else return x.N;
}
|
旋转和颜色变换
进行插入的过程中可能会破坏上述性质: 出现红色右链接和两条连续的红链接。这些情况可以通过简单的旋转和颜色变换进行修复。其中旋转是一次进行链接变换的简单操作。
- 左旋转: 把一条右红链接转换为左链接, 如图:
- 右旋转: 把一条左红链接转换为右链接, 如图:
- 颜色变换: 当左右链接均为红色, 则把两条链接都变黑, 并把根结点变红, 如图:
我们可以利用旋转操作帮我们保证红黑树和2-3树的一一对应, 因此我们无需担心树的平衡性。
代码实现
1
2
3
4
5
6
7
8
9
10
| TreeNode rotateLeft(TreeNode h){
TreeNode x = h.right;
h.right = x.right;
x.left = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) +size(h.right);
retrurn x;
}
|
1
2
3
4
5
6
7
8
9
10
| TreeNode rotateRight(TreeNode h){
TreeNode x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
|
1
2
3
4
5
| TreeNode filpColors(TreeNode h){
h.left.color = BLACK;
h.right.color = BLACK;
h.color = RED;
}
|