TreeMap源码解析

一、TreeMap数据结构介绍

1.红黑树简介

红黑树是一种常用的数据结构,它使得对数据的搜索、插入和删除操作都保持O(lgn)的时间复杂度
红黑树又称红-黑二叉树,它首先是一颗二叉树(Binary Search Tree,简称BST),具有二叉树所有的特性(即树中的任何节点的值大于它的左子节点且小于它的右子节点).同时红黑树更是一颗自平衡的排序二叉树

按照二叉搜索树组织数据,使得对元素的查找非常快捷.比如上如中的二叉搜索树,如果查找值为48的节点,只需要遍历4个节点即可完成.
理论上一颗平衡的二叉搜索树的任意节点平均查找效率为O(lgn),但是如果二叉搜索树失去平衡(元素全在异常),搜索效率退化为O(n),因为二叉搜索树的平衡是搜索效率的关键所在.当它的高度为logN+1时,我们就说二叉查找树是平衡的
为了维护树的平衡性,数据结构内出现了各种各样的树,比如AVL树通过维持任何节点的左右子树的高度差不大于1保持树的平衡,而红黑树使用颜色的概念维持树的平衡,使二叉搜索树的左右子树的高度差保持在固定的范围.相比于其他二叉搜索树树,红黑树对二叉搜索树的平衡性维持有着自身的优势
即红黑树节点是有颜色概念的,即非红即黑.通过颜色的约束红黑树维持着二叉搜索树的平衡性,一颗红黑树必须满足以下几点条件:

根节点必须是黑色的
任意从根到叶子的路径不包含连续的红色节点
任意从根到叶子的路径黑色节点总数相同

这些约束强制了红黑树的关键性质:从根到叶子最长的可能路径不多于最短的可能路径的两倍长.结果是这棵树大致上是平衡的.因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树.所以红黑树它是复杂而高效的,其检索效率O(lg n)

二、TreeMap的继承关系

下面先让我们来看一下TreeMap的继承关系,对它有一个大致的了解:

可以看到,除了在之前HashMap里常见的继承类和接口以外,TreeMap实现了NavigableMap接口,而NavigableMap继承自SortedMap,由名字可以看出这是一个用来实现排序的接口,这也是TreeMap能够实现排序的原因

1.SortedMap接口源码分析

1.1SortedMap接口

public interface SortedMap<K,V> extends Map<K,V> {
//返回用于对键的进行排序的比较器,如果此映射使用其键的自然排序,则为null
  Comparator<? super K> comparator();
  //返回从fromKey（包括）到toKey（不包括）之间的map
  SortedMap<K,V> subMap(K fromKey, K toKey);
  //返回小于toKey的map
  SortedMap<K,V> headMap(K toKey);
  //返回大于或等于fromKey的map
  SortedMap<K,V> tailMap(K fromKey);
  //返回map中第一个（最低）键
  K firstKey();
  //返回map中最后一个（最高）键
  K lastKey();
  Set<K> keySet();
  Collection<V> values();
  Set<Map.Entry<K, V>> entrySet();
}

SortedMap的接口比较简单,没有很特别的地方,唯一比较特别的就是Comparator接口,可以设想实现排序功能就在此处
下面让我们来看下Comparator和Comparable接口,两者之间有点关联,可以理解为Comparable自带了比较功能,而Comparator是赋予没有比较能力的对象一种比较能力
举个简单例子:面对一道计算题,小明天生口算能力很强,看一眼就能算出来答案.而小李没有这种能力,需要借助计算器才能得出答案

1.2Comparable接口

接口代码如下:

public interface Comparable<T> {
  //如果小于o,返回负数;等于o,返回0;大于o返回正数
  public int compareTo(T o);
}

里面传入一个泛型T的对象o,对o进行比较.如果小于o返回负数;等于0返回0;大于o返回正数
我们熟悉的很对对象如:String、Integer、Double等都实现了这个接口.可以来看下这个简单的例子:

@Data
public class Item implements Comparable<Item> {
    private String name;
    private int price;

    public Item(String name, int price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Item{" +
                "name='" + name + '\'' +
                ", price=" + price +
                '}';
    }

    @Override
    public int compareTo(Item o) {
        if (this.name.compareTo(o.name) < 0) {
            return -1;
        } else if (this.name.compareTo(o.name) > 0) {
            return 1;
        } else {
            return 0;
        }
    }

    public static void main(String[] args) {
        List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400));
        System.out.println("before = " + items);
        Collections.sort(items);
        System.out.println("after = " + items);
    }
}

