JAVA基础知识-HashMap

JAVA基础知识-HashMap 相关知识。

常用的通配符

T, E, K, V, ?

本质上没有任何区别,但是为了维持可读性,常这样约定:

?表示不确定的JAVA类型

T (type) 表示一个具体的JAVA类型

K V (key value) 分别表示JAVA键值对 key - value

E (element) 代表Element

RBT(红黑树)

  • 每个节点是红色或者黑色
  • 根节点是黑色
  • 每个叶节点是黑色的
  • 如果一个节点是红色的,则它的两个儿子都是黑色的
  • 对于每个节点,从该结点到其叶子节点构成的所有路径上的黑色结点个数相同

插入过程:

默认插入节点为红色

AVL(自平衡二叉查找树)

  • 首先是一棵二叉查找树

    某节点的左子树节点值仅包含小于该节点值

    某节点的右子树节点值仅包含大于该节点值

    左右子树每个也必须是二叉查找树

  • 带有平衡条件,每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1

RBT和AVL

查找远远多于插入删除,选择AVL树

如果查找、插入、删除频率差不多,那么选择红黑树

JAVA 中红黑树的实现

1
2
3
4
5
6
7
8
9
10
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}

红黑树的插入过程:

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
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
// 初始染色为红
x.red = true;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// 插入的为根节点(父节点为空),则直接把颜色改为黑色
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 父节点为黑色节点或者插入节点的祖父节点为空,则直接返回
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// I. 父节点和祖父节点都存在且父节点是祖父节点的左节点
if (xp == (xppl = xpp.left)) {
// 1. 祖父节点的右节点(叔叔节点)不是空且为红色
if ((xppr = xpp.right) != null && xppr.red) {
// 将叔叔节点改为黑色
xppr.red = false;
// 将父亲节点改为黑色
xp.red = false;
// 将祖父节点改为红色
xpp.red = true;
x = xpp;
}
// 2. 祖父节点的右节点(叔叔节点)是空或者为黑色
else {
// 插入节点是父节点的右孩子,将父节点左旋
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 插入节点是父节点的左孩子
if (xp != null) {
// 将父节点变成黑色节点
xp.red = false;
if (xpp != null) {
// 祖父节点变成红色节点,然后将祖父节点右旋
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
// II. 父节点和祖父节点都存在且父节点是祖父节点的右节点
else {
// 1. 祖父节点的左节点(叔叔节点)不为空且为红色
if (xppl != null && xppl.red) {
// 将叔叔节点改为黑色
xppl.red = false;
// 将父亲节点改为黑色
xp.red = false;
// 将祖父节点改为红色
xpp.red = true;
x = xpp;
}
// 2. 祖父节点的左节点(叔叔节点)是空或者为黑色
else {
// 插入节点是父节点的左孩子,将父节点右旋
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 插入节点是父节点的右孩子
if (xp != null) {
// 将父节点变成黑色节点
xp.red = false;
if (xpp != null) {
// 祖父节点变成红色节点,然后将祖父节点左旋
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}

左旋右旋方法:

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
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}

static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
}

红黑树的删除过程:

  1. 先进行二叉搜索树的删除
  2. 然后进行红黑树的调整
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
// p是待删除节点,replacement用于后续的红黑树调整,指向的是p或者p的继承者。
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}

// 如果删除时的节点p是红色,则树平衡不会被破坏,无需调整。
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, 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
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
// root : 根节点 | x : 根节点的继承者
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
// 如果x为空或x为根节点,直接返回
if (x == null || x == root)
return root;
// x为根节点,染成黑色,直接返回(删除的为根节点,则扶植继承者x为新的根节点)
else if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// x为红色,则无需调整,直接返回根节点
else if (x.red) {
x.red = false;
return root;
}
// x为其父节点的左孩子
else if ((xpl = xp.left) == x) {
// 如果x有红色兄弟节点xpr, 则它的父节点xp一定是黑色节点
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
// 将父节点左旋
root = rotateLeft(root, xp);
// 重新将xp指向x的父节点,xpr指向xp新的右孩子
xpr = (xp = x.parent) == null ? null : xp.right;
}
//如果xpr为空,则向上继续调整,将x的父节点xp作为新的x继续循环
if (xpr == null)
x = xp;
else {
// sl和sr分别为其近侄子和远侄子
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
// 若s1和s2都为黑色或者不存在,即xpr没有红色孩子,则将xpr染红
if ((sr == null || !sr.red) && (sl == null || !sl.red)) {
xpr.red = true;
// 继续向上循环
x = xp;
}
else {
// 右孩子为空或者为黑色
if (sr == null || !sr.red) {
// 有左孩子则染黑
if (sl != null)
sl.red = false;
// 将xpr染红
xpr.red = true;
// xpr右旋
root = rotateRight(root, xpr);
// 右旋后xpr指向xp的新右孩子,即上面的s1
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
// xpr染成跟父节点一致的颜色,为后面父节点xp的左旋做准备
if ((sr = xpr.right) != null)
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
// xpr新的右孩子染黑,防止出现两个红色相连
sr.red = false;
}
if (xp != null) {
// 将xp染黑,并对其左旋,这样就能保证被删除的X所在的路径又多了一个黑色节点,从而达到恢复平衡的目的
xp.red = false;
root = rotateLeft(root, xp);
}
// 到此调整已经完毕,进入下一次循环后将直接退出
x = root;
}
}
}
// x为其父节点的右孩子...
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}

重写HashCode()方法和Equals()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Prediction.java
import java.util.Random;

public class Prediction {
private static Random rand = new Random(47);

private boolean shadow = rand.nextDouble() > 0.5;

public String toString() {
if (shadow) {
return "Six more weeks of Winner!";
}
else {
return "Early Spring";
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
// Groundhog.java
public class Groundhog {
protected int number;

public Groundhog(int n) {
number = n;
}

public String toString() {
return "Groundhog #" + number;
}
}
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
// SpringDetector.java
import java.lang.reflect.Constructor;
import java.util.HashMap;
import java.util.Map;

public class SpringDetector {
// 利用反射机制获取构造函数
public static <T extends Groundhog>
void detectSpring(Class<T> type) throws Exception {
Constructor<T> ghog = type.getConstructor(int.class);

Map<Groundhog, Prediction> map = new HashMap<Groundhog, Prediction>();
for (int i = 0; i < 10; i++) {
map.put(ghog.newInstance(i), new Prediction());
}

System.out.println("MAP" + map);

Groundhog groundhog = ghog.newInstance(3);

System.out.println("Looking up prediction for" + groundhog);

if (map.containsKey(groundhog)) {
System.out.println(map.get(groundhog));
} else {
System.out.println("Key not found:" + groundhog);
}
}

public static void main(String[] args) throws Exception {
detectSpring(Groundhog.class);
}
}

Output:

1
2
3
MAP{Groundhog #1=Six more weeks of Winner!, Groundhog #4=Six more weeks of Winner!, Groundhog #5=Early Spring, Groundhog #3=Early Spring, Groundhog #8=Six more weeks of Winner!, Groundhog #7=Early Spring, Groundhog #0=Six more weeks of Winner!, Groundhog #2=Early Spring, Groundhog #9=Six more weeks of Winner!, Groundhog #6=Early Spring}
Looking up prediction forGroundhog #3
Key not found:Groundhog #3

Groundhog默认调用的是基类Object的hashCode方法,默认使用的是对象的地址计算的散列码。同时只重写hashCode()方法是不够的,还需要重写equals()方法。

补充一句,hashCode()是基类Object的方法,所有Java对象都能产生散列码。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Groundhog2.java
public class Groundhog2 extends Groundhog {
public Groundhog2(int n) {
super(n);
}
public int hashCode() {
return number;
}

public boolean equals(Object object) {
return object instanceof Groundhog2 && (number == ((Groundhog2)object).number);
}
}
1
2
3
4
5
6
// SpringDetector2.java
public class SpringDetector2 {
public static void main(String[] args) throws Exception {
SpringDetector.detectSpring(Groundhog2.class);
}
}

Output:

1
2
3
MAP{Groundhog #0=Six more weeks of Winner!, Groundhog #1=Six more weeks of Winner!, Groundhog #2=Early Spring, Groundhog #3=Early Spring, Groundhog #4=Six more weeks of Winner!, Groundhog #5=Early Spring, Groundhog #6=Early Spring, Groundhog #7=Early Spring, Groundhog #8=Six more weeks of Winner!, Groundhog #9=Six more weeks of Winner!}
Looking up prediction forGroundhog #3
Early Spring
0%