TreeMap
TreeMap基于NavigableMap接口，元素按照Comparable自然排序或按照提供的Comparator进行排序，使用时可以选择不同的构造方法来达到上述排序要求。
TreeMap提供时间复杂度为log(n)的基本操作(containsXXX、get、put、remove)。
请注意方法实现不是同步的，因此多线程操作时需要自己单独做同步处理
或者
SortedSet s = Collections.synchronizedSortedSet(new TreeMap(...))。
学习本节知识你需要掌握红黑二叉树的相关信息。/qqqq
创建TreeMap对象
// 单独的比较器(Comparator)，如果比较的对象实现了Comparable接口可以不设置这个参数
private final Comparator<? super K> comparator;
// 红-黑二叉树的根节点
private transient Entry<K,V> root;
public TreeMap(Comparator<? super K> comparator) {
// 请注意是按照key的规则排序
this.comparator = comparator;
}
添加键值对
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key);
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();
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;
}
可以发现TreeMap与其他Map添加键值对的方式并无二致，但是需要注意的是与其他Map的数据存储结构的巨大差异。
首先查看root的赋值，它的值代表红黑二叉树的根节点，首个添加的元素会被作为根节点。
如果继续添加元素，那么会根据Comparator或者Comparable来决定新元素插入的位置，以Comparator为例。
Comparator<? super K> cpr = comparator;
...
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);
...
do...while循环至少会执行一次，初次会将t赋值为root，即判断从根节点的左边还是右边进行插入。
- 将parent也指向t；
- 将key值与t.key进行compare方法比较；
- 如果compare方法比较的结果小于0，那么将t重新赋值为t.left，即从当前节点的左子树开始查找，然后再次执行1；
- 如果compare方法比较的结果大于0，；那么将t重新赋值为t.right，即从当前节点的右子树开始查找，然后再次执行1；
- 如果compare方法比较的结果等于0，那么将使用新值替换旧值，循环结束；
请注意循环结束的条件是向root的左或右查找直到left或right为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;
cmp的值与上一步的查找节点中的compare值一致，至此节点就被插入到对应的位置处。Comparable的实现方式与Comparator类似，略。
插入节点之后需要判断是否会导致红黑树失去平衡，即通过父节点的颜色来进行判断。
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
首先我们需要明确在节点插入之前，红黑树也是平衡的。从着色的方法来看，每个节点插入时默认的颜色为红色，尽管Entry的构造默认颜色为黑色，其他添加的情况具体可以查看红黑树的插入部分内容。
获取键值对
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
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) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
以Comparable的情况为例，将root(根节点)赋值给p，即从根节点开始判断遍历的方向。
- 将对象进行compareTo方法比较，值为cmp；
- 如果cmp小于0，那么将p赋值为p.left，从节点的左边开始查找，继续遍历；
- 如果cmp大于0，那么将p赋值为p.right，从节点的右边开始查找，继续遍历；
- 如果cmp等于0，说明已找到满足key条件的节点，遍历结束；
上述过程与put键值对时的查找算法一致，下面来看看Comparator的实现方式。
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;
}
可以看到代码与Comparable实现非常类似，只是比较方式从compareTo变成了compare，不在累述。
删除键值对
public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
首先查找到需要删除的Entry对象，如果Entry对象为null，说明未找到对应的节点，不需要执行删除操作。如果找到Entry对象，则执行删除操作。
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// 待删除的节点存在两个子节点(left和right)
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 这里需要注意待删除节点存在两个子节点的处理情况
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// 将替换节点的父节点指向待删除节点的父节点，为后面的删除做准备
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;
// 这里执行的是替换删除，而不是直接删除，将引用置空达到删除效果
p.left = p.right = p.parent = null;
// 删除节点为黑色很明显会破坏平衡，因此需要重新着色
if (p.color == BLACK)
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.entrySet().iterator()
public Set<Map.Entry<K,V>> entrySet() {
EntrySet es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
初次遍历时entrySet为空，将会进行创建。
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
.....
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator(getFirstEntry());
}
.....
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
找到最左子节点(这点很重要)，因为"小"的节点会被放到左边，这个地方的小并不一定是数字上的大小，指的是一种人为的排序方式。在代码上指的是那些在Comparator额compare方法中返回-1或Comparable对象的compareTo方法返回-1的值。
EntryIterator(Entry<K,V> first) {
super(first);
}
下面开始遍历Entry中的键值。
一般书写方式为：
while(iterator.hasNext()){
Entry next = iterator.next();
K key = next.getKey();
V value = next.getValue();
......
}
abstract class PrivateEntryIterator<T> implements Iterator<T> {
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
......
}
TreeMap中的EntryIterator继承自PrivateEntryIterator，其hasNext方法如上所述。
final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
......
public Map.Entry<K,V> next() {
return nextEntry();
}
}
abstract class PrivateEntryIterator<T> implements Iterator<T> {
......
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
next = successor(e);
lastReturned = e;
return e;
}
......
}
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;
}
}
注意successor方法第一次调用的参数传递的是整个二叉树中最左边的非空孩子节点(节点child)，同时还需要注意这种情况下child不会在存在左子节点。此时child、child右节点(如果存在的话)、child的父节点大小关系如下：
child < child右节点 < child父节点
在else if代码块中，先查找右孩子中最左子孩子(因为这是最小值)；在最后的else代码块中用于查找父节点，想想一下场景没有右孩子的节点遍历或是已经遍历完右的情形来理解这个else代码块。
假如没有右孩子：那么此时左节点已经遍历完毕，需要继续遍历父节点，while循环结束。
假如已经遍历完右节点：那么此时我们根据红黑二叉树的排序可知，此时右节点的父节点肯定遍历过了。因此下一个遍历节点为右节点的父父节点。
如此循环往复完成遍历操作。
其他
其他操作相对比较简单，不再累述。