TreeMap源码分析(JDK1.8)

秒速五厘米 2023-07-03 04:36 26阅读 0赞

### 文章目录 ###

*   *   *  成员变量
         *   *  1、comparator
             *  2、root
             *  3、size
             *  4、modCount
         *  构造方法
         *   *  1、TreeMap()
             *  2、TreeMap(Comparator<? super K> comparator)
             *  3、TreeMap(Map<? extends K, ? extends V> m)
             *  4、TreeMap(SortedMap<K, ? extends V> m)
         *  内部类
         *   *  1、Entry
             *  2、EntrySet
             *  3、KeySet
             *  4、Values
         *  常用方法
         *   *  1、get(Object key)
             *  2、put(K key, V value)
             *  3、putAll(Map map)
             *  4、remove(Object key)
             *  5、remove(Object key, Object value)
             *  6、size()
             *  7、clear()
             *  8、comparator()
             *  9、equals(Object o)
             *  10、entrySet()
             *  11、keySet()
             *  12、values()
             *  13、getFirstEntry()
             *  14、getLastEntry()
             *  15、firstKey()
             *  16、lastKey()
             *  17、ceilingEntry(K key)
             *  18、ceilingKey(K key)
             *  19、floorEntry(K key)
             *  20、ceilingEntry(K key)
         *  总结

### 成员变量 ###

#### 1、comparator ####

/** * 比较器，如果没指定比较器则key要实现Comparable接口重写compareTo方法 * TreeMap有两种方式定义key的比较规则：1:key实现Comparable接口重写compareTo方法;2:通过构造方法指定构造器 */
    private final Comparator<? super K> comparator;

#### 2、root ####

/** * 根节点，所有元素都存储在以root为根节点的红黑树中 */
    private transient Entry<K,V> root;

#### 3、size ####

/** * 实际元素的个数 */
    private transient int size = 0;

#### 4、modCount ####

/** * 修改次数，用于快速失败校验 */
    private transient int modCount = 0;

### 构造方法 ###

#### 1、TreeMap() ####

/** * 无参构造方法，key必须实现Comparable接口重写compareTo方法 */
    public TreeMap() { 
      comparator = null;
    }

#### 2、TreeMap(Comparator<? super K> comparator) ####

/** * 有参构造方法，使用指定的比较器来对key进行比较 */
    public TreeMap(Comparator<? super K> comparator) { 
      this.comparator = comparator;
    }

#### 3、TreeMap(Map<? extends K, ? extends V> m) ####

/** * 将传入的Map集合中的元素添加到TreeMap中，key必须实现Comparable接口重写compareTo方法 */
    public TreeMap(Map<? extends K, ? extends V> m) { 
      comparator = null;
      putAll(m);
    }

#### 4、TreeMap(SortedMap<K, ? extends V> m) ####

/** * 将传入的Map集合中的元素添加到TreeMap中，使用传入的Map集合中使用的比较器 */
    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、Entry ####

/** * 存在TreeMap中的元素其实都可以看做是一个Entry对象元素 */
    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;
      }
    }

#### 2、EntrySet ####

/** * 静态内部类EntrySet，返回一个空的内部实现类，该内部类在返回的时候内部并没有元素，同时TreeMap在put()的时候也并未特意将元素添加到内部类中，它是在迭代器遍历的时候遍历root根节点中的Entry元素，也可以使用foreach遍历(底层也是使用迭代器遍历) */
    class EntrySet extends AbstractSet<Map.Entry<K,V>> { 
      public Iterator<Map.Entry<K,V>> iterator() { 
        return new EntryIterator(getFirstEntry());
      }
    
      public boolean contains(Object o) { 
        if (!(o instanceof Map.Entry))
          return false;
        Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
        Object value = entry.getValue();
        Entry<K,V> p = getEntry(entry.getKey());
        return p != null && valEquals(p.getValue(), value);
      }
    
      public boolean remove(Object o) { 
        if (!(o instanceof Map.Entry))
          return false;
        Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
        Object value = entry.getValue();
        Entry<K,V> p = getEntry(entry.getKey());
        if (p != null && valEquals(p.getValue(), value)) { 
          deleteEntry(p);
          return true;
        }
        return false;
      }
    
      public int size() { 
        return TreeMap.this.size();
      }
    
      public void clear() { 
        TreeMap.this.clear();
      }
    
      public Spliterator<Map.Entry<K,V>> spliterator() { 
        return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
      }
    }

#### 3、KeySet ####