上述例子中,我们自己实现了Comparable接口,比较了Item的name属性,然后通过Collections.sort对它进行了排序(值得注意的是:没有实现Comparable接口的对象不能使用该方法).但是如果我不想用name属性对它进行排序,想对price进行排序,或者先对name排序相同在对price排序?这个时候需要Comparator接口

1.3Comparator接口

先看一下接口的源码:

@FunctionalInterface
public interface Comparator<T> {
  // 核心方法，用来比较两个对象，如果o1小于o2，返回负数；等于o2，返回0；大于o2返回正数
  int compare(T o1, T o2);
  // 好像很少用到，一般都用对象自带的equals
  boolean equals(Object obj);
   
  /**-----------下面的都是JDK1.8新增的接口，挑几个放进去----------*/
 
  //返回反向排序比较器
  default Comparator<T> reversed() {
    return Collections.reverseOrder(this);
  }
  //根据名字知道，先进行compare比较后，再进行一次比较
  default Comparator<T> thenComparing(Comparator<? super T> other) {
    Objects.requireNonNull(other);
    return (Comparator<T> & Serializable) (c1, c2) -> {
      int res = compare(c1, c2);
      return (res != 0) ? res : other.compare(c1, c2);
    };
  }
  //对int类型的key进行比较
  public static <T> Comparator<T> comparingInt(ToIntFunction<? super T> keyExtractor) {
    Objects.requireNonNull(keyExtractor);
    return (Comparator<T> & Serializable)
      (c1, c2) -> Integer.compare(keyExtractor.applyAsInt(c1), keyExtractor.applyAsInt(c2));
  }
  //返回正常顺序的比较器
  public static <T extends Comparable<? super T>> Comparator<T> naturalOrder() {
    return (Comparator<T>) Comparators.NaturalOrderComparator.INSTANCE;
  }
}

一起来看一下如何使用,先来看一下JDK1.8之前的用法:

public class SimpleComparator implements Comparator<Item> {
  @Override
  public int compare(Item o1, Item o2) {
    return o1.price - o2.price;
  }
   
  public static void main(String[] args) {
    List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400), new Item("Orange", 100));
    Collections.sort(items, new SimpleComparator());
    System.out.println(items);
  }
}

JDK1.8以前的用法是要自己手动实现Comparator接口,然后调用Collections.sort()传入实现类来完成排序,非常麻烦,而JDK1.8则相对来说简单了很多:

public static void main(String[] args) {
  List<Item> items = Arrays.asList(new Item("banana", 200), new Item("apple", 400), new Item("Orange", 100));
  Collections.sort(items, (Item a, Item b) -> a.price - b.price);
  System.out.println(items);
}

甚至我们可以不使用Collections.sort:

public static void main(String[] args) {
  List<Item> items = Arrays.asList(new Item("banana", 100), new Item("Orange", 100), new Item("apple", 400), new Item("Orange", 50));
  items.sort((Item a, Item b) -> a.price - b.price);
  System.out.println(items);
  //使用上面的thenComparing
  items.sort(Comparator.comparing(Item::getName).thenComparing(Comparator.comparingInt(Item::getPrice)));
  System.out.println("after using thenComparing: " + items); 
}

1.4NavigableMap接口源码解析

public interface NavigableMap<K,V> extends SortedMap<K,V> {
  //返回键小于且最接近Key（不包含等于）的键值对，没有返回null
  Map.Entry<K,V> lowerEntry(K key);
  //返回小于且最接近（不包含等于）Key的键，没有返回null
  K lowerKey(K key);
  //返回键小于且最接近（包含等于）Key的键值对，没有返回null
  Map.Entry<K,V> floorEntry(K key);
  //返回小于且最接近（包含等于）Key的键，没有返回null
  K floorKey(K key);
  //返回大于且最接近（包含等于）给定key的键值对，没有返回null
  Map.Entry<K,V> ceilingEntry(K key);
  //同上
  K ceilingKey(K key);
  //返回大于且最接近（不包含等于）给定key的键值对
  Map.Entry<K,V> higherEntry(K key);
  //同上
  K higherKey(K key);
  //返回第一个Entry
  Map.Entry<K,V> firstEntry();
  //返回最后一个Entry
  Map.Entry<K,V> lastEntry();
  //移除并返回第一个Entry
  Map.Entry<K,V> pollFirstEntry();
  //同上
  Map.Entry<K,V> pollLastEntry();
  //返回map中包含的映射关系的逆序视图
  NavigableMap<K,V> descendingMap();
  //返回map中包含的键的NavigableSet视图。 set的迭代器按key的升序
  NavigableSet<K> navigableKeySet();
  //逆序
  NavigableSet<K> descendingKeySet();
  //根据fromKey和toKey来返回子map，两个boolean参数用于是否包含该key
  NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                             K toKey,   boolean toInclusive);
  //返回小于（或等于,根据inclusive）toKey的map
  NavigableMap<K,V> headMap(K toKey, boolean inclusive);
  //返回大于（或等于,根据inclusive）fromKey的map
  NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
  SortedMap<K,V> subMap(K fromKey, K toKey);
  SortedMap<K,V> headMap(K toKey);
  SortedMap<K,V> tailMap(K fromKey);
}

