TreeMap
实现原理
在Java中，TreeMap是基于红黑树的NavigableMap实现。红黑树是一种自平衡的二叉搜索树，它通过在节点中引入一个额外的属性——颜色（红色或黑色），来保持树的平衡。这种平衡是通过旋转和重新着色操作来维护的，确保了以下性质：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色。
- 所有叶子节点（NIL节点，空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的（不会有两个连续的红色节点）。
- 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。
由于这些性质，红黑树可以确保最长的路径不会超过最短路径的两倍，因此在最坏的情况下，操作的时间复杂度能够保持在O(log n)。
TreeMap利用红黑树的性质来实现键值对的有序存储。它保证了键的排序，这个排序可以是自然排序（根据键的Comparable接口），也可以是构造TreeMap时提供的Comparator。
用途
TreeMap在需要以下特性的场景中非常有用：
-
有序的键值对：
TreeMap中的键总是有序的，无论是按自然排序还是自定义排序。这对于需要有序遍历键值对的应用非常重要。 -
快速查找：由于红黑树的性质，
TreeMap提供了O(log n)时间复杂度的查找性能。 -
范围查找和操作：
TreeMap实现了NavigableMap接口，提供了一系列的导航方法，如firstEntry(),lastEntry(),higherEntry(),lowerEntry()等，这些方法使得范围查找和操作变得简单高效。 -
键值对的自动排序：在
TreeMap中，当添加或删除键值对时，它会自动维护排序顺序。 -
子映射操作：可以非常方便地获取
TreeMap的子映射，例如headMap(),tailMap(),subMap()等方法，这些方法返回的是原映射的视图，而不是副本。
示例
下面是一个简单的TreeMap示例，展示了如何在Java中使用它：
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
// 创建一个 TreeMap，键按自然顺序排序
TreeMap<Integer, String> treeMap = new TreeMap<>();
// 添加键值对
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");
// 遍历键值对
treeMap.forEach((key, value) -> System.out.println(key + " => " + value));
// 获取并操作第一个（最小的键）和最后一个（最大的键）的条目
System.out.println("First Entry: " + treeMap.firstEntry());
System.out.println("Last Entry: " + treeMap.lastEntry());
// 获取大于或等于给定键的最小键的条目
System.out.println("Ceiling Entry for 2: " + treeMap.ceilingEntry(2));
}
}
在这个例子中，整数键被添加到TreeMap中，并且由于整数具有自然的比较方法，它们会被自动排序。然后，我们遍历了映射，并使用了一些NavigableMap接口的方法来获取特定的条目。
区别
HashMap的底层是Array，所以HashMap在添加，查找，删除等方法上面速度会非常快。而TreeMap的底层是一个Tree结构，所以速度会比较慢。
另外HashMap因为要保存一个Array，所以会造成空间的浪费，而TreeMap只保存要保持的节点，所以占用的空间比较小。
HashMap如果出现hash冲突的话，效率会变差，不过在java 8进行TreeNode转换之后，效率有很大的提升。
TreeMap在添加和删除节点的时候会进行重排序，会对性能有所影响。