/**

返回最大的键 maxKey，且 maxKey 仅小于参数 key

*/

K lowerKey(K key);

/**

返回最小的键 minKey，且 minKey 仅大于参数 key

*/

K higherKey(K key);

// 其他略

通过这些导航方法，我们可以快速定位到目标的 key 或 Entry。至于 SortedMap 接口，这个接口提供了一些基于有序键的操作，比如

/**

返回包含键值在 [minKey, toKey) 范围内的 Map

*/

SortedMap headMap(K toKey));

/**

返回包含键值在 [fromKey, toKey) 范围内的 Map

*/

SortedMap subMap(K fromKey, K toKey);

// 其他略

以上就是两个接口的介绍，很简单。至于 AbstractMap 和 Map 这里就不说了，大家有兴趣自己去看看 Javadoc 吧。关于 TreeMap 的继承体系就这里就说到这，接下来我们进入细节部分分析。

源码分析

JDK 1.8中的TreeMap源码有两千多行，还是比较多的。本文并不打算逐句分析所有的源码，而是挑选几个常用的方法进行分析。这些方法实现的功能分别是查找、遍历、插入、删除等，其他的方法小伙伴们有兴趣可以自己分析。TreeMap实现的核心部分是关于红黑树的实现，其绝大部分的方法基本都是对底层红黑树增、删、查操作的一个封装。如简介所说，只要弄懂了红黑树原理，TreeMap 就没什么秘密了。关于红黑树的原理，红黑树详细分析，本篇文章不会对此展开讨论。

查找

TreeMap基于红黑树实现，而红黑树是一种自平衡二叉查找树，所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的，先将目标值和根节点的值进行比较，如果目标值小于根节点的值，则再和根节点的左孩子进行比较。如果目标值大于根节点的值，则继续和根节点的右孩子比较。在查找过程中，如果目标值和二叉树中的某个节点值相等，则返回 true，否则返回 false。TreeMap 查找和此类似，只不过在 TreeMap 中，节点（Entry）存储的是键值对。在查找过程中，比较的是键的大小，返回的是值，如果没找到，则返回null。TreeMap 中的查找方法是get，具体实现在getEntry方法中，相关源码如下：

public V get(Object key) {

Entry p = getEntry(key);

return (p==null ? null : p.value);

}

final Entry 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 k = (Comparable) key;

Entry 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 m;

KeySet(NavigableMap map) { m = map; }

public Iterator iterator() {

if (m instanceof TreeMap)

return ((TreeMap)m).keyIterator();

else

return ((TreeMap.NavigableSubMap)m).keyIterator();

}

// 省略非关键代码

}

Iterator keyIterator() {

return new KeyIterator(getFirstEntry());

}

final class KeyIterator extends PrivateEntryIterator {

KeyIterator(Entry first) {

super(first);

}

public K next() {

return nextEntry().key;

}

}

abstract class PrivateEntryIterator implements Iterator {

Entry next;

Entry lastReturned;

int expectedModCount;

PrivateEntryIterator(Entry first) {

expectedModCount = modCount;

lastReturned = null;

next = first;

}

public final boolean hasNext() {

return next != null;

}

final Entry nextEntry() {

Entry 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种情况：

N 是根节点 N 的父节点是黑色 N 的父节点是红色，叔叔节点也是红色 N 的父节点是红色，叔叔节点是黑色，且 N 是 P 的右孩子 N 的父节点是红色，叔叔节点是黑色，且 N 是 P 的左孩子

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

public V put(K key, V value) {

Entry t = root;

// 1.如果根节点为 null，将新节点设为根节点

if (t == null) {

compare(key, key);

root = new Entry<>(key, value, null);

size = 1;

modCount++;

return null;

}

int cmp;

Entry parent;

// split comparator and comparable paths

Comparator 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 e = new Entry<>(key, value, parent);

// 3.将新节点链入红黑树中

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数同学面临毕业设计项目选题时，很多人都会感到无从下手，尤其是对于计算机专业的学生来说，选择一个合适的题目尤为重要。因为毕业设计不仅是我们在大学四年学习的一个总结，更是展示自己能力的重要机会。

因此收集整理了一份《2024年计算机毕业设计项目大全》，初衷也很简单，就是希望能够帮助提高效率，同时减轻大家的负担。

既有Java、Web、PHP、也有C、小程序、Python等项目供你选择，真正体系化！

由于项目比较多，这里只是将部分目录截图出来，每个节点里面都包含素材文档、项目源码、讲解视频

如果你觉得这些内容对你有帮助，可以添加VX：vip1024c （备注项目大全获取）

目选题时，很多人都会感到无从下手，尤其是对于计算机专业的学生来说，选择一个合适的题目尤为重要。因为毕业设计不仅是我们在大学四年学习的一个总结，更是展示自己能力的重要机会。**

因此收集整理了一份《2024年计算机毕业设计项目大全》，初衷也很简单，就是希望能够帮助提高效率，同时减轻大家的负担。 [外链图片转存中…(img-IK9oj1ul-1712537652751)] [外链图片转存中…(img-CaIrRwHI-1712537652752)] [外链图片转存中…(img-7VBhYDZs-1712537652753)]

既有Java、Web、PHP、也有C、小程序、Python等项目供你选择，真正体系化！

由于项目比较多，这里只是将部分目录截图出来，每个节点里面都包含素材文档、项目源码、讲解视频

如果你觉得这些内容对你有帮助，可以添加VX：vip1024c （备注项目大全获取） [外链图片转存中…(img-l4Faphtw-1712537652753)]

参考文章

评论可见，请评论后查看内容，谢谢！！！
 您阅读本篇文章共花了：