之前公众号发布的文章中,《Java常用数据结构系列》漏了一章,就直接在掘金发布了。
TreeMap是一种带有排序功能的key-value存储结构,它是通过 红黑树 实现的。如果想学习TreeMap的内部细节操作(旋转平衡处理等),就必须充分学习红黑树。本文不关注红黑树操作的具体细节(大家自行补课),只分析TreeMap自身的特点。
先来看看TreeMap的继承关系:
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable 复制代码
entrySet()
主要说一下NavigableMap接口:
public interface NavigableMap<K,V> extends SortedMap<K,V> 复制代码
继承自SortedMap接口:
public interface SortedMap<K,V> extends Map<K,V> 复制代码
顾名思义,SortedMap的职责是排序,而NavigableMap的职责是在排好序的集合中进行各种导航搜索的。
看SortedMap中的关键方法:
/** * Returns the comparator used to order the keys in this map, or * {@code null} if this map uses the {@linkplain Comparable * natural ordering} of its keys. * * @return the comparator used to order the keys in this map, * or {@code null} if this map uses the natural ordering * of its keys */ Comparator<? super K> comparator(); 复制代码
comparator()
方法就是返回 比较器
的。从注释中可以看出,有两种排序方式:一种是自然排序(返回null),另一种则是自定义排序(返回Comparator实例)。
浏览一下NavigableMap中的部分导航方法。
// 返回小于key的第一个元素 Map.Entry<K,V> lowerEntry(K key); ... // 一系列类似方法 // 返回倒序集合 NavigableMap<K,V> descendingMap(); ... // 返回子集合,开闭区间 NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive); ... // 一系列类似方法 复制代码
首当其冲的当然是用来存储key-value键值对的存储结构了。
// 直接用布尔值来表示 private static final boolean RED = false; private static final boolean BLACK = true; 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是红黑树的树结点结构,和HashMap中的TreeNode稍有区别。
然后就是红黑树的相关操作了,这里仅简单说明,不做展开。
// 左旋:左子树不平衡时使用 private void rotateLeft(Entry<K,V> p) // 右旋:右子树不平衡时使用 private void rotateRight(Entry<K,V> p) // 插入新结点 public V put(K key, V value) // 插入新结点后的调整,保证新树还是红黑树 private void fixAfterInsertion(Entry<K,V> x) // 删除某个结点 private void deleteEntry(Entry<K,V> p) // 删除某个结点后的调整,保证新树还是红黑树 private void fixAfterDeletion(Entry<K,V> x) 复制代码
这里仅分析 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; 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; 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); } 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<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; // 插入为左子树 else parent.right = e; // 插入为右子树 fixAfterInsertion(e); // 红黑树调整 size++; modCount++; return null; } 复制代码
// 使用自然排序 public TreeMap() // 使用自定义排序 public TreeMap(Comparator<? super K> comparator) // 传的map不一定是有序的,所以调用的是putAll方法来进行添加 public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } // 传的map是有序的,需要做一些调整 public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException | ClassNotFoundException cannotHappen) { } } 复制代码
第三个和第四个构造方法的实现是不同的。在第三个构造方法中,不能保证传入的Map是有序的,所以需要调用putAll方法将元素一个一个添加到Map中。而第四个构造方法中,传入的就是一个有序的Map,所以直接将传入的Map转成红黑树了。
private void buildFromSorted(int size, Iterator<?> it, java.io.ObjectInputStream str, V defaultVal) throws java.io.IOException, ClassNotFoundException { this.size = size; // 将转换后的树的根结点赋值给TreeMap的根结点 // computeRedLevel可以理解为计算树的高度 root = buildFromSorted(0, 0, size-1, computeRedLevel(size), it, str, defaultVal); } 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); // extract key and/or value from iterator or stream 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; // 返回根结点 } 复制代码
这个转换方法是通过递归来将所有结点关联成一个红黑树的,且会返回根结点(其实就是中间点)。有意思的是,它只将最底层的结点设置成了红色,而其他结点都是黑色。这样是为了方便后续结点的插入。
TreeMap中所有迭代器子类都继承自 PrivateEntryIterator
:
abstract class PrivateEntryIterator<T> implements Iterator<T> { Entry<K,V> next; Entry<K,V> lastReturned; int expectedModCount; PrivateEntryIterator(Entry<K,V> first) { expectedModCount = modCount; lastReturned = null; next = first; } public final boolean hasNext() { return next != null; } // 下一个结点 final Entry<K,V> nextEntry() { ... next = successor(e); // 二叉树查找,主要查右子树 lastReturned = e; return e; } // 前一个结点 final Entry<K,V> prevEntry() { ... next = predecessor(e); // 二叉树查找,主要查左子树 lastReturned = e; return e; } public void remove() { ... } } 复制代码
直接看 successor
方法, predecessor
方法类似。
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; else if (t.right != null) { // 右子树不为空,即存在比当前结点大的结点 Entry<K,V> p = t.right; while (p.left != null) // 这里就需要查左子树了 p = p.left; return p; } else { // 右子树为空 Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { // 针对叶结点 ch = p; p = p.parent; } // 因为结点t可能是其父节点的左子树,也可能是右子树 return p; } } 复制代码
因为继承了AbstractMap,所以必须实现 entrySet()
方法:
public Set<Map.Entry<K,V>> entrySet() { EntrySet es = entrySet; return (es != null) ? es : (entrySet = new EntrySet()); } class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>> iterator() { // 把红黑树的最小结点作为迭代器的第一个结点 return new EntryIterator(getFirstEntry()); } ... } final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> { EntryIterator(Entry<K,V> first) { super(first); } public Map.Entry<K,V> next() { return nextEntry(); } } 复制代码
EntrySet继承了AbstractSet,其中 iterator()
方法返回了 EntryIterator
,它直接就继承了 PrivateEntryIterator
接口。类似的迭代器还有: ValueIterator
、 KeyIterator
和 DescendingKeyIterator
。
TreeMap中有很多导航方法,比如: lowerEntry
、 lowerKey
、 tailMap
等等,方法本身实现没有什么要说的。如果你仔细阅读源码,你会发现有下面这两种方法(还有类似的):
public Map.Entry<K,V> lowerEntry(K key) { return exportEntry(getLowerEntry(key)); } final Entry<K,V> getLowerEntry(K key) { ... } 复制代码
为什么给出两个方法?明明 getLowerEntry
就可以拿到Entry了。其实, lowerEntry
才是对外接口,而 getLowerEntry
是内部接口。因为 getLowerEntry
拿到的Entry是可读写的,而TreeMap不希望开发人员修改返回的Entry,所以多做了一层处理,让返回的Entry只能读。关键在 exportEntry
方法:
static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) { return (e == null) ? null : new AbstractMap.SimpleImmutableEntry<>(e); } 复制代码
可以看到,直接强转成了 SimpleImmutableEntry
,它是AbstractMap实现的一个不可变Entry,它的 setValue
方法会抛出 UnsupportedOperationException
异常。
TreeMap由红黑树实现,它是有序的,所以它可以反向:
private transient NavigableMap<K,V> descendingMap; public NavigableMap<K, V> descendingMap() { NavigableMap<K, V> km = descendingMap; return (km != null) ? km : (descendingMap = new DescendingSubMap<>(this, true, null, true, true, null, true)); } 复制代码
那如何反向呢?
static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> { ... // 直接反转比较器 private final Comparator<? super K> reverseComparator = Collections.reverseOrder(m.comparator); ... } 复制代码
在 DescendingSubMap
中,可以发现,所谓反向其实只需要反转比较器就可以了。
既然可以反向,那TreeMap就可以进行逆序遍历和迭代。