1. /**
    2.  * 我们前面提到TreeMap是可以自动排序的，默认情况下comparator为null，这个时候按照key的自然顺序进行排
    3.  * 序，然而并不是所有情况下都可以直接使用key的自然顺序，有时候我们想让Map的自动排序按照我们自己的规则，
    4.  * 这个时候你就需要传递Comparator的实现类
    5.  */
    6.   private final Comparator<? super K> comparator;
    1. /**
    2.  * TreeMap的存储结构既然是红黑树，那么必然会有唯一的根节点。
    3.  */
    4. private transient Entry<K,V> root;
    1. /**
    2.  * Map中key-val对的数量，也即是红黑树中节点Entry的数量
    3.  */
    4. private transient int size = 0;
    1. /**
    2.  * 红黑树结构的调整次数
    3.  */
    4. private transient int modCount = 0;
    1.      /**
    2.      * Node in the Tree.  Doubles as a means to pass key-value pairs back to
    3.      * user (see Map.Entry).
    4.      */
    6.     static final class Entry<K,V> implements Map.Entry<K,V> {
    7.         //key,val是存储的原始数据
    8.         K key;
    9.         V value;
    10.         //定义了节点的左孩子 
    11.         Entry<K,V> left;
    12.         //定义了节点的右孩子
    13.         Entry<K,V> right;
    14.         //通过该节点可以反过来往上找到自己的父亲
    15.         Entry<K,V> parent;
    16.         //默认情况下为黑色节点，可调整
    17.         boolean color = BLACK;
    19.         /**
    20.          * Make a new cell with given key, value, and parent, and with
    21.          * {@code null} child links, and BLACK color.
    22.          */
    23.         Entry(K key, V value, Entry<K,V> parent) {
    24.             this.key = key;
    25.             this.value = value;
    26.             this.parent = parent;
    27.         }
    29.         /**
    30.          * Returns the key.
    31.          *
    32.          * @return the key
    33.          */
    34.         public K getKey() {
    35.             return key;
    36.         }
    38.         /**
    39.          * Returns the value associated with the key.
    40.          *
    41.          * @return the value associated with the key
    42.          */
    43.         public V getValue() {
    44.             return value;
    45.         }
    47.         /**
    48.          * Replaces the value currently associated with the key with the given
    49.          * value.
    50.          *
    51.          * @return the value associated with the key before this method was
    52.          *         called
    53.          */
    54.         public V setValue(V value) {
    55.             V oldValue = this.value;
    56.             this.value = value;
    57.             return oldValue;
    58.         }
    60.         public boolean equals(Object o) {
    61.             if (!(o instanceof Map.Entry))
    62.                 return false;
    63.             Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    65.             return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
    66.         }
    68.         public int hashCode() {
    69.             int keyHash = (key==null ? 0 : key.hashCode());
    70.             int valueHash = (value==null ? 0 : value.hashCode());
    71.             return keyHash ^ valueHash;
    72.         }
    74.         public String toString() {
    75.             return key + "=" + value;
    76.         }
    77.     }