首页 > 代码库 > 【源码】TreeMap源码剖析
【源码】TreeMap源码剖析
注:以下源码基于jdk1.7.0_11
之前介绍了一系列Map集合中的具体实现类,包括HashMap,HashTable,LinkedHashMap。这三个类都是基于哈希表实现的,今天我们介绍另一种Map集合,TreeMap。TreeMap是基于红黑树实现的。
介绍TreeMap之前,回顾下红黑树的性质:
首先,我们要明确,红黑树是一种二叉排序树,而且是平衡二叉树。因而红黑树具有排序树的所有特点,任意结点的左子树(如果有的话)的值比该结点小,右子树(如果有的话)的值比该结点大。二叉排序树各项操作的平均时间复杂度为O(logn),但是最坏情况下,二叉排序树会退化成单链表,此时时间复杂度为O(n),红黑树在二叉排序树的基础上,对其增加了一系列约束,使得其尽可能地平衡,红黑树的查询和更新的时间复杂度为O(logn)。
红黑树的五条性质:
1.每个结点要么是红色,要么是黑色;
2.根结点为黑色;
3.叶结点为黑色(空结点);
4.若一个结点为红色,则其子结点为黑色;
5.每个叶结点到根结点的路径中黑色结点的数目一致(黑高度相同)。
红黑树的查询操作与二叉排序树相同,重点是其插入和删除操作。红黑树的插入和删除操作在二叉排序树的基础上增加了修复操作,因为插入和删除可能会导致树不再满足红黑树性质,这时候会通过着色、旋转操作对其进行修复。
下面来看TreeMap的实现。
类声明:
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
TreeMap同样继承AbstractMap,但是它实现了NavigableMap接口,而NavigableMap接口继承自SortedMap接口。
TreeMap有四个成员变量,其中root是红黑树的根结点,由于红黑树的查询和更新操作需要比较,故而有个比较器comparator,默认情况下,comparator为空,这就要求我们的键必须实现Comparable接口,以定义比较规则。
private final Comparator<? super K> comparator;//比较器 private transient Entry<K,V> root = null;//树根 /** * The number of entries in the tree */ private transient int size = 0;//大小 /** * The number of structural modifications to the tree. */ private transient int modCount = 0;//修改次数
构造器:
public TreeMap() { comparator = null;//比较器为空 } public TreeMap(Comparator<? super K> comparator) {//传入比较器 this.comparator = comparator; } public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } 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的查询和更新操作之前,我们先看下Entry的实现,其实我们都可以猜到,Entry既然是TreeMap存储的结点,那么其必然包括如下几个域:数据(键、值)、父结点、左孩子、右孩子、颜色。事实正是如此:
static final class Entry<K,V> implements Map.Entry<K,V> { K key;//键 V value;//值 Entry<K,V> left = null;//左孩子 Entry<K,V> right = null;//右孩子 Entry<K,V> parent;//父结点 boolean color = BLACK;//默认颜色 /** * Make a new cell with given key, value, and parent, and with * {@code null} child links, and BLACK color. */ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = http://www.mamicode.com/value;>
下面来看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 {//如果没有定义比较器,那么key必须实现Comparable接口 if (key == null)//不允许空键 throw new NullPointerException(); 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; }明确以下几点:1.TreeMap的查询和更新操作都涉及到比较操作,故而TreeMap的键必须实现Comparable接口或者构造时得传入比较器(既实现了Comparable接口又传入了比较器情况下,比较器优先);2.put操作不允许null键,但是值(value)允许为null;3.键重复的情况下,新值会覆盖掉旧值。再看get方法:public V get(Object key) {//查询操作 Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); }
调用getEntry方法查询指定键值: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(); Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) {//根据Comparable接口定义的比较规则查找 int cmp = k.compareTo(p.key); if (cmp < 0)//待查结点在左子树 p = p.left; else if (cmp > 0)//待查结点在右子树 p = p.right; else return p; } return null;//没找到 } 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) { 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; }对比HashMap近乎O(1)的查找复杂度,TreeMap显得略有不足。再看remove删除操作:public V remove(Object key) { Entry<K,V> p = getEntry(key);//首先找到待删结点 if (p == null) return null; V oldValue = http://www.mamicode.com/p.value;>
虽然看上去寥寥几行代码,其实逻辑十分复杂,具体体现在删除结点后的恢复操作。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) {//p的左右孩子都存在 Entry<K,V> s = successor(p);//找到p的直接后继(顺着p右子树一直向左) p.key = s.key;//用直接后继替代p p.value = http://www.mamicode.com/s.value;>successtor函数用于找一个结点的中序后继(参见之前写的一篇如何得到一个结点的中序后继,算法一致):迭代器遍历操作正是基于successtor操作完成的。所以遍历TreeMap得到的键值对是有序的。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; } return p; } }
对称地,还有个查找直接前驱的函数:static <K,V> Entry<K,V> predecessor(Entry<K,V> t) { if (t == null) return null; else if (t.left != null) {//若存在左子树 Entry<K,V> p = t.left; while (p.right != null)//顺着左子树,向右搜索 p = p.right; return p; } else { Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } }注:文章故意忽略了更新操作中涉及到的红黑树修复动作(着色,旋转),此部分内容较为复杂,作者目前也没有完全吃透。总结:1.TreeMap的实现基于红黑树;2.TreeMap不允许插入null键,但允许null值;3.TreeMap线程不安全;4.插入结点时,若键重复,则新值会覆盖旧值;5.TreeMap要求key必须实现Comparable接口,或者初始化时传入Comparator比较器;6.遍历TreeMap得到的结果集是有序的(中序遍历);7.TreeMap的各项操作的平均时间复杂度为O(logn).【源码】TreeMap源码剖析
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。