java源码解读--treemap

发表于 | 分类于 |
字数统计: | 阅读时长 ≈

TreeMap

treemap可以根据key的大小存储k-v对，从而保证元素有序。treemap底层使用红黑树结构来实现。

类定义

继承了AbstractMap抽象类，实现了NavigableMap接口

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

成员变量

1
2
3
4
5
6
7
8
//比较器
   private final Comparator<? super K> comparator;
//头节点
   private transient Entry<K,V> root;
//k-v对数量
   private transient int size = 0;
//修改次数
   private transient int modCount = 0;

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public TreeMap() {
    comparator = null;
}

public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

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) {
    }
}

entry

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
//treemap中entry的定义，除了k、v还有左右父节点指针，颜色标志位
   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;
       }

       public K getKey() {
           return key;
       }

       public V getValue() {
           return value;
       }

       public V setValue(V value) {
           V oldValue = this.value;
           this.value = value;
           return oldValue;
       }

       public boolean equals(Object o) {
           if (!(o instanceof Map.Entry))
               return false;
           Map.Entry<?,?> e = (Map.Entry<?,?>)o;

           return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
       }

       public int hashCode() {
           int keyHash = (key==null ? 0 : key.hashCode());
           int valueHash = (value==null ? 0 : value.hashCode());
           return keyHash ^ valueHash;
       }

       public String toString() {
           return key + "=" + value;
       }
   }

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

   public V put(K key, V value) {
       Entry<K,V> t = root;
//root是null，则构建新entry作为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;
               else
                   return t.setValue(value);
           } while (t != null);
       }
       else {
	//如果没有设置比较器，则使用对象内部的compareTo方法进行比较
           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
       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;
   }

fixAfterInsertion

在红黑树中插入节点后，会让红黑树变得不平衡，需要调用该方法调整树结构

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

   private void fixAfterInsertion(Entry<K,V> x) {
//默认所有新插入元素为红色节点，这样不违反红黑树从根节点到叶子节点所有路径包含的黑色节点个数相同的性质
       x.color = RED;
//3种情况满足一点就结束调整
//1.当前节点为空
//2.当前节点是root
//3.当前节点的父节点是黑色
       while (x != null && x != root && x.parent.color == RED) {
	//父节点是祖父节点的左节点
           if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
	//y是祖父节点的右节点，即叔父节点
               Entry<K,V> y = rightOf(parentOf(parentOf(x)));
	//如果叔父节点是红色
               if (colorOf(y) == RED) {
		//父节点颜色置为黑色
                   setColor(parentOf(x), BLACK);
		//叔父节点颜色置为黑色
                   setColor(y, BLACK);
		//祖父节点置为红色
                   setColor(parentOf(parentOf(x)), RED);
		//重新冲祖父节点调整红黑树
                   x = parentOf(parentOf(x));
               } 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 {
	//如果当前节点的左节点是祖父节点的右节点
	//y是祖父节点的左节点，即当前节点的叔父节点
               Entry<K,V> y = leftOf(parentOf(parentOf(x)));
	//叔父节点是红色，直接修改颜色
               if (colorOf(y) == RED) {
                   setColor(parentOf(x), BLACK);
                   setColor(y, BLACK);
                   setColor(parentOf(parentOf(x)), RED);
                   x = parentOf(parentOf(x));
               } else {
		//如果x是父节点的左节点
                   if (x == leftOf(parentOf(x))) {
                       x = parentOf(x);
		//以父节点为支点左右旋
                       rotateRight(x);
                   }
		//设置父节点为黑色
                   setColor(parentOf(x), BLACK);
		//设置祖父节点为红色
                   setColor(parentOf(parentOf(x)), RED);
		//以祖父节点为支点进行左旋
                   rotateLeft(parentOf(parentOf(x)));
               }
           }
       }
       root.color = BLACK;
   }

get

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
   public V get(Object key) {
       Entry<K,V> p = getEntry(key);
       return (p==null ? null : p.value);
   }
//直接根据排序查找
   final Entry<K,V> getEntry(Object key) {
//如果默认比较器不为空，则使用默认比较器进行比较
       if (comparator != null)
           return getEntryUsingComparator(key);
       if (key == null)
           throw new NullPointerException();
       @SuppressWarnings("unchecked")
           Comparable<? super K> k = (Comparable<? super K>) key;
//默认比较器为空，则使用compareTo方法进行比较
       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;
   }

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
61
62
63
64
65

   public V remove(Object key) {
//先找到对应的entry
       Entry<K,V> p = getEntry(key);
       if (p == null)
           return null;
//返回原value
       V oldValue = p.value;
//删除entry
       deleteEntry(p);
       return oldValue;
   }

