[Java]-Map源码分析-TreeMap

发表于 | 分类于 | 阅读次数

TreeMap 继承于AbstractMap，实现了navigableMap, treeMap是红黑树的java实现，已经分析过，红黑树能保证树的增删改查都在O(logN).

1
2
3
4
5
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
}

成员变量

  • 类型为键值对的根节点

  • 树的大小

  • 修改次数modCount，这个变量记录了对象的修改次数，再Iterator中使用，Iterator中有变量expectedModCount也记录了对象的更改次数，在遍历的时候若expectedModCount和modCount不同则说明有其他线程已经修改了这个对象，抛出异常。

modCount通常在线程不安全的类中才会看到，是一个避免多线程操作错误的方式：fast-fail策略。所以当大家遍历那些非线程安全的数据结构时，尽量使用迭代器。

1
2
3
4
5
6
7
8
//final，声明后不可改变
   private final Comparator<? super K> comparator;

   private transient Entry<K,V> root;

   private transient int size = 0;

   private transient int modCount = 0;
  • 这个类实现了Serializable接口，可序列化，transient关键字可以避免有该关键字的变量不被保存，默认情况下，对象中的所有变量都转换为持久状态。 在某些情况下，我们可能想要
    避免保留一些变量，因为没有必要通过网络传输。

Entry

Entry其实就是树的节点，一个键值对，这里的节点保存着key，值和父节点，左孩子，右孩子和节点颜色(初始颜色黑色)，还有一些修改节点，获得值的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    // ... 省略其他方法
}

构造函数

四个构造函数

默认构造起使用默认的自然比较， 也可以指定特殊的比较器

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
// 默认构造，比较器采用key的自然比较顺序
public TreeMap() {
    comparator = null;
}

// 指定比较器
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

// 从Map集合导入初始数据
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

// 从SortedMap导入初始数据
public TreeMap(SortedMap<K, ? extends V> m) {
    comparator = m.comparator();
    try {
        buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
    } catch (java.io.IOException cannotHappen) {
    } catch (ClassNotFoundException cannotHappen) {
    }
}

方法

添加元素

像红黑树增加一个元素：

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
public V put(K key, V value) {
	//根节点 t
    Entry<K,V> t = root;
    //如果是空树
    if (t == null) {
        compare(key, key); // type (and possibly null) check
		//创建根节点，颜色默认黑色
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        //终止
        return null;
    }
    
    //存放比较结果
    int cmp;
    //父节点
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            //节点比跟节点小，插入左子树
            if (cmp < 0)
                t = t.left;
            //节点比跟节点小，插入左子树
            else if (cmp > 0)
                t = t.right;
            //相同的key，更新value
            else
                return t.setValue(value);
        } while (t != null);
    }
    
    //没有设置比较器，用默认
    else {
        if (key == null)
            throw new NullPointerException();
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    
    //插入节点
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        parent.left = e;
    else
        parent.right = e;
        
    //修复平衡，以满足红黑树的规则，对新节点调整
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}


//恢复平衡的调整函数，原理查看：http://jiaxuehui.top/2018/11/10/[算法]-搜索-AVL、红黑树/

private void fixAfterInsertion(Entry<K,V> x) {、
	//新插入的节点设为红色
    x.color = RED;

	//当x存在，x不是根节点，x的父亲是红色的（已知x是新插入的节点为红色，且规则规定不能存在两个红色节点相连，所以需要进行如下调整）
    while (x != null && x != root && x.parent.color == RED) {
    
    //如果父亲是爷爷的左节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
        
        //让y是爷爷的右孩子，所以y是新节点的叔叔节点
            Entry<K,V> y = rightOf(parentOf(parentOf(x)));
            
            //情况1:如果叔叔是红色的，将父亲的颜色红色改为黑色，叔叔变为黑色，爷爷变为红色即可，每个子树黑色节点数目不变。不需旋转
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //继续向上循环，如果需要变色则继续，直到全部节点满足规则
                x = parentOf(parentOf(x));
            }
            //情况2:若叔叔是黑色的，变色后需要旋转（因为叔叔的路径黑色节点数减少了） 
            else {
            		//如果新节点是父亲的右子树，需要两次旋转：先左旋转
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                
                //把父亲设为黑色，爷爷变成红色，叔叔不是红色不用变色，变完色右旋转
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            } 
        } 
        //如果父亲是爷爷的右节点
        else {
            Entry<K,V> y = leftOf(parentOf(parentOf(x)));
            //情况3:父节点是右节点，叔叔是红色的
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            }
            //情况4:父节点是右节点，叔叔是黑色的，旋转
             else {
             //新节点是左孩子，右旋转
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                //左旋
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }
    //root是黑色
    root.color = BLACK;
}

左旋转：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** From CLR */
//非递归左旋转，参数：要旋转的父节点
private void rotateLeft(Entry<K,V> p) {
    if (p != null) {
    //新根为右节点
        Entry<K,V> r = p.right;
        //新根的左节点变成父节点的右节点
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        
        //如果p就是根节点
        if (p.parent == null)
            root = r;
            
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }
}

获取元素

TreeMap中的元素是有序的，当使用中序遍历时就可以得到一个有序的Set集合，所以获取元素可以采用二分法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
final Entry<K,V> getEntry(Object key) {
    // Offload comparator-based version for sake of performance
    if (comparator != null)
        return getEntryUsingComparator(key);
    if (key == null)
        throw new NullPointerException();
    @SuppressWarnings("unchecked")
        Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = k.compareTo(p.key);
        if (cmp < 0)
            p = p.left;
        else if (cmp > 0)
            p = p.right;
        else
            return p;
    }
    return null;
}

获取前一个元素

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
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
        //如果有左节点，找左子树中最大的节点
    else if (t.left != null) {
        Entry<K,V> p = t.left;
        如果左子树有有右节点，说明当前不是最大的，在右子树中找最大节点，及右子树右叶子
        while (p.right != null)
            p = p.right;
        return p;
    }
    //只有右子树，说明右边都比当前大，往前的左子树中找
     // t没有左孩子，所以t的前一个元素有两种情况
        // 1. t是右孩子，那它的前一个元素就是它的父结点
        // 2. t是左孩子，它的前一个元素需要向上递归，直到递归到下一个是右孩子的节点，转为情况1
    else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

暂时分析到这里，其他复杂方法先暂时不研究了。。