前言
TreeMap的底层数据结构是红黑树，对数据结构不熟悉的话可以先看
【红黑树的插入】这篇文章
TreeMap的继承体系
TreeMap实现了Map、SortedMap、NavigableMap、Cloneable、Serializable等接口。SortedMap规定了元素可以按key的大小来遍历，它定义了一些返回部分map的方法。
SortedMap
public interface SortedMap<K,V> extends Map<K,V> {
/**
* key的比较器
*/
Comparator<? super K> comparator();
/**
* 返回大于等于fromKey小于等于toKey的元素组成的子map
*/
SortedMap<K,V> subMap(K fromKey, K toKey);
/**
* 返回小于toKet的子map
*/
SortedMap<K,V> headMap(K toKey);
/**
* 返回大于等于fromKey的子map
*/
SortedMap<K,V> tailMap(K fromKey);
/**
* 返回最小的key
*/
K firstKey();
/**
* 返回最大的key
*/
K lastKey();
/**
* 返回key的集合
*/
Set<K> keySet();
/**
* 返回value的集合
*/
Collection<V> values();
/**
* 返回节点集合
*/
Set<Map.Entry<K, V>> entrySet();
}
NavigableMap
public interface NavigableMap<K,V> extends SortedMap<K,V> {
/**
* 返回小于key的最大节点
*/
Map.Entry<K,V> lowerEntry(K key);
/**
* 返回小于key的最大key
*/
K lowerKey(K key);
/**
* 返回小于等于key的最大节点
*/
Map.Entry<K,V> floorEntry(K key);
/**
* 返回小于等于key的最大key
*/
K floorKey(K key);
/**
* 返回大于等于key的最小节点
*/
Map.Entry<K,V> ceilingEntry(K key);
/**
* 返回大于等于key的最小key
*/
K ceilingKey(K key);
/**
* 返回大于key的最小节点
*/
Map.Entry<K,V> higherEntry(K key);
/**
* 返回大于key的最小key
*/
K higherKey(K key);
/**
* 最小节点
*/
Map.Entry<K,V> firstEntry();
/**
* 最大节点
*/
Map.Entry<K,V> lastEntry();
/**
* poll出最小节点
*/
Map.Entry<K,V> pollFirstEntry();
/**
* poll出最大节点
*/
Map.Entry<K,V> pollLastEntry();
/**
* 返回倒叙的map
*/
NavigableMap<K,V> descendingMap();
/**
* 返回有序的key集合
*/
NavigableSet<K> navigableKeySet();
/**
* 返回倒序的key集合
*/
NavigableSet<K> descendingKeySet();
/**
* 返回从fromKey到toKey的子map，是否包含起止元素可以通过toInclusive设置
*/
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
/**
* 返回小于toKey的子map，是否包含toKey自己决定
*/
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
/**
* 返回大于fromKey的子map，是否包含fromKey通过inclusive设置
*/
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
/**
* 等价于 subMap(fromKey, true, toKey, false)
*/
SortedMap<K,V> subMap(K fromKey, K toKey);
/**
* 等价于 headMap(toKey, false)
*/
SortedMap<K,V> headMap(K toKey);
/**
* 等价于 tailMap(fromKey, true)
*/
SortedMap<K,V> tailMap(K fromKey);
}
TreeMap的存储结构
TreeMap只使用到了红黑树，所以它的时间复杂度为O(log n)。红黑树的特性：
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。（注意：叶子节点是指为空(NIL或NULL)的叶子节点！）
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
属性
/**
* 比较器，如果没传则key要实现Comparable接口
*/
private final Comparator<? super K> comparator;
/**
* root节点
*/
private transient Entry<K,V> root;
/**
* 元素的个数
*/
private transient int size = 0;
/**
* 操作次数
*/
private transient int modCount = 0;
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;
// 节点颜色，黑色为false
boolean color = BLACK;
}
构造方法
/**
* 默认构造方法，key必须实现Comparable接口
*/
public TreeMap() {
comparator = null;
}
/**
* 传入comparator，比较两个key的大小
*/
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 带map参数构造方法，把map所有元素保存到新的treeMap中
*/
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
/**
* 使用传入map的比较器，并把传入map中的所有元素保存到新的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) {
}
}
get方法
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// 如果当前treemap比较器不为空，使用比较器来进行比较返回
if (comparator != null)
return getEntryUsingComparator(key);
// 判断key是否为空，为空的话抛出异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
// 设置父节点为root节点，如果root节点为空，说明TreeMap是空的。
Entry<K,V> p = root;
// 循环节点信息，判断是否为空
while (p != null) {
// 输入的key和当前节点比较
int cmp = k.compareTo(p.key);
// 当前key小于p节点，设置p节点为p的left节点
if (cmp < 0)
p = p.left;
// 当前key大于p节点，设置p节点为p的right节点
else if (cmp > 0)
p = p.right;
// 相等的话返回p节点
else
return p;
}
return null;
}
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
// 定义key
K k = (K) key;
// 定义比较器
Comparator<? super K> cpr = comparator;
if (cpr != null) {
// 设置p节点为root节点
Entry<K,V> p = root;
// 循环p节点
while (p != null) {
// 比较p节点和输入节点k
int cmp = cpr.compare(k, p.key);
// k节点小于p，则进行设置p为p的left节点
if (cmp < 0)
p = p.left;
// k节点大于p，则进行设置p为p的right节点
else if (cmp > 0)
p = p.right;
// 相等返回p
else
return p;
}
}
return null;
}
- 从root节点开始遍历整个树。
- 根据查找的key进行比较，如果key大于当前节点，那么在左侧进行查找；如果key小于当前节点，那么在右侧进行查找；相等的话直接返回。
- treemap根据是否有comparator分化成了两个方法，但是内部逻辑是一样的。
左旋
左旋过程
- G节点的右节点将设置为原P节点的左节点。（如果B节点为空，将设置G节点的右节点为null，不为空将进行绑定B节点的父节点为G节点。）
- P节点的父节点将设置为原G节点的父节点。(如果原G节点是Root节点，将设置P节点为Root节点。)
- P节点的左节点将设置为原G节点。（绑定G的父节点为P。）
TreeMap中的左旋
/**
* p为上图中的G节点
*/
private void rotateLeft(Entry<K,V> p) {
// 首先判断p节点是否为空
if (p != null) {
// p的右节点r，即为P
Entry<K,V> r = p.right;
// 设置G的节点为P的左节点
p.right = r.left;
// 判断P的左节点是否为空，不为空进行绑定，P的左节点的父亲节点为G节点
if (r.left != null)
r.left.parent = p;
// 设置P节点的父节点为G节点的父亲节点
r.parent = p.parent;
// 判断G节点的父亲节点是否为空
// 如果为空说明原来的G节点是Root节点
// 那么也就设置P节点为Root节点
if (p.parent == null)
root = r;
// 判断原有的G节点是否是G的父亲节点左子节点
else if (p.parent.left == p)
p.parent.left = r;
// 判断原有的G节点是否是G的父亲节点右子节点
else
p.parent.right = r;
// 设置P的左节点为G
r.left = p;
// 设置G的父亲节点为P
p.parent = r;
}
}
右旋
右旋过程
- G节点的左节点将设置为P节点的右节点C。(如果C节点不为空，将绑定C节点的父亲节点为G)
- P节点的父节点将设置为原G节点的父节点。(如果原G节点是Root节点，将设置P节点为Root节点。)
- P节点的左节点将设置为原G节点的左子节点B。（如果B节点不为空，将设置B节点的父亲节点为P）
TreeMap中的右旋
/**
* p为上图中的G节点
*/
private void rotateRight(Entry<K,V> p) {
if (p != null) {
// p的左节点l，既为P节点
Entry<K,V> l = p.left;
// 设置G节点的左节点为P节点的右节点
p.left = l.right;
// 如果P节点的右节点不为空
// 则绑定P节点的右节点的父亲节点为G节点
if (l.right != null) l.right.parent = p;
// 设置P节点的父亲节点为G节点的父亲节点
l.parent = p.parent;
// 如果G节点的父亲节点为空
// 设置P节点为Root节点
if (p.parent == null)
root = l;
// 如果G是父亲节点的右子节点，设置原G的父亲的右子节点为P
else if (p.parent.right == p)
p.parent.right = l;
// 如果G是父亲节点的左子节点，设置原G的父亲的左子节点为P
else p.parent.left = l;
// P节点的右节点为G
l.right = p;
// G节点的父亲节点为P
p.parent = l;
}
}