//删除entry的真正实现
   private void deleteEntry(Entry<K,V> p) {
       modCount++;
       size--;
//若被删除节点p的左孩子和右孩子都不为空，则查找替代节点
       if (p.left != null && p.right != null) {
	//查找p的替代节点，一般为p的右子树中最小的节点
           Entry<K,V> s = successor(p);
           p.key = s.key;
           p.value = s.value;
	//后继节点变成待删除节点，由于只是替换，没有真正删除节点，所以前面的树结构不用改变
           p = s;
       } // p has 2 children

//replacement是替代节点的后继节点
       Entry<K,V> replacement = (p.left != null ? p.left : p.right);
//如果待删除节点p只有一个后继节点
       if (replacement != null) {	
	//把p的父节点给replacement节点
           replacement.parent = p.parent;
	//如果p是根节点，则replacement为根节点
           if (p.parent == null)
               root = replacement;
           else if (p == p.parent.left)
               p.parent.left  = replacement;
           else
               p.parent.right = replacement;
	//接触待删除节点的前后引用关系
           p.left = p.right = p.parent = null;

	//如果替代节点p的节点为黑色，需要调整红黑树的结构
           if (p.color == BLACK)
               fixAfterDeletion(replacement);
       } else if (p.parent == null) { // return if we are the only node.
           root = null;
       } else {
	//p没有子节点
	//如果p是黑色节点，调整红黑树
           if (p.color == BLACK)
               fixAfterDeletion(p);
	//删除p
           if (p.parent != null) {
	//解除父节点对p的饮用
               if (p == p.parent.left)
                   p.parent.left = null;
               else if (p == p.parent.right)
                   p.parent.right = null;
	//解除p对父节点的饮用
               p.parent = null;
           }
       }
   }

fixAfterDeletion

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
//被删除节点的为黑色时才需要进行结构调整 
   private void fixAfterDeletion(Entry<K,V> x) {
//如果x不是跟节点并且x的颜色是黑色
       while (x != root && colorOf(x) == BLACK) {
	//如果x是父节点的左节点
           if (x == leftOf(parentOf(x))) {
	//sib代表兄弟节点
               Entry<K,V> sib = rightOf(parentOf(x));
	//如果兄弟节点是红色，删除节点后导致各条路径中黑色节点个数不一样，需要进行旋转操作
               if (colorOf(sib) == RED) {
                   setColor(sib, BLACK);
                   setColor(parentOf(x), RED);
                   rotateLeft(parentOf(x));
		//兄弟节点设置为父节点的右节点
                   sib = rightOf(parentOf(x));
               }
	//如果兄弟节点的两个子节点都是黑色，此时parentof(x)一定是红色，不管经不经过第一个if的调整
               if (colorOf(leftOf(sib))  == BLACK &&
                   colorOf(rightOf(sib)) == BLACK) {
		//把兄弟节点设置为红色
                   setColor(sib, RED);
		//x更新为x的父节点
                   x = parentOf(x);
               } else {
		//兄弟节点的两个自节点不都是黑色
		//如果兄弟节点的右节点是黑色
                   if (colorOf(rightOf(sib)) == BLACK) {
		//把兄弟节点的左节点设置为黑色
                       setColor(leftOf(sib), BLACK);
		//把兄弟节点设置为红色
                       setColor(sib, RED);
		//以兄弟节点为支点进行右旋
                       rotateRight(sib);
		//把兄弟节点设置为x的右节点
                       sib = rightOf(parentOf(x));
                   }
		//如果兄弟节点的两个子节点都是红色
		//把兄弟节点颜色设置为父节点颜色
                   setColor(sib, colorOf(parentOf(x)));
		//把父节点设置为黑色
                   setColor(parentOf(x), BLACK);
		//把兄弟节点的右节点设置为黑色
                   setColor(rightOf(sib), BLACK);	
		//以父节点为支点进行左旋
                   rotateLeft(parentOf(x));
                   x = root;
               }
           } else { // symmetric
               Entry<K,V> sib = leftOf(parentOf(x));

               if (colorOf(sib) == RED) {
                   setColor(sib, BLACK);
                   setColor(parentOf(x), RED);
                   rotateRight(parentOf(x));
                   sib = leftOf(parentOf(x));
               }

               if (colorOf(rightOf(sib)) == BLACK &&
                   colorOf(leftOf(sib)) == BLACK) {
                   setColor(sib, RED);
                   x = parentOf(x);
               } else {
                   if (colorOf(leftOf(sib)) == BLACK) {
                       setColor(rightOf(sib), BLACK);
                       setColor(sib, RED);
                       rotateLeft(sib);
                       sib = leftOf(parentOf(x));
                   }
                   setColor(sib, colorOf(parentOf(x)));
                   setColor(parentOf(x), BLACK);
                   setColor(leftOf(sib), BLACK);
                   rotateRight(parentOf(x));
                   x = root;
               }
           }
       }

       setColor(x, BLACK);
   }
-------------本文结束感谢您的阅读-------------

本文标题:java源码解读--treemap

文章作者:小建儿

发布时间:2018年06月13日 - 10:06

最后更新:2018年06月13日 - 10:06

原始链接:http://yajian.github.io/java源码解读-treemap/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多