注意:上述返回的map与原map是相互影响的

三、TreeMap的类定义

1
2
3

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

实现NavigableMap接口,即能排序
实现了Cloneable接口,即覆盖了函数clone(),能克隆
实现了java.io.Serializable接口,意味着LinkedList支持序列化,能通过序列化去传输

四、TreeMap的属性

/**
 * 比较器:
 * - TreeMap是有序的,通过comparator接口对TreeMap排序进行控制
 * - 用键的自然排序,则比较器为null
 */
private final Comparator<? super K> comparator;

// 树的根节点
private transient Entry<K,V> root;

// 集合大小
private transient int size = 0;

// 树结构被修改的次数
private transient int modCount = 0;

五、TreeMap的构造函数

/**
 * 无参构造方法
 * - 默认比较机制,自然排序
 */
public TreeMap() {
    comparator = null;
}

/**
 * 自定义比较器的构造方法
 */
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

/**
 * 构造已知Map对象为TreeMap
 * - 默认比较机制
 */
public TreeMap(Map<? extends K, ? extends V> m) {
    comparator = null;
    putAll(m);
}

/**
 * 构造已知的SortedMap对象为TreeMap
 * - 使用已知对象的构造器
 */
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) {
    }
}

六、TreeMap的核心函数分析

1.put方法

public V put(K key, V value) {
    Entry<K,V> t = root;  // 获取根节点

    // 如果根节点为空，则该元素置为根节点 
    if (t == null) {
        compare(key, key); // type (and possibly null) check

        root = new Entry<>(key, value, null);
        size = 1;    // 集合大小为1
        modCount++;  // 结构修改次数自增
        return null;
    }

    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;  // 比较器对象

    // 如果比较器对象不为空，也就是自定义了比较器
    if (cpr != null) {   
        do { // 循环比较并确定元素应插入的位置(也就是找到该元素的父节点)
            parent = t;  // t就是root

            // 调用比较器对象的compare()方法，该方法返回一个整数
            cmp = cpr.compare(key, t.key); 
            if (cmp < 0)      // 待插入元素的key"小于"当前位置元素的key，则查询左子树
                t = t.left;
            else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的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)       // 待插入元素的key"小于"当前位置元素的key，则查询左子树
                t = t.left;
            else if (cmp > 0)  // 待插入元素的key"大于"当前位置元素的key，则查询右子树
                t = t.right;
            else               // "相等"则替换其value。
                return t.setValue(value);
        } while (t != null);
    }

    Entry<K,V> e = new Entry<>(key, value, parent);  // 根据key找到父节点后新建一个节点
    if (cmp < 0)  // 根据比较的结果来确定放在左子树还是右子树
        parent.left = e;
    else
        parent.right = e;
    fixAfterInsertion(e);
    size++;      // 集合大小+1
    modCount++;  // 集合结构被修改次数+1
    return null;
}

2.以getEntry方法为基础的获取元素方法,containsKey()、get()、remove()等

/**
 * 返回给定key的节点
 * - 如果不包含则返回null
 * @return
 * @throws ClassCastException
 * @throws NullPointerException
 */
final Entry<K,V> getEntry(Object key) {
    // 为了性能卸载基于比较器的版本
    // 如果有比较器,则调用通过比较器来比较key的方法
    if (comparator != null) {
        return getEntryUsingComparator(key);
    }
    if (key == null) {
        throw new NullPointerException();
    }
    @SuppressWarnings("unchecked")
    /*
     *  获取key的Comparable接口:
     *  super则是使用K或K的父类的compareTo方法
     *  如果用extends的话K的子类加了其他属性进行比较就没法进行比较了
      */
    Comparable<? super K> k = (Comparable<? super K>) key;
    // 从根节点开始比较,根据二叉树的形式,小了往左找,大了往右找,直到找到返回
    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;
}

