概述
从API文档上我们可以知道,TreeMap是基于红黑树(Red-Black tree)来实现的,该数据结构最重要的特点就是可排序。默认情况下根据key的自然顺序进行排序,不过我们也可以自定义排序的顺序。
至于红黑树的相关实现,就先不讲了,由于有些复杂,并且本人对红黑树还没有完成吃透,但红黑树的性质大家起码还是要知道的。
继承关系
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
// NavigableMap接口继承了SortedMap
public interface NavigableMap<K,V> extends SortedMap<K,V> {
TreeMap实现了NavigableMap接口,而通过查看NavigableMap则是继承了SortedMap接口。由此我们可以知道,TreeMap排序的功能是基于NavigableMap也就是SortedMap的。
NavigableMap,这个接口翻译过来可以理解为导航相关,该接口提供了许多个导航相关的方法,比如lowerKey,ceilingKey,higherKey等,同样,TreeMap实现该接口后,除了实现这些方法,也自定义类了一些导航相关的方法,大家可自行根据API进行查看。
而这些排序相关的操作,基本上都离不开JDK排序相关的两个接口:Comparator和Comparable。
属性
/**
* 比较器
*/
private final Comparator<? super K> comparator;
/**
* 红黑树的红黑节点
*/
private transient Entry<K,V> root;
/**
* 容量大小
*/
private transient int size = 0;
/**
* 结构性修改
*/
private transient int modCount = 0;
/**
* 红黑树节点类型
*/
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;
}
// 红黑树节点-红颜色
private static final boolean RED = false;
// 红黑树节点-黑颜色
private static final boolean BLACK = true;
构造方法
/**
* 默认构造器,使用默认排序机制
*/
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,并使用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) {
}
}
方法
put方法
/**
* 红黑树的put操作大体上分为两步:构建二叉排序树,平衡二叉排序树
* 构建的时候,如果用户自定义了比较器,则会按照用户定义的规则来,否则将按照默认的比较规则来插入数据;
*/
public V put(K key, V value) {
// 二叉树当前节点
Entry<K,V> t = root;
// 如果二叉树为null,直接插入
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
// 使用cmp来表示排序返回的结果
int cmp;
// 父节点
Entry<K,V> parent;
// 比较器
Comparator<? super K> cpr = comparator;
// 如果比较器不为空,按照用户指定比较器进行循环比较,确定元素插入位置
if (cpr != null) {
do {
parent = t;
// 对key进行比较
cmp = cpr.compare(key, t.key);
// 比较结果小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点
if (cmp < 0)
t = t.left;
// 比较结果大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点
else if (cmp > 0)
t = t.right;
// 比较结果等于0,说明key相等,覆盖旧值,返回新值
else
return t.setValue(value);
} while (t != null);
}
// 如果比较器为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);
}
// 新增节点设为parent的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
// 如果新增节点的key小于parent的key,则当做左子节点
if (cmp < 0)
parent.left = e;
// 否则,右子节点
else
parent.right = e;
// 插入完成,对二叉树进行平衡操作
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
get方法
/**
* get方法相对简单些,只是对二叉树的比较遍历而已
*/
final Entry<K,V> getEntry(Object key) {
// 如果比较器不为空,则按照自定义规则遍历二叉树
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;
// 按照默认比较规则遍历二叉树
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;
}
remove方法
/**
* 这里删除操作其实很微妙,并不是直接删除,而是用被删除节点的后继节点来代替被删掉的节点,然后修复被删除节点的结构来进行操作的
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// p节点为要删除的节点,如果p节点的左右子节点都不为空
if (p.left != null && p.right != null) {
// 找到p节点的后继节点,这里不是直接删除p节点,而是将p的后继节点来代替要删除的节点,然后再进行修复操作
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// 开始修复操作
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;
}
}
}
/**
* 获取后继节点,其实这是一个类似中序遍历的方式
*/
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;
}
}
获取后继节点可参考:
Java TreeMap工作原理及实现
如果要深入理解TreeMap的红黑树实现,可以搜索《史上最简单清晰的红黑树讲解》系列博客。
文章参考自:
TreeMap源码分析(jdk1.8)
网友评论