本文基于jdk1.8进行分析。
TreeMap继承自AbstractMap 实现了NavigableMap接口，意味着它支持一系列的导航方法。比如返回有序的key集合。
此外其还实现了Cloneable, java.io.Serializable两个接口说明其是可以被克隆、序列化的。
TreeMap基于红黑树（Red-Black tree）实现。该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator 进行排序，具体取决于使用的构造方法。
【1】核心属性和构造
① 核心属性
//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制 //可以通过构造函数自定义比较器，也可以使用默认比较器 private final Comparator<? super K> comparator; //treeMap的根节点 private transient Entry<K,V> root = null; //容器大小 private transient int size = 0; //结构修改次数 private transient int modCount = 0; //红黑树结构 private static final boolean RED = false; private static final boolean BLACK = true; //继承自父类AbstractMap transient Set<K> keySet; transient Collection<V> values;
② 构造函数
默认构造函数，比较器为null。
public TreeMap() { comparator = null; }
指定比较器comparator
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，这里会同时绑定比较器与SortedMap元素。
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) { } }
③ 核心结点类型Entry
如下所示Entry是TreeMap的静态内部类实现了Map.Entry<K,V>接口。其除了key value外还维护了left、right、parent以及color(红还是黑)。这里没有看到prev、next表明**其底层数据结构是红黑树而非数组+链表**。
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;//父节点 // BLACK默认值是true boolean color = BLACK; Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } //... }
【2】获取方法
① get(Object key)
如下所示其通过getEntry(key)方法获取到P，然后返回p.value。
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); }
② getEntry
如果比较器不为null，则将行为交给getEntryUsingComparator方法实现。否则从root结点开始与目标key进行compareTo对比。
如果k.compareTo(p.key)<0，说明目标key小于对比结点p，则p=p.left;
如果k.compareTo(p.key)>0，说明目标key大于于对比结点p，则p=p.right;
如果k.compareTo(p.key)==0，说明目标key等于对比结点p，直接返回p;
否则，返回null。
final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; // 如果p == null ,直接返回null 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; }
③ getEntryUsingComparator
这个方法核心在于使用比较器来对比两个结点的key，而非采用目标对象的compareTo方法。本质仍然是对比，判断left还是right，更新p，进行下一步判断，直到找到合适的结点。否则就返回null。
final Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; }
④ getFirstEntry&getLastEntry
如下所示，其一路遍历找到最底层的left结点。也就是排序结果最小的一个结点(红黑树是二叉查找树哦)。
final Entry<K,V> getFirstEntry() { Entry<K,V> p = root; if (p != null) while (p.left != null) p = p.left; return p; }
与之对应的则是getLastEntry会一路找到最底层的right结点，也就是排序最大的结点。
final Entry<K,V> getLastEntry() { Entry<K,V> p = root; if (p != null) while (p.right != null) p = p.right; return p; }
⑤ getHigherEntry
返回大于目标K key的元素中最小的一个。
比如从(1 2 3 4 5)中找到大于目标key=2的元素中最小的为3，如果找不到则返回null。其实也就是找结点2的后继结点。
final Entry<K,V> getHigherEntry(K key) { Entry<K,V> p = root; while (p != null) { //compare方法要么采用比较器，要么采用对象自身的compareTo方法 int cmp = compare(key, p.key); if (cmp < 0) { if (p.left != null) p = p.left; else return p; } else { if (p.right != null) { p = p.right; } else { // 这里为什么不是返回null呢？给机会回溯， //能够找到其父节点作为后继结点返回 Entry<K,V> parent = p.parent; Entry<K,V> ch = p; //这里ch == parent.right很关键 while (parent != null && ch == parent.right) { ch = parent; parent = parent.parent; } return parent; } } } //否则就返回null return null; }
与之对应的则是getLowerEntry。仍旧以(1 2 3 4 5)为例，找到比3小的元素中最大的元素也就是2。
getLowerEntry本质就是找到当前结点的前驱结点，可能为null。
final Entry<K,V> getLowerEntry(K key) { Entry<K,V> p = root; while (p != null) { int cmp = compare(key, p.key); // k > p 往p的右侧找 if (cmp > 0) { if (p.right != null) p = p.right; else return p; } else { if (p.left != null) { p = p.left; } 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; } } } return null; }
【3】存放方法
① put
方法逻辑梳理如下：
- 判断根节点是否为null
- 如果比较器不为null，则使用比较器进行对比，尝试从left、right找到合适的结点(位置)
- 如果比较器为null，则使用对象自身的compareTo方法从根节点往下找到合适的结点(位置)
- 插入结点并进行处理
- 更新size、modCount
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; modCount++; return null; } // 记录key比较之后的大小 int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; //如果比较器不为null，使用比较器从left right找结点(位置) 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); } // 如果比较器为null，则使用对象自身的compareTo方法寻找 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); } // 到这里找到了当前parent cmp Entry<K,V> e = new Entry<>(key, value, parent); //插入e if (cmp < 0) parent.left = e; else parent.right = e; //这个很重要 会触发左旋和右旋 fixAfterInsertion(e); //更新size 、modCount size++; modCount++; return null; }
其结点结构只有left、right以及parent，没有prev、next也就是典型的树结构。遍历查找合适结点(位置)其实也就是树的遍历。这里特别需要注意的是插入后的操作，会触发红黑树的左旋和右旋。
② fixAfterInsertion
下面注释中符号释义：
- xp是x.parent，也就是父亲结点
- xpp 为xp的parent，也就是祖父结点
- xppl 为xpp的left，可能是XP也可能是叔叔结点；
- xppr 为 xpp的right ，可能是XP也可能是叔叔结点
- 这个过程会涉及到红黑树的左旋和右旋。
private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; //xp.color ==red while (x != null && x != root && x.parent.color == RED) { // xp==xp.parent.left 也就是左侧分支 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // y=xppr Entry<K,V> y = rightOf(parentOf(parentOf(x))); //xppr.color=red if (colorOf(y) == RED) { //xp.color=black setColor(parentOf(x), BLACK); //xppr.color=black setColor(y, BLACK); //xpp.color=red setColor(parentOf(parentOf(x)), RED); // x=xpp x = parentOf(parentOf(x)); } else { //x=xpr if (x == rightOf(parentOf(x))) { // 等价于rotateLeft(x=xp) x = parentOf(x); rotateLeft(x); } // xp.color=black setColor(parentOf(x), BLACK); // xpp.color=red setColor(parentOf(parentOf(x)), RED); //rotateRight(x) rotateRight(parentOf(parentOf(x))); } } else { //右侧分支 y=xppl Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) {//叔叔是红色，XP是红色，那么必然进行颜色调整 setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else {//可能是RL调整，也可能是RR调整 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; }
其实总结起来就是六种情况：
- 左侧分支，叔叔是红色，此时不发生结构调整，只需要改变父亲与叔叔结点颜色为黑色；
- 右侧分支，叔叔是红色，此时不发生结构调整，只需要改变父亲与叔叔结点颜色为黑色；
- LL调整
- LR调整
- RL调整
- RR调整
整体来讲这个过程其实就是红黑树的平衡过程。
另外和HashMap一样，删除结点后也要进行平衡。fixAfterDeletion方法可以参考HashMap的balanceDeletion方法。