3.以getFirstEntry、getLastEntry为基础的获取头尾元素方法,其中包含firstKey、lastKey、firstEntry、lastEntry、pollFirstEntry、pollLastEntry

/**
 * 返回TreeMap的第一个节点(最左侧的节点)
 * - 如果为空则返回null
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null) {
        while (p.left != null) {
            p = p.left;
        }
    }
    return p;
}

/**
 * 返回TreeMap的最后一个节点(最右侧节点)
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null) {
        while (p.right != null) {
            p = p.right;
        }
    }
    return p;
}

4.keySet()和entrySet()

/**
 * 返回key集合对象
 */
@Override
public Set<K> keySet() {
    return navigableKeySet();
}

/**
 * 返回NavigableSet对象,实际上返回的是当前对象的key集合
 */
@Override
public NavigableSet<K> navigableKeySet() {
    KeySet<K> nks = navigableKeySet;
    return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
}

/**
 * 获取TreeMap的Entry集合,实际上返回EntrySet类的对象
 */
@Override
public Set<Map.Entry<K,V>> entrySet() {
    EntrySet es = entrySet;
    return (es != null) ? es : (entrySet = new EntrySet());
}
/**
 * EntrySet是TreeMap所有键值对组成的集合
 * - EntrySet集合单位是单个键值对
 */
class EntrySet extends AbstractSet<Map.Entry<K,V>> {

5.computeRedLevel

/**
 * 计算完全二叉树的层数
 */
private static int computeRedLevel(int sz) {
    int level = 0;
    for (int m = sz - 1; m >= 0; m = m / 2 - 1) {
        level++;
    }
    return level;
}

把根节点的索引看为0,那么高度为2的树最后一个节点的索引为2;类推高度为3的最后一个节点为6,满足m=(m+1)*2.计算这个高度的好处
如果一个树有9个节点,那么我们构造红黑树的时候,只要把前面3层的节点都设置为黑色,第4层设置为红色,则构造完的树就是红黑树,是满足红黑树的5个条件
而实现的关键就是找到要构造树的完全二叉树的层数

6.buildFromSorted

/**
* level: 当前树的层数，注意：是从0层开始
* lo: 子树第一个元素的索引
* hi: 子树最后一个元素的索引
* redLevel: 上述红节点所在层数
* 剩下的3个就不解释了，跟上面的一样
*/
@SuppressWarnings("unchecked")
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 {
  // hi >= lo 说明子树已经构造完成
  if (hi < lo) return null;
  // 取中间位置，无符号右移，相当于除2
  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;
  // 通过迭代器获取key， 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;
    }
  // 通过流来读取key, value
  } else {
    key = (K) str.readObject();
    value = (defaultVal != null ? defaultVal : (V) str.readObject());
  }
  //构建结点
  Entry<K,V> middle =  new Entry<>(key, value, null);
  // level从0开始的，所以上述9个节点，计算出来的是3，实际上就是代表的第4层
  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;
}

buildFromSorted能这么构造是因为这是一个已经排序的map
具体构造顺序如下图:

七、TreeMap的内部类

1.keySet类

keySet继承于AbstractSet;实现了Set接口

/**
 * KeySet是TreeMap中所有key组成的集合
 * - 继承于AbstractSet而且实现了NavigableSet接口
 * @param <E>
 */
