一、概念及概述
TreeMap 是一个有序的key-value集合，非同步，基于红黑树（Red-Black tree）实现，每个key-value作为红黑树的一个节点。
TreeMap存储时会进行排序的，会根据key来对key-value键值对进行排序，其中排序方式也是分为两种，一种是默认排序（按key的升序），一种是定制排序，具体取决于使用的构造方法。
二、插入
插入操作比较复杂一些，当往 TreeMap 中放入新的键值对后，可能会破坏红黑树的性质，在此只做简单说明
源码分析
public V put(K key, V value) {
Entry<K,V> t = root;
// 1.如果根节点为 null，将新节点设为根节点
if (t == null) {
compare(key, key);
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) {
// 2.为 key 在红黑树找到合适的位置
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 {
// 与上面代码逻辑类似，省略
}
Entry<K,V> e = new Entry<>(key, value, parent);
// 3.将新节点链入红黑树中
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 4.插入新节点可能会破坏红黑树性质，这里修正一下
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
put 方法代码如上，逻辑和二叉查找树插入节点逻辑一致。重要的步骤已经写了注释，并不难理解。插入逻辑的复杂之处在于插入后的修复操作，对应的方法fixAfterInsertion，该方法的源码和说明如下：
三、查找
TreeMap基于红黑树实现，而红黑树是一种自平衡二叉查找树，所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的，先将目标值和根节点的值进行比较，如果目标值小于根节点的值，则再和根节点的左孩子进行比较。如果目标值大于根节点的值，则继续和根节点的右孩子比较。在查找过程中，如果目标值和二叉树中的某个节点值相等，则返回 true，否则返回 false。TreeMap 查找和此类似，只不过在 TreeMap 中，节点（Entry）存储的是键值对<k,v>。在查找过程中，比较的是键的大小，返回的是值，如果没找到，则返回null。TreeMap 中的查找方法是get，具体实现在getEntry方法中。
相关源码如下：
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);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
// 查找操作的核心逻辑就在这个 while 循环里
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;
}
四、删除
删除操作是红黑树最复杂的部分，原因是该操作可能会破坏红黑树性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点），修复性质5要比修复其他性质（性质2和4需修复，性质1和3不用修复）复杂的多。
红黑树的五个特性：
1、节点是红色或黑色。
2、根是黑色。
3、所有叶子都是黑色（叶子是NIL节点）。
4、每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5、从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点（简称黑高）。
删除的相关源码如下：
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
/*
* 1. 如果 p 有两个孩子节点，则找到后继节点，
* 并把后继节点的值复制到节点 P 中，并让 p 指向其后继节点
*/
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
/*
* 2. 将 replacement parent 引用指向新的父节点，
* 同时让新的父节点指向 replacement。
*/
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;
// 3. 如果删除的节点 p 是黑色节点，则需要进行调整
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // 删除的是根节点，且树中当前只有一个节点
root = null;
} else { // 删除的节点没有孩子节点
// p 是黑色，则需要进行调整
if (p.color == BLACK)
fixAfterDeletion(p);
// 将 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;
}
}
}
简单用7个字总结：找后继 -> 替换 -> 修复。这三步中，最复杂的是修复操作。修复操作要重新使红黑树恢复平衡，修复操作的源码分析如下：
上面对 fixAfterDeletion 部分代码逻辑就行了分析，通过配图的形式解析了每段代码逻辑所处理的情况。
五、遍历
遍历操作也是大家使用频率较高的一个操作，对于TreeMap，使用方式一般如下：
for(Object key : map.keySet()) {
// do something
}
或者
for(Map.Entry entry : map.entrySet()) {
// do something
}
从上面代码片段中可以看出，大家一般都是对 TreeMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历keySet 方法产生的集合，在编译时会转换成用迭代器遍历，等价于：
Set keys = map.keySet();
Iterator ite = keys.iterator();
while (ite.hasNext()) {
Object key = ite.next();
// do something
}