SAKURA
0%

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