static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
    private final NavigableMap<E, ?> m;
    KeySet(NavigableMap<E,?> map) { m = map; }

    /**
     * 升序迭代器
     * @return
     */
    @Override
    public Iterator<E> iterator() {
        // 若是TreeMap对象,则调用TreeMap的迭代器keyIterator
        // 否则调用TreeMap的子类NavigableSubMap的迭代器keyIterator
        if (m instanceof TreeMap) {
            return ((TreeMap<E,?>)m).keyIterator();
        } else {
            return ((NavigableSubMap<E,?>)m).keyIterator();
        }
    }

    /**
     * 降序迭代器
     * @return
     */
    @Override
    public Iterator<E> descendingIterator() {
        // 若是TreeMap对象,则调用TreeMap的迭代器descendingKeyIterator
        // 否则调用TreeMap的子类NavigableSubMap的迭代器descendingKeyIterator
        if (m instanceof TreeMap) {
            return ((TreeMap<E,?>)m).descendingKeyIterator();
        } else {
            return ((NavigableSubMap<E,?>)m).descendingKeyIterator();
        }
    }

    @Override
    public int size() { return m.size(); }
    @Override
    public boolean isEmpty() { return m.isEmpty(); }
    @Override
    public boolean contains(Object o) { return m.containsKey(o); }
    @Override
    public void clear() { m.clear(); }
    @Override
    public E lower(E e) { return m.lowerKey(e); }
    @Override
    public E floor(E e) { return m.floorKey(e); }
    @Override
    public E ceiling(E e) { return m.ceilingKey(e); }
    @Override
    public E higher(E e) { return m.higherKey(e); }
    @Override
    public E first() { return m.firstKey(); }
    @Override
    public E last() { return m.lastKey(); }
    @Override
    public Comparator<? super E> comparator() { return m.comparator(); }
    @Override
    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();
        return (e == null) ? null : e.getKey();
    }
    @Override
    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();
        return (e == null) ? null : e.getKey();
    }
    @Override
    public boolean remove(Object o) {
        int oldSize = size();
        m.remove(o);
        return size() != oldSize;
    }
    @Override
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement, boolean toInclusive) {
        return new KeySet<>(m.subMap(fromElement, fromInclusive,
                toElement,   toInclusive));
    }
    @Override
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new KeySet<>(m.headMap(toElement, inclusive));
    }
    @Override
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new KeySet<>(m.tailMap(fromElement, inclusive));
    }
    @Override
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }
    @Override
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }
    @Override
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }
    @Override
    public NavigableSet<E> descendingSet() {
        return new KeySet<>(m.descendingMap());
    }

    @Override
    public Spliterator<E> spliterator() {
        return keySpliteratorFor(m);
    }
}

2.values类

values继承于AbstractCollection;继承于Collection,继承于Iterable

/**
 * Treemap值的集合对应的类
 * - 继承于AbstractCollection
 */
class Values extends AbstractCollection<V> {
    @Override
    public Iterator<V> iterator() {
        return new ValueIterator(getFirstEntry());
    }

    @Override
    public int size() {
        return TreeMap.this.size();
    }

    @Override
    public boolean contains(Object o) {
        return TreeMap.this.containsValue(o);
    }

    @Override
    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;
    }

    @Override
    public void clear() {
        TreeMap.this.clear();
    }

    @Override
    public Spliterator<V> spliterator() {
        return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
    }
}

3.EntrySet

/**
 * EntrySet是TreeMap所有键值对组成的集合
 * - EntrySet集合单位是单个键值对
 */
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    @Override
    public Iterator<Map.Entry<K,V>> iterator() {
        return new EntryIterator(getFirstEntry());
    }

    @Override
    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);
    }

    @Override
    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;
    }

    @Override
    public int size() {
        return TreeMap.this.size();
    }

    @Override
    public void clear() {
        TreeMap.this.clear();
    }

    @Override
    public Spliterator<Map.Entry<K,V>> spliterator() {
        return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
    }
}

4.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;

    /**
     * 使用给定的键、值、父节点、子连接和BLACK色创建新的节点
     */
    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }

    /**
     * 获取key
     */
    @Override
    public K getKey() {
        return key;
    }

    /**
     * 返回指定的key的value
     */
    @Override
    public V getValue() {
        return value;
    }

    /** 设置值 */
    @Override
    public V setValue(V value) {
        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    @Override
    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());
    }

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

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

八、TreeMap的遍历

Map没有迭代器,要将Map转化为Set,用Set的迭代器才能进行元素迭代
TreeMap的遍历方式一般分为两步:

先通过entrySet()或ketSet()或values()方法获得相应的集合
通过Iterator迭代器遍历上面得到的集合

1.遍历TreeMap的Entry

// 假设map是TreeMap对象  
// map中的key是String类型，value是Integer类型  
Integer integ = null;  
Iterator iter = map.entrySet().iterator();  
while(iter.hasNext()) {  
    Map.Entry entry = (Map.Entry)iter.next();  
    // 获取key  
    key = (String)entry.getKey();  
    // 获取value  
    integ = (Integer)entry.getValue();  
}

2.遍历TreeMap的key

// 假设map是TreeMap对象  
// map中的key是String类型，value是Integer类型  
String key = null;  
Integer integ = null;  
Iterator iter = map.keySet().iterator();  
while (iter.hasNext()) {  
        // 获取key  
    key = (String)iter.next();  
        // 根据key，获取value  
    integ = (Integer)map.get(key);  
}

3.遍历TreeMap的value

// 假设map是TreeMap对象  
// map中的key是String类型，value是Integer类型  
Integer value = null;  
Collection c = map.values();  
Iterator iter= c.iterator();  
while (iter.hasNext()) {  
    value = (Integer)iter.next();  
}