Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
1.总结
1.TreeMap数据结构：红黑树
2.有序的key-value映射，key必须可以自然排序的，否则就要自定义比较器Comparator作为参数传入
3.默认key不可以为null，因为要通过key排序
2.继承关系图
TreeMap.png
3.源码分析
3.1成员变量分析
// key的比较器
private final Comparator<? super K> comparator;
// 红黑树的根节点
private transient Entry<K,V> root;
// treeMap的大小
private transient int size = 0;
// 树修改的次数
private transient int modCount = 0;
// 键值对集合
private transient EntrySet entrySet;
// 键集合
private transient KeySet<K> navigableKeySet;
// 降序的NavigableMap
private transient NavigableMap<K,V> descendingMap;
3.2构造方法分析
public TreeMap() {
comparator = null;
}
/**
* 自定义比较器comparator
*/
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) {
}
}
没啥好深究的，一般都是用默认的构造方法
3.3常用方法分析
1.put方法
public V put(K key, V value) {
// 将根节点赋值给t
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // 默认要通过比较key进行排序，所以key不能为null，否则空指针异常
// 如果根节点为null，则新增元素节点就是根节点
// 此时不用调整红黑树，新增结束
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// 使用自定义比较器进行比较
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);
// k < t.key
if (cmp < 0)
t = t.left;
// k > t.key
else if (cmp > 0)
t = t.right;
// k = t.key，由于key不能重复，所以这里更新节点数据
else
return t.setValue(value);
} while (t != null); // 直到找到的子节点为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;
}
- 如果红黑树为null，则之间新建一个Entry节点，并设置为根节点root
- 检查comparator是否为null，不为null则使用comparator比较key的大小，否则使用k.compareTo(t.key)比较；遍历红黑树，找到对应的key，更新value
- 如果没有找到，则新建一个Entry节点添加到树上，然后执行fixAfterInsertion(e)，确保新增节点后仍是红黑树
- 关于fixAfterInsertion方法调整红黑树比较复杂，这里不再展开，我会在数据结构中更新红黑树的分析
2.putAll方法
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
// 针对将一个非空的SortedMap加入空的TreeMap且比较器相同的情况做了优化
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
buildFromSorted(mapSize, map.entrySet().iterator(),
null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
return;
}
}
// 否则，直接遍历给定map，将每一个节点添加到TreeMap上
super.putAll(map); // 会循环调用put方法
}
3.get(key)方法
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
// 使用指定比较器遍历红黑树
return getEntryUsingComparator(key);
// key为null时，抛出空指针异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 从根节点开始遍历红黑树
while (p != null) {
// 将给定k与树的节点的key比较
int cmp = k.compareTo(p.key);
if (cmp < 0) // < 0则遍历左子树
p = p.left;
else if (cmp > 0)
p = p.right; // > 0则遍历右子树
else
return p; // 相等表示找到节点
}
return null; // 否则没有该节点，返回null
}
4.remove()方法
public V remove(Object key) {
Entry<K,V> p = getEntry(key); // 根据key查找节点
if (p == null)
return null;
V oldValue = p.value;
// 删除节点
deleteEntry(p);
return oldValue;
}
/**
* p：待删除节点
*/
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) { // p有左右节点
// 得到p的后继节点；得到的是p的右子树的最左节点(大于当前节点的最小节点)
Entry<K,V> s = successor(p);
// 修改p的key和value，并将p指向s
p.key = s.key;
p.value = s.value;
p = s; // 经过上述操作其实已经将p删除，p节点的内容已经变为s节点的内容
} // p has 2 children
// Start fixup at replacement node, if it exists.
// p == s，replacement为p(s)的左孩子或右孩子；如果上面进入了if代码块，这里得到的一定是右孩子
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// 1.具有孩子节点的情况
if (replacement != null) {
// 修改replacement的父节点指向p的父节点
replacement.parent = p.parent;
if (p.parent == null) // 表示删除的根节点
// 孩子节点成为根节点
root = replacement;
else if (p == p.parent.left)
// 只有进入上面的if代码块才可能进入这个代码块
// 此时replacement为p的右孩子，将p的父节点的左孩子指向replacement
p.parent.left = replacement;
else
// 否则，p的父节点的右孩子指向replacement
p.parent.right = replacement;
// 将p节点删除
p.left = p.right = p.parent = null;
if (p.color == BLACK)
// 如果p的颜色为黑色，需要调整红黑树的平衡
fixAfterDeletion(replacement);
} else if (p.parent == null) { // 删除的是根节点且只有一个节点
root = null;
} else { // 删除的节点没有孩子节点
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;
}
}
}
TreeMap的红黑树结构操作比较复杂，没有红黑树基础建议先看看红黑树的知识。
如果不深究的话，知道TreeMap的存储结构，并且key不可以为null，默认以key的升序排序就足够了。
