TreeMap(JDK1，java零基础自学教程

本文主要是介绍TreeMap(JDK1，java零基础自学教程，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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;

}

查找操作的核心逻辑就是getEntry方法中的while循环，大家对照上面的说的流程，自己看一下吧，比较简单，就不多说了。

遍历

遍历操作也是大家使用频率较高的一个操作，对于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

}

另一方面，TreeMap 有一个特性，即可以保证键的有序性，默认是正序。所以在遍历过程中，大家会发现 TreeMap 会从小到大输出键的值。那么，接下来就来分析一下keySet方法，以及在遍历 keySet 方法产生的集合时，TreeMap 是如何保证键的有序性的。相关代码如下：

public Set keySet() {

return navigableKeySet();

}

public NavigableSet navigableKeySet() {

KeySet nks = navigableKeySet;

return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));

}

static final class KeySet extends AbstractSet implements NavigableSet {

private final NavigableMap<E, ?> m;

KeySet(NavigableMap<E,?> map) { m = map; }

public Iterator iterator() {

if (m instanceof TreeMap)

return ((TreeMap<E,?>)m).keyIterator();

else

return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();

}

// 省略非关键代码

}

Iterator keyIterator() {

return new KeyIterator(getFirstEntry());

}

final class KeyIterator extends PrivateEntryIterator {

KeyIterator(Entry<K,V> first) {

super(first);

}

public K next() {

return nextEntry().key;

}

}

abstract class PrivateEntryIterator implements Iterator {

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;

}

final Entry<K,V> nextEntry() {

Entry<K,V> e = next;

if (e == null)

throw new NoSuchElementException();

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

// 寻找节点 e 的后继节点

next = successor(e);

lastReturned = e;

return e;

}

// 其他方法省略

}

上面的代码比较多，keySet 涉及的代码还是比较多的，大家可以从上往下看。从上面源码可以看出 keySet 方法返回的是KeySet类的对象。这个类实现了Iterable接口，可以返回一个迭代器。该迭代器的具体实现是KeyIterator，而 KeyIterator 类的核心逻辑是在PrivateEntryIterator中实现的。上面的代码虽多，但核心代码还是 KeySet 类和 PrivateEntryIterator 类的 nextEntry方法。KeySet 类就是一个集合，这里不分析了。而 nextEntry 方法比较重要，下面简单分析一下。

在初始化 KeyIterator 时，会将 TreeMap 中包含最小键的 Entry 传给 PrivateEntryIterator。当调用 nextEntry 方法时，通过调用 successor 方法找到当前 entry 的后继，并让 next 指向后继，最后返回当前的 entry。通过这种方式即可实现按正序返回键值的的逻辑。

好了，TreeMap 的遍历操作就讲到这。遍历操作本身不难，但讲的有点多，略显啰嗦，大家见怪。

插入

相对于前两个操作，插入操作明显要复杂一些。当往 TreeMap 中放入新的键值对后，可能会破坏红黑树的性质。这里为了描述方便，把 Entry 称为节点。并把新插入的节点称为N，N 的父节点为P。P 的父节点为G，且 P 是 G 的左孩子。P 的兄弟节点为U。在往红黑树中插入新的节点 N 后（新节点为红色），会产生下面5种情况：

1. N 是根节点

2. N 的父节点是黑色

3. N 的父节点是红色，叔叔节点也是红色

4. N 的父节点是红色，叔叔节点是黑色，且 N 是 P 的右孩子

5. N 的父节点是红色，叔叔节点是黑色，且 N 是 P 的左孩子

上面5种情况中，情况2不会破坏红黑树性质，所以无需处理。情况1 会破坏红黑树性质2

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

（根是黑色），情况3、4、和5会破坏红黑树性质4（每个红色节点必须有两个黑色的子节点）。这个时候就需要进行调整，以使红黑树重新恢复平衡。至于怎么调整，可以参考红黑树详细分析，这里不再重复说明。接下来分析一下插入操作相关源码：

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 中最复杂的部分，也就是删除操作了。

删除

删除操作是红黑树最复杂的部分，原因是该操作可能会破坏红黑树性质5（从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点），修复性质5要比修复其他性质（性质2和4需修复，性质1和3不用修复）复杂的多。当删除操作导致性质5被破坏时，会出现8种情况。为了方便表述，这里还是先做一些假设。我们把最终被删除的节点称为 X，X 的替换节点称为 N。N 的父节点为P，且 N 是 P 的左孩子。N 的兄弟节点为S，S 的左孩子为 SL，右孩子为 SR。这里特地强调 X 是 最终被删除 的节点，是原因二叉查找树会把要删除有两个孩子的节点的情况转化为删除只有一个孩子的节点的情况，该节点是欲被删除节点的前驱和后继。

接下来，简单列举一下删除节点时可能会出现的情况，先列举较为简单的情况：

1. 最终被删除的节点 X 是红色节点

2. X 是黑色节点，但该节点的孩子节点是红色

比较复杂的情况：

1. 替换节点 N 是新的根

2. N 为黑色，N 的兄弟节点 S 为红色，其他节点为黑色。

3. N 为黑色，N 的父节点 P，兄弟节点 S 和 S 的孩子节点均为黑色。

4. N 为黑色，P 是红色，S 和 S 孩子均为黑色。

5. N 为黑色，P 可红可黑，S 为黑色，S 的左孩子 SL 为红色，右孩子 SR 为黑色

6. N 为黑色，P 可红可黑，S 为黑色，SR 为红色，SL 可红可黑

上面列举的8种情况中，前两种处理起来比较简单，后6种情况中情况26较为复杂。接下来我将会对情况26展开分析，删除相关的源码如下：

public V remove(Object key) {

Entry<K,V> p = getEntry(key);

if (p == null)

return null;

V oldValue = p.value;

deleteEntry§;

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.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;

这篇关于TreeMap(JDK1，java零基础自学教程的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！