前言

TreeMap采用的是红黑树(基本上是平衡二叉树时间复杂度为O(logN))
也就是它的查找保证了效率。
频繁的新增删除会导致树结构的移动变更树操作效率低下。

comparable comparator

在分析TreeMap之前先要了解一下这两个接口。他们是TreeMap的经常用到的工具方法

1
2
3
4
5
6
7
8
9
10
11
12
//集合内部默认实现比较器
public interface Comparable<T> {
    public int compareTo(T o);
}
//集合外部传入的比较器
@FunctionalInterface
public interface Comparator<T> {
	int compare(T o1, T o2);
	boolean equals(Object obj);
}

参考文章http://blog.csdn.net/mageshuai/article/details/3849143

comparable

这两个都是用来实现集合内部元素比较排序。comparable是集合元素是否显示comparable接口。
如果对象没有实现，集合内部会采用默认的自然key进行排序重复判断排序

comparator

comparator相当于一个外部专用比较器。当这个对象的自比较或者是他们提供的比较方法不能满足
时可以采用自己定义专用比较器的方式。用comparator是策略模式。不改变自身二是
用一个外部策略对象来改变他的行为。

数据结构定义

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
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;
       }
       /**
        * Returns the key.
        *
        * @return the key
        */
       public K getKey() {
           return key;
       }
       /**
        * Returns the value associated with the key.
        *
        * @return the value associated with the key
        */
       public V getValue() {
           return value;
       }
       /**
        * Replaces the value currently associated with the key with the given
        * value.
        *
        * @return the value associated with the key before this method was
        *         called
        */
       public V setValue(V value) {
           V oldValue = this.value;
           this.value = value;
           return oldValue;
       }
	//判断两个节点是否相同的方法 重写equals 和hashcode.只有key和value都相同时这个结点才相同
       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;
       }
   
}

