TreeMap底层源码

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
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>{
    //外置比较器
    private final Comparator<? super K> comparator;
    //根节点
    private transient Entry<K,V> root;//null
    //元素个数
    private transient int size = 0;
	//外部操作数
    private transient int modCount = 0;
    
    public TreeMap() {
        comparator = null;
    }
    
    public TreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }
    
    //key - new Student("水菜丽", '女', 27, "2301", "003")
    //value - "吃马赛克
    public V put(K key, V value) {
        Entry<K,V> t = root;//t - 0x001
        //第一次添加元素时进入的判断
        if (t == null) {
            compare(key, key); // key自己判断自己的目的：检查key是否为null

            root = new Entry<>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        //比较结果
        int cmp;
        //父节点
        Entry<K,V> parent;
       
        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 {//执行的是内置比较器的逻辑
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            
            //t - null
            do {
                //parent - 0x001
                parent = t;
                //cmp - 2
                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);
        }
        //e - 0x003
        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;
    }
    
    //k1 - new Student("麻生希", '女', 25, "2301", "001")
    //k2 - new Student("麻生希", '女', 25, "2301", "001")
    @SuppressWarnings("unchecked")
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }
    
    //节点类
    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; -- 红黑树

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    }
}
1
2
3
4
5
6
场景一：
    TreeMap<Student,String> map = new TreeMap<>();
		
    map.put(new Student("麻生希", '女', 25, "2301", "001"),"写代码");   
    map.put(new Student("椎名空", '女', 20, "2301", "002"),"打游戏");   
    map.put(new Student("水菜丽", '女', 27, "2301", "003"),"吃马赛克");   
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
场景二：
    TreeMap<Student,String> map = new TreeMap<>(new Comparator<Student>() {
			//排序规则 - 按照名字排序，名字长度一致按照年龄排序
			@Override
			public int compare(Student o1, Student o2) {
				if(o1.equals(o2)){
					return 0;
				}
				
				int nameLen1 = o1.getName().length();
				int nameLen2 = o2.getName().length();
				if(nameLen1 != nameLen2){
					return nameLen1 - nameLen2;
				}
				
				int age1 = o1.getAge();
				int age2 = o2.getAge();
				if(age1 != age2){
					return age1 - age2;
				}
				return 1;
			}
		});
		
		map.put(new Student("麻生希", '女', 25, "2301", "001"),"写代码");   
		map.put(new Student("椎名空", '女', 20, "2301", "002"),"打游戏");   
		map.put(new Student("水菜丽", '女', 27, "2301", "003"),"吃马赛克");

TreeMap底层数据结构是：红黑树