/** * 静态内部类KeySet，返回一个空的内部实现类，该内部类在返回的时候内部并没有元素，同时TreeMap在put()的时候也并未特意将元素添加到内部类中，它是在迭代器遍历的时候遍历root根节点中的Entry元素，也可以使用foreach遍历(底层也是使用迭代器遍历) */
    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> { 
      private final NavigableMap<E, ?> m;
      KeySet(NavigableMap<E,?> map) {  m = map; }
    
      public Iterator<E> iterator() { 
        if (m instanceof TreeMap)
          return ((TreeMap<E,?>)m).keyIterator();
        else
          return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
      }
    
      public Iterator<E> descendingIterator() { 
        if (m instanceof TreeMap)
          return ((TreeMap<E,?>)m).descendingKeyIterator();
        else
          return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
      }
    
      public int size() {  return m.size(); }
      public boolean isEmpty() {  return m.isEmpty(); }
      public boolean contains(Object o) {  return m.containsKey(o); }
      public void clear() {  m.clear(); }
      public E lower(E e) {  return m.lowerKey(e); }
      public E floor(E e) {  return m.floorKey(e); }
      public E ceiling(E e) {  return m.ceilingKey(e); }
      public E higher(E e) {  return m.higherKey(e); }
      public E first() {  return m.firstKey(); }
      public E last() {  return m.lastKey(); }
      public Comparator<? super E> comparator() {  return m.comparator(); }
      public E pollFirst() { 
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
      }
      public E pollLast() { 
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
      }
      public boolean remove(Object o) { 
        int oldSize = size();
        m.remove(o);
        return size() != oldSize;
      }
      public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                    E toElement,   boolean toInclusive) { 
        return new KeySet<>(m.subMap(fromElement, fromInclusive,
                                     toElement,   toInclusive));
      }
      public NavigableSet<E> headSet(E toElement, boolean inclusive) { 
        return new KeySet<>(m.headMap(toElement, inclusive));
      }
      public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { 
        return new KeySet<>(m.tailMap(fromElement, inclusive));
      }
      public SortedSet<E> subSet(E fromElement, E toElement) { 
        return subSet(fromElement, true, toElement, false);
      }
      public SortedSet<E> headSet(E toElement) { 
        return headSet(toElement, false);
      }
      public SortedSet<E> tailSet(E fromElement) { 
        return tailSet(fromElement, true);
      }
      public NavigableSet<E> descendingSet() { 
        return new KeySet<>(m.descendingMap());
      }
    
      public Spliterator<E> spliterator() { 
        return keySpliteratorFor(m);
      }
    }

#### 4、Values ####

/** * 静态内部类Values，返回一个空的内部实现类，该内部类在返回的时候内部并没有元素，同时TreeMap在put()的时候也并未特意将元素添加到内部类中，它是在迭代器遍历的时候遍历root根节点中的Entry元素，也可以使用foreach遍历(底层也是使用迭代器遍历) */
    class Values extends AbstractCollection<V> { 
      public Iterator<V> iterator() { 
        return new ValueIterator(getFirstEntry());
      }
    
      public int size() { 
        return TreeMap.this.size();
      }
    
      public boolean contains(Object o) { 
        return TreeMap.this.containsValue(o);
      }
    
      public boolean remove(Object o) { 
        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) { 
          if (valEquals(e.getValue(), o)) { 
            deleteEntry(e);
            return true;
          }
        }
        return false;
      }
    
      public void clear() { 
        TreeMap.this.clear();
      }
    
      public Spliterator<V> spliterator() { 
        return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
      }
    }

### 常用方法 ###

#### 1、get(Object key) ####

*  get(Object key)方法执行流程

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjIwNTAx_size_16_color_FFFFFF_t_70][]

*  get(Object key)方法源码分析