定义基本的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class TreeMap<K,V>{
	//默认的比较器
	private final Comparator<? super K> comparator;
	
	//根节点	
    private transient Entry<K,V> root;
    /**
     * The number of entries in the tree
     */
    private transient int size = 0;
    /**
     * The number of structural modifications to the tree.
     */
    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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
	/**
 * 没有提供比较器则按照key自然大小进行排序
 * 	
    * Constructs a new, empty tree map, using the natural ordering of its
    * keys.  All keys inserted into the map must implement the {@link
    * Comparable} interface.  Furthermore, all such keys must be
    * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
    * a {@code ClassCastException} for any keys {@code k1} and
    * {@code k2} in the map.  If the user attempts to put a key into the
    * map that violates this constraint (for example, the user attempts to
    * put a string key into a map whose keys are integers), the
    * {@code put(Object key, Object value)} call will throw a
    * {@code ClassCastException}.
    */
   public TreeMap() {
       comparator = null;
   }
   /**
 * 使用传入的比较方法，这块我们可以进行自定义自己的排序规则。也可以按照value来排序
 * 
    * Constructs a new, empty tree map, ordered according to the given
    * comparator.  All keys inserted into the map must be <em>mutually
    * comparable</em> by the given comparator: {@code comparator.compare(k1,
    * k2)} must not throw a {@code ClassCastException} for any keys
    * {@code k1} and {@code k2} in the map.  If the user attempts to put
    * a key into the map that violates this constraint, the {@code put(Object
    * key, Object value)} call will throw a
    * {@code ClassCastException}.
    *
    * @param comparator the comparator that will be used to order this map.
    *        If {@code null}, the {@linkplain Comparable natural
    *        ordering} of the keys will be used.
    */
   public TreeMap(Comparator<? super K> comparator) {
       this.comparator = comparator;
   }
//采用key的默认排序，同时传入map
public TreeMap(Map<? extends K, ? extends V> m) {
       comparator = null;
       putAll(m);
   }

主要是对红黑树定义，红黑树最基本的结点entry应该包括：key、value、parent、left、right、color。并且对key进行了hash equals运算用来去重。

新增方法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
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
/**
 * 如果key已经存在老的value就会被替换
    * Associates the specified value with the specified key in this map.
    * If the map previously contained a mapping for the key, the old
    * value is replaced.
    *
    * @param key key with which the specified value is to be associated
    * @param value value to be associated with the specified key
    *
    * @return the previous value associated with {@code key}, or
    *         {@code null} if there was no mapping for {@code key}.
    *         (A {@code null} return can also indicate that the map
    *         previously associated {@code null} with {@code key}.)
    * @throws ClassCastException if the specified key cannot be compared
    *         with the keys currently in the map
    * @throws NullPointerException if the specified key is null
    *         and this map uses natural ordering, or its comparator
    *         does not permit null keys
    */
   public V put(K key, V value) {
	//检查根节点
       Entry<K,V> t = root;
	
	//特殊情况优先处理，快速结束。如果根节点为null
       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;
			//判断当前key和父key关系
               cmp = cpr.compare(key, t.key);
               if (cmp < 0)
				//父节点变成左侧叶子结点
                   t = t.left;
               else if (cmp > 0)
				//如果当前key大于父节点，父节点替换成右侧结点
                   t = t.right;
               else
				//相等直接替换父节点value值
                   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赋值关键是确定父节点
       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. 每个叶结点，即空结点（NIL）是黑的。
  4. 如果一个结点是红色的那么他的子节点都是黑色的
  5. 对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

删除方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
    * Removes the mapping for this key from this TreeMap if present.
    *
    * @param  key key for which mapping should be removed
    * @return the previous value associated with {@code key}, or
    *         {@code null} if there was no mapping for {@code key}.
    *         (A {@code null} return can also indicate that the map
    *         previously associated {@code null} with {@code key}.)
    * @throws ClassCastException if the specified key cannot be compared
    *         with the keys currently in the map
    * @throws NullPointerException if the specified key is null
    *         and this map uses natural ordering, or its comparator
    *         does not permit null keys
    */
   public V remove(Object key) {
       Entry<K,V> p = getEntry(key);
       if (p == null)
           return null;
       V oldValue = p.value;
       deleteEntry(p);
       return oldValue;
   }

先查询再删除

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
/**
    * Returns this map's entry for the given key, or {@code null} if the map
    * does not contain an entry for the key.
    *
    * @return this map's entry for the given key, or {@code null} if the map
    *         does not contain an entry for the key
    * @throws ClassCastException if the specified key cannot be compared
    *         with the keys currently in the map
    * @throws NullPointerException if the specified key is null
    *         and this map uses natural ordering, or its comparator
    *         does not permit null keys
    */
   final Entry<K,V> getEntry(Object key) {
       // Offload comparator-based version for sake of performance,最重要的是这
	//个key比较方法确定
       if (comparator != null)
           return getEntryUsingComparator(key);
       if (key == null)
           throw new NullPointerException();
       @SuppressWarnings("unchecked")
           Comparable<? super K> k = (Comparable<? super K>) key;
	//<font color="red">从父节点开始比较，比父节点小向左移动。否则向右移动</font>        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
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
/**
    * Delete node p, and then rebalance the tree.
    */
   private void deleteEntry(Entry<K,V> p) {
       modCount++;
       size--;
       // If strictly internal, copy successor's element to p and then make p
       // point to successor.
       if (p.left != null && p.right != null) {
           Entry<K,V> s = successor(p);
           p.key = s.key;
           p.value = s.value;
           p = s;
       } // p has 2 children
       // Start fixup at replacement node, if it exists.
       Entry<K,V> replacement = (p.left != null ? p.left : p.right);
       if (replacement != null) {
           // Link replacement to parent
           replacement.parent = p.parent;
           if (p.parent == null)
               root = replacement;
           else if (p == p.parent.left)
               p.parent.left  = replacement;
           else
               p.parent.right = replacement;
           // Null out links so they are OK to use by fixAfterDeletion.
           p.left = p.right = p.parent = null;
           // Fix replacement
           if (p.color == BLACK)
               fixAfterDeletion(replacement);
       } else if (p.parent == null) { // return if we are the only node.
           root = null;
       } else { //  No children. Use self as phantom replacement and unlink.
           if (p.color == BLACK)
               fixAfterDeletion(p);
           if (p.parent != null) {
               if (p == p.parent.left)
                   p.parent.left = null;
               else if (p == p.parent.right)
                   p.parent.right = null;
               p.parent = null;
           }
       }
   }