/** * 根据key来获取value元素 */
    public V get(Object key) { 
      // 根据key来获取Entry元素
      Entry<K,V> p = getEntry(key);
      
      return (p==null ? null : p.value);
    }
    
    /** * 根据key来获取Entry元素 */
    final Entry<K,V> getEntry(Object key) { 
      if (comparator != null)
        return getEntryUsingComparator(key);
      // 下面的代码为根据key实现Comparable接口重写compareTo方法来比较key元素的方式
      if (key == null)
        throw new NullPointerException();
      Comparable<? super K> k = (Comparable<? super K>) key;
      Entry<K,V> p = root;
      while (p != null) { 
        // 这里cmp为传入的key与节点元素中的key根据key中重写的compareTo方法所比较的大小
        int cmp = k.compareTo(p.key);
        // 根据cmp的大小来判断遍历左子树还是右子树
        if (cmp < 0)
          p = p.left;
        else if (cmp > 0)
          p = p.right;
        else
          return p;
      }
      return null;
    }
    
    /** * 使用指定的Comparator比较器来比较key */
    final Entry<K,V> getEntryUsingComparator(Object key) { 
      K k = (K) key;
      Comparator<? super K> cpr = comparator;
      if (cpr != null) { 
        Entry<K,V> p = root;
        while (p != null) { 
          // 这里cmp为指定的比较器来比较传入的key和节点元素中key元素的大小
          int cmp = cpr.compare(k, p.key);
          // 根据cmp的大小来判断遍历左子树还是右子树
          if (cmp < 0)
            p = p.left;
          else if (cmp > 0)
            p = p.right;
          else
            return p;
        }
      }
      return null;
    }

#### 2、put(K key, V value) ####

/** * 添加单个元素 */
    public V put(K key, V value) { 
      Entry<K,V> t = root;
        
      // root根节点为null，这是第一次执行put()操作的时候
      if (t == null) { 
        compare(key, key);
    	  // 第一次执行put()时，将该节点设置为root根节点
        root = new Entry<>(key, value, null);
        
        size = 1;
        modCount++;
        return null;
      }
      int cmp;
      Entry<K,V> parent;
      Comparator<? super K> cpr = comparator;
      
      // 使用指定的比较器来比较大小，当root红黑树中存在此元素时直接替换
      if (cpr != null) { 
        do { 
          parent = t;
          cmp = cpr.compare(key, t.key);
          // 小于0从当前节点的左子树寻找
          if (cmp < 0)
            t = t.left;
          // 大于0从当前节点的右子树寻找
          else if (cmp > 0)
            t = t.right;
          // 等于0，直接更换其value值并返回旧值
          else
            return t.setValue(value);
        } while (t != null);
      }
      
      // 根据key中重写的compareTo方法所比较的大小，当root红黑树中存在此元素时直接替换
      else { 
        if (key == null)
          throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        do { 
          parent = t;
          cmp = k.compareTo(t.key);
          // 小于0从当前节点的左子树寻找
          if (cmp < 0)
            t = t.left;
          // 大于0从当前节点的右子树寻找
          else if (cmp > 0)
            t = t.right;
          // 等于0，直接更换其value值并返回旧值
          else
            return t.setValue(value);
        } while (t != null);
      }
      
      // 当root红黑树中不存在此元素时
      // 创建Entry对象
      Entry<K,V> e = new Entry<>(key, value, parent);
      
      // 此时cmp为比较之后的最后一个节点，小于0将新加的Entry元素添加到左子树
      if (cmp < 0)
        parent.left = e;
      // 大于0将新加的Entry元素添加到右子树
      else
        parent.right = e;
      
      // 待添加好元素后，平衡红黑树
      fixAfterInsertion(e);
      
      size++;
      modCount++;
      return null;
    }
    
    /** * 比较k1和k2 */
    final int compare(Object k1, Object k2) { 
      return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
    }
    
    /** * 平衡红黑树 */
    private void fixAfterInsertion(Entry<K,V> x) { 
      x.color = RED;
    
      while (x != null && x != root && x.parent.color == RED) { 
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { 
          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 { 
          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 { 
            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;
    }

#### 3、putAll(Map map) ####

/** * 批量添加元素 */
    public void putAll(Map<? extends K, ? extends V> map) { 
        int mapSize = map.size();
      
        // 当该TreeMap对象中size为0，并且传入的SortedMap对象不为空时
        if (size==0 && mapSize!=0 && map instanceof SortedMap) { 
            Comparator<?> c = ((SortedMap<?,?>)map).comparator();
            
            // comparator和SortedMap对象的比较器一致
            if (c == comparator || (c != null && c.equals(comparator))) { 
                ++modCount;
                try { 
                    buildFromSorted(mapSize, map.entrySet().iterator(), null, null);
                } catch (java.io.IOException cannotHappen) { 
                } catch (ClassNotFoundException cannotHappen) { 
                }
                return;
            }
        }
    
        // 调用父类AbstractMap中的putAll()方法
        super.putAll(map);
    }
    
    /** * 根据传入的SortedMap构建TreeMap对象 */
    private void buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws  java.io.IOException, ClassNotFoundException { 
      this.size = size;
    
    	// 根据传入的SortedMap构建TreeMap对象实现
      root = buildFromSorted(0, 0, size-1, computeRedLevel(size), it, str, defaultVal);
    }
    
    /** * 计算红黑树的高度 */
    private static int computeRedLevel(int sz) { 
      int level = 0;
      for (int m = sz - 1; m >= 0; m = m / 2 - 1)
        level++;
      return level;
    }
    
    /** * 根据传入的SortedMap构建TreeMap对象实现 * * @param level 树的高度，初始值为0 * @param lo 子树的第一个元素的索引，初始值为0 * @param hi 子树的最后一个元素的索引，初始值为size-1. * @param redLevel 哪些节点应该是红色的节点. 它必须和computeRedLevel方法计算出来的一样 */
    private final Entry<K,V> buildFromSorted(int level, int lo, int hi, int redLevel, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException { 
        if (hi < lo) return null;
    
        int mid = (lo + hi) >>> 1;
    
        Entry<K,V> left  = null;
        if (lo < mid)
            left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                                   it, str, defaultVal);
    
        K key;
        V value;
        if (it != null) { 
            if (defaultVal==null) { 
                Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
                key = (K)entry.getKey();
                value = (V)entry.getValue();
            } else { 
                key = (K)it.next();
                value = defaultVal;
            }
        } else {  // use stream
            key = (K) str.readObject();
            value = (defaultVal != null ? defaultVal : (V) str.readObject());
        }
    
        Entry<K,V> middle =  new Entry<>(key, value, null);
    
        // color nodes in non-full bottommost level red
        if (level == redLevel)
            middle.color = RED;
    
        if (left != null) { 
            middle.left = left;
            left.parent = middle;
        }
    
        if (mid < hi) { 
            Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                               it, str, defaultVal);
            middle.right = right;
            right.parent = middle;
        }
    
        return middle;
    }
    
    /** * 在父类AbstractMap中的putAll()方法中，循环调用put(K key, V value)方法添加元素 */
    public void putAll(Map<? extends K, ? extends V> m) { 
      // for循环调用put(key,value)方法来添加元素
      for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
        put(e.getKey(), e.getValue());
    }

#### 4、remove(Object key) ####

/** * 根据key来删除Entry元素 */
    public V remove(Object key) { 
      // 根据key来获取Entry元素
      Entry<K,V> p = getEntry(key);
      
      // 当Entry元素不存在时，返回null
      if (p == null)
        return null;
    
      V oldValue = p.value;
      
      // 根据Entry来删除Entry元素
      deleteEntry(p);
      
      // 返回删除之前的value值
      return oldValue;
    }
    
    /** * 根据key来获取Entry元素 */
    final Entry<K,V> getEntry(Object key) { 
      if (comparator != null)
        return getEntryUsingComparator(key);
      // 下面的代码为根据key实现Comparable接口重写compareTo方法来比较key元素的方式
      if (key == null)
        throw new NullPointerException();
      Comparable<? super K> k = (Comparable<? super K>) key;
      Entry<K,V> p = root;
      while (p != null) { 
        // 这里cmp为传入的key与节点元素中的key根据key中重写的compareTo方法所比较的大小
        int cmp = k.compareTo(p.key);
        // 根据cmp的大小来判断遍历左子树还是右子树
        if (cmp < 0)
          p = p.left;
        else if (cmp > 0)
          p = p.right;
        else
          return p;
      }
      return null;
    }
    
    /** * 删除Entry元素，并平衡红黑树 */
    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;
        }
      }
    }

#### 5、remove(Object key, Object value) ####

/** * 根据key和value来删除元素，该方法为集合顶级接口Map中定义的接口默认实现方法 */
    default boolean remove(Object key, Object value) { 
      Object curValue = get(key);
      
      // 判断传入的value值和根据key获取的value值是否相等 || root红黑树中是否包含该key
      if (!Objects.equals(curValue, value) || (curValue == null && !containsKey(key))) { 
        return false;
      }
      
      // 根据key来删除Entry元素
      remove(key);
      
      return true;
    }
    
    /** * 从root红黑树中获取Entry元素 */
    public V get(Object key) { 
      Entry<K,V> p = getEntry(key);
      return (p==null ? null : p.value);
    }
    
    /** * 判断root红黑树中是否包含该key */
    public boolean containsKey(Object key) { 
      return getEntry(key) != null;
    }

#### 6、size() ####

/** * 返回红黑树实际的元素个数 */
    public int size() { 
        return size;
    }

#### 7、clear() ####

/** * 将root根据置为null，同时size为0 */
    public void clear() { 
      modCount++;
      size = 0;
      root = null;
    }

#### 8、comparator() ####

/** * 返回比较器实例 */
    public Comparator<? super K> comparator() { 
      return comparator;
    }

#### 9、equals(Object o) ####

/** * 调用的是父类AbstractMap中的equals(Object o)方法，用于比较当前TreeMap和传入的Map对象中元素是否完全一样 */
    public boolean equals(Object o) { 
      // 如果是当前对象，直接返回true
      if (o == this)
        return true;
    	// 如果不是Map对象，直接返回false
      if (!(o instanceof Map))
        return false;
      Map<?,?> m = (Map<?,?>) o;
      // 如果传入的Map对象的size和当前TreeMap的size不一样，直接返回false
      if (m.size() != size())
        return false;
    
      try { 
        // 迭代器遍历当前TreeMap集合
        Iterator<Entry<K,V>> i = entrySet().iterator();
        while (i.hasNext()) { 
          Entry<K,V> e = i.next();
          K key = e.getKey();
          V value = e.getValue();
          
          // 当value为null时
          if (value == null) { 
            // 当!(m中该key下的value为null并且包含此key时)
            if (!(m.get(key)==null && m.containsKey(key)))
              return false;
          }
          // 当value不为null时
          else { 
            // 当value不和传入Map对象的value一致时
            if (!value.equals(m.get(key)))
              return false;
          }
        }
      } catch (ClassCastException unused) { 
        return false;
      } catch (NullPointerException unused) { 
        return false;
      }
    
      return true;
    }

#### 10、entrySet() ####

/** * 返回一个非空的EntrySet对象 */
    public Set<Map.Entry<K,V>> entrySet() { 
      EntrySet es = entrySet;
      return (es != null) ? es : (entrySet = new EntrySet());
    }

#### 11、keySet() ####

/** * 返回一个非空的key的Set对象 */
    public Set<K> keySet() { 
      return navigableKeySet();
    }
    
    /** * 返回一个非空的key的Set对象实现 */
    public NavigableSet<K> navigableKeySet() { 
      KeySet<K> nks = navigableKeySet;
      return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }

#### 12、values() ####

/** * 返回一个非空的value的Collection对象 */
    public Collection<V> values() { 
      Collection<V> vs = values;
      if (vs == null) { 
        vs = new Values();
        values = vs;
      }
      return vs;
    }

#### 13、getFirstEntry() ####

/** * 获取第一个Entry元素 */
    final Entry<K,V> getFirstEntry() { 
      Entry<K,V> p = root;
      if (p != null)
        while (p.left != null)
          p = p.left;
      return p;
    }

#### 14、getLastEntry() ####

/** * 获取最后一个Entry元素 */
    final Entry<K,V> getLastEntry() { 
      Entry<K,V> p = root;
      if (p != null)
        while (p.right != null)
          p = p.right;
      return p;
    }

#### 15、firstKey() ####

/** * 获取第一个Entry元素的key */
    public K firstKey() { 
      return key(getFirstEntry());
    }
    
    /** * 获取Entry元素的key */
    static <K> K key(Entry<K,?> e) { 
      if (e==null)
        throw new NoSuchElementException();
      return e.key;
    }

#### 16、lastKey() ####

/** * 获取最后一个Entry元素 */
    public K lastKey() { 
      return key(getLastEntry());
    }
    
    /** * 获取Entry元素的key */
    static <K> K key(Entry<K,?> e) { 
      if (e==null)
        throw new NoSuchElementException();
      return e.key;
    }

#### 17、ceilingEntry(K key) ####

/** * 返回至少大于或等于指定key的Entry对象，如果不存在这样的Entry对象，返回null */
    public Map.Entry<K,V> ceilingEntry(K key) { 
      return exportEntry(getCeilingEntry(key));
    }
    
    /** * 返回至少大于或等于指定key的Entry对象，如果不存在这样的Entry对象，返回null的实现 */
    final Entry<K,V> getCeilingEntry(K key) { 
      Entry<K,V> p = root;
      while (p != null) { 
        
        // 比较两个key的大小
        int cmp = compare(key, p.key);
        
        // cmp<0，遍历p的左子树
        if (cmp < 0) { 
          if (p.left != null)
            p = p.left;
          else
            return p;
        }
        
        // cmp>0，遍历p的右子树
        else if (cmp > 0) { 
          if (p.right != null) { 
            p = p.right;
          }
          
          // 当前节点的key比指定的key要小，需要找比当前节点key要大的节点，即右子树，但是右子树为null，则上一个节点(父节点>左子树节点)就是需要的节点
          else { 
            Entry<K,V> parent = p.parent;
            Entry<K,V> ch = p;
            while (parent != null && ch == parent.right) { 
              ch = parent;
              parent = parent.parent;
            }
            return parent;
          }
        } else
          return p;
      }
      return null;
    }
    
    /** * 将TreeMap.Entry中的key、value值赋值到AbstractMap.SimpleImmutableEntry中的key、value中 */
    static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { 
      return (e == null) ? null :
      new AbstractMap.SimpleImmutableEntry<>(e);
    }

#### 18、ceilingKey(K key) ####

/** * 返回至少大于或等于指定key的key */
    public K ceilingKey(K key) { 
      return keyOrNull(getCeilingEntry(key));
    }
    
    /** * 如果不存在这样的Entry对象，返回null */
    static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) { 
      return (e == null) ? null : e.key;
    }

#### 19、floorEntry(K key) ####

/** * 返回至少小于或等于指定key的Entry对象，如果不存在这样的Entry对象，返回null */
    public Map.Entry<K,V> floorEntry(K key) { 
      return exportEntry(getFloorEntry(key));
    }
    
    /** * 返回至少小于或等于指定key的Entry对象，如果不存在这样的Entry对象，返回null的实现 */
    final Entry<K,V> getFloorEntry(K key) { 
      Entry<K,V> p = root;
      while (p != null) { 
        
        // 比较两个key的大小
        int cmp = compare(key, p.key);
        
        // cmp>0，遍历p的右子树
        if (cmp > 0) { 
          if (p.right != null)
            p = p.right;
          else
            return p;
        }
        
        // cmp<0，遍历p的左子树
        else if (cmp < 0) { 
          if (p.left != null) { 
            p = p.left;
          }
          
          // 当前节点的key比指定的key要大，需要找比当前节点key要小的节点，即左子树，但是左子树为null，则上一个节点(父节点>左子树节点)就是需要的节点
          else { 
            Entry<K,V> parent = p.parent;
            Entry<K,V> ch = p;
            while (parent != null && ch == parent.left) { 
              ch = parent;
              parent = parent.parent;
            }
            return parent;
          }
        } else
          return p;
    
      }
      return null;
    }
    
    /** * 将TreeMap.Entry中的key、value值赋值到AbstractMap.SimpleImmutableEntry中的key、value中 */
    static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { 
      return (e == null) ? null :
      new AbstractMap.SimpleImmutableEntry<>(e);
    }

#### 20、ceilingEntry(K key) ####

/** * 返回至少小于或等于指定key的key */
    public K floorKey(K key) { 
      return keyOrNull(getFloorEntry(key));
    }
    
    /** * 如果不存在这样的Entry对象，返回null */
    static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) { 
      return (e == null) ? null : e.key;
    }

### 总结 ###

*  TreeMap有两种方式定义key的比较规则，优先使用指定的构造器进行比较key
    
     *  key实现Comparable接口重写compareTo方法
     *  通过构造方法指定构造器
 *  JDK1.8的TreeMap底层是用红黑树来实现的
 *  执行put()、remove()方法都会对红黑树进行平衡
 *  TreeMap是线程不安全的，内部使用fast-fail机制当在使用HashMap中出现了线程安全问题时，将会抛出ConcurrentModificationException来提交你，避免你继续错下去
 *  TreeMap中的元素都可以看做是一个Entry对象，每一个Entry对象都是红黑树中的一个节点，Entry对象主要包含六个成员变量
    
     *  key：TreeMap的key
     *  value：TreeMap的value
     *  left：指向当前节点的左子树
     *  right：指向当前节点的右子树
     *  parent：指向当前节点的父节点
     *  color：表示当前节点的颜色
 *  keySet()、values()、entrySet()方法返回的都是空的内部实现类，该内部类在返回的时候内部并没有元素，同时HashMap在put()的时候也并未特意将元素添加到内部类中，它是在迭代器遍历的时候遍历table数组中的Entry元素，也可以使用foreach遍历(底层也是使用迭代器遍历)，set集合和collection集合中并未提供get()方法，所以不能使用普通for循环来遍历

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjIwNTAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200122225531574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1NjIwNTAx,size_16,color_FFFFFF